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分别表示有无线索化,默认为0int 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();}}