JAVA递归实现线索化二叉树

基础理论

首先，二叉树递归遍历分为先序遍历、中序遍历和后序遍历。

先序遍历为：根节点+左子树+右子树

中序遍历为：左子树+根节点+右子树

后序遍历为：左子树+右子树+根节点

（只要记住根节点在哪里就是什么遍历，且都是先左再右）

线索化

现在有这么一棵二叉树，它的数据结构由左节点+权+右节点构成。

可以看到4,5,6,7这几个节点的左右节点空间被浪费了。因此，线索化是指有效利用这些空间。

中序遍历的顺序为：4 2 5 1 6 3 7

现在引入前驱节点以及后继节点。

前驱节点：线索化二叉树时，一个节点的前一个节点

后继节点：线索化二叉树时，一个节点的后一个节点

（例如下图：根据中序遍历，5的前驱节点是2 , 5的后继节点是1）

(中序遍历)实现线索化二叉树

定义数据结构ThreadedNode

1	//节点的权
2	int value;
3	//左儿子
4	ThreadedNode leftNode;
5	//右儿子
6	ThreadedNode rightNode;
7	//标识指针类型,其中0,1分别表示有无线索化，默认为0
8	int leftType;
9	int rightType;

中序遍历

1//中序遍历
2public void midShow() {
3   //左子节点
4   if(leftNode!=null) {
5      leftNode.midShow();
6   }
7   //当前节点
8   System.out.println(value);
9   //右子节点
10   if(rightNode!=null) {
11      rightNode.midShow();
12   }
13}

这里使用递归的方式来实现。我们先把问题简单化，只看红圈的部分，如下图

定义一个节点pre用来存储当前节点，类似指针。

从根节点1开始递归，如果当前节点为空，返回，到4，此时4的前驱结点为null,结点5的前驱结点为2

遍历到5的时候指向前驱结点2，前驱结点2为上一层递归的指针，因此指向它的前驱结点就行，再把左指针类型置为1

如果当前节点的前驱结点pre的右指针为null,则将它设置为当前节点，此时即4的后继结点为2，并将右指针类型置为1

每处理一个节点，当前节点是下一个节点的前驱节点

线索化二叉树ThreadedBinaryTree

1	//中序线索化二叉树
2	public void threadNodes() {
3		threadNodes(root);
4	}
5	
6	public void threadNodes(ThreadedNode node) {
7		//当前节点如果为null，直接返回
8		if(node==null) {
9			return;
10		}
11		//处理前驱节点
12		if(node.leftNode==null){
13			//让当前节点的左指针指向前驱节点
14			node.leftNode=pre;
15			//改变当前节点左指针的类型
16			node.leftType=1;
17		}
18		//处理前驱的右指针，如果前驱节点的右指针是null(没有指下右子树)
19		if(pre!=null&&pre.rightNode==null) {
20			//让前驱节点的右指针指向当前节点
21			pre.rightNode=node;
22			//改变前驱节点的右指针类型
23			pre.rightType=1;
24		}
25		//每处理一个节点，当前节点是下一个节点的前驱节点
26		pre=node;
27	}

现在再把上面这段代码按照中序遍历的方式放在中间,进行递归

1		//当前节点如果为null，直接返回
2		if(node==null) {
3			return;
4		}
5		//处理左子树
6		threadNodes(node.leftNode);
7//----------------------------------------------------------
8		//处理前驱节点
9		if(node.leftNode==null){
10			//让当前节点的左指针指向前驱节点
11			node.leftNode=pre;
12			//改变当前节点左指针的类型
13			node.leftType=1;
14		}
15		//处理前驱的右指针，如果前驱节点的右指针是null(没有指下右子树)
16		if(pre!=null&&pre.rightNode==null) {
17			//让前驱节点的右指针指向当前节点
18			pre.rightNode=node;
19			//改变前驱节点的右指针类型
20			pre.rightType=1;
21		}
22		//每处理一个节点，当前节点是下一个节点的前驱节点
23		pre=node;
24//-----------------------------------------------------------
25		//处理右子树
26		threadNodes(node.rightNode);
27	}

现在编写测试方法

1package demo7;
2
3public class TestThreadedBinaryTree {
4
5	public static void main(String[] args) {
6		//创建一颗树
7		ThreadedBinaryTree binTree = new ThreadedBinaryTree();
8		//创建一个根节点
9		ThreadedNode root = new ThreadedNode(1);
10		//把根节点赋给树
11		binTree.setRoot(root);
12		//创建一个左节点
13		ThreadedNode rootL = new ThreadedNode(2);
14		//把新创建的节点设置为根节点的子节点
15		root.setLeftNode(rootL);
16		//创建一个右节点
17		ThreadedNode rootR = new ThreadedNode(3);
18		//把新创建的节点设置为根节点的子节点
19		root.setRightNode(rootR);
20		//为第二层的左节点创建两个子节点
21		rootL.setLeftNode(new ThreadedNode(4));
22		ThreadedNode fiveNode = new ThreadedNode(5);
23		rootL.setRightNode(fiveNode);
24		//为第二层的右节点创建两个子节点
25		rootR.setLeftNode(new ThreadedNode(6));
26		rootR.setRightNode(new ThreadedNode(7));
27		//中序遍历树
28		binTree.midShow();
29		System.out.println("===============");
30		//中前线索化二叉树
31		binTree.threadNodes();
32		binTree.threadIterate();
33	}
34
35}