编程语言
218
JAVA递归实现线索化二叉树
基础理论
首先，二叉树递归遍历分为先序遍历、中序遍历和后序遍历。
先序遍历为：根节点+左子树+右子树
中序遍历为：左子树+根节点+右子树
后序遍历为：左子树+右子树+根节点
（只要记住根节点在哪里就是什么遍历，且都是先左再右）
线索化
现在有这么一棵二叉树，它的数据结构由左节点+权+右节点构成。
可以看到4,5,6,7这几个节点的左右节点空间被浪费了。因此，线索化是指有效利用这些空间。
中序遍历的顺序为：4 2 5 1 6 3 7
现在引入前驱节点以及后继节点。
前驱节点：线索化二叉树时，一个节点的前一个节点
后继节点：线索化二叉树时，一个节点的后一个节点
（例如下图：根据中序遍历，5的前驱节点是2 , 5的后继节点是1）
(中序遍历)实现线索化二叉树
定义数据结构ThreadedNode
//节点的权 int value; //左儿子 ThreadedNode leftNode; //右儿子 ThreadedNode rightNode; //标识指针类型,其中0,1分别表示有无线索化，默认为0 int leftType; int rightType;
中序遍历
//中序遍历 public void midShow() { //左子节点 if(leftNode!=null) { leftNode.midShow(); } //当前节点 System.out.println(value); //右子节点 if(rightNode!=null) { rightNode.midShow(); } }
这里使用递归的方式来实现。我们先把问题简单化，只看红圈的部分，如下图
定义一个节点pre用来存储当前节点，类似指针。
从根节点1开始递归，如果当前节点为空，返回，到4，此时4的前驱结点为null,结点5的前驱结点为2
遍历到5的时候指向前驱结点2，前驱结点2为上一层递归的指针，因此指向它的前驱结点就行，再把左指针类型置为1
如果当前节点的前驱结点pre的右指针为null,则将它设置为当前节点，此时即4的后继结点为2，并将右指针类型置为1
每处理一个节点，当前节点是下一个节点的前驱节点
线索化二叉树ThreadedBinaryTree
//中序线索化二叉树 public void threadNodes() { threadNodes(root); } public void threadNodes(ThreadedNode node) { //当前节点如果为null，直接返回 if(node==null) { return; } //处理前驱节点 if(node.leftNode==null){ //让当前节点的左指针指向前驱节点 node.leftNode=pre; //改变当前节点左指针的类型 node.leftType=1; } //处理前驱的右指针，如果前驱节点的右指针是null(没有指下右子树) if(pre!=null&&pre.rightNode==null) { //让前驱节点的右指针指向当前节点 pre.rightNode=node; //改变前驱节点的右指针类型 pre.rightType=1; } //每处理一个节点，当前节点是下一个节点的前驱节点 pre=node; }
现在再把上面这段代码按照中序遍历的方式放在中间,进行递归
//当前节点如果为null，直接返回 if(node==null) { return; } //处理左子树 threadNodes(node.leftNode); //---------------------------------------------------------- //处理前驱节点 if(node.leftNode==null){ //让当前节点的左指针指向前驱节点 node.leftNode=pre; //改变当前节点左指针的类型 node.leftType=1; } //处理前驱的右指针，如果前驱节点的右指针是null(没有指下右子树) if(pre!=null&&pre.rightNode==null) { //让前驱节点的右指针指向当前节点 pre.rightNode=node; //改变前驱节点的右指针类型 pre.rightType=1; } //每处理一个节点，当前节点是下一个节点的前驱节点 pre=node; //----------------------------------------------------------- //处理右子树 threadNodes(node.rightNode); }
现在编写测试方法
package demo7; public class TestThreadedBinaryTree { public static void main(String[] args) { //创建一颗树 ThreadedBinaryTree binTree = new ThreadedBinaryTree(); //创建一个根节点 ThreadedNode root = new ThreadedNode(1); //把根节点赋给树 binTree.setRoot(root); //创建一个左节点 ThreadedNode rootL = new ThreadedNode(2); //把新创建的节点设置为根节点的子节点 root.setLeftNode(rootL); //创建一个右节点 ThreadedNode rootR = new ThreadedNode(3); //把新创建的节点设置为根节点的子节点 root.setRightNode(rootR); //为第二层的左节点创建两个子节点 rootL.setLeftNode(new ThreadedNode(4)); ThreadedNode fiveNode = new ThreadedNode(5); rootL.setRightNode(fiveNode); //为第二层的右节点创建两个子节点 rootR.setLeftNode(new ThreadedNode(6)); rootR.setRightNode(new ThreadedNode(7)); //中序遍历树 binTree.midShow(); System.out.println("==============="); //中前线索化二叉树 binTree.threadNodes(); binTree.threadIterate(); } }
