JAVA递归实现线索化二叉树

Wesley13
• 阅读 651

JAVA递归实现线索化二叉树

基础理论

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

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

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

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

(只要记住根节点在哪里就是什么遍历,且都是先左再右)

线索化

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

JAVA递归实现线索化二叉树

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

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

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

前驱节点:线索化二叉树时,一个节点的前一个节点

后继节点:线索化二叉树时,一个节点的后一个节点

(例如下图:根据中序遍历,5的前驱节点是2 , 5的后继节点是1)

JAVA递归实现线索化二叉树

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

定义数据结构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();
   }
}

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

JAVA递归实现线索化二叉树

定义一个节点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();
    }

}
点赞
收藏
评论区
推荐文章
白茶清欢 白茶清欢
3年前
js实现二叉树、二叉查找树
树是一种数据结构,该章节讨论二叉树(二叉树的每个节点的子节点不允许超过两个),二叉树中有又分为完全二叉树和不完全二叉树.....不在本章节赘述相关概念,感兴趣可以去查阅《数据结构》。你将会获得:1.如何使用js实现二叉查找树。2.学会前、中、后序遍历。3.了解相关实现原理阅读时长5min,可选择直接调试代码特点    二叉查找树中序遍历后
九路 九路
3年前
前端学数据结构与算法:二叉树的四种遍历方式及其应用
前言上一章我们从0到1的实现了一颗二叉搜索树,以及理解了二叉搜索树的特性与基本操作,这一章介绍关于二叉树的更多操作,也就是树的遍历,对树的每个节点进行访问。主要包括前序遍历、中序遍历、后序遍历、层序遍历,前面三种也叫深度优先遍历(DFS),最后的层序遍历也叫广度优先遍历(BFS),理解这四种遍历方式的不同,再遇到树相关的算法问题时,也就能更加游刃有余。这
Wesley13 Wesley13
2年前
java——平衡二叉树 AVLTree、AVLMap、AVLSet
平衡二叉树:对于任意一个节点,左子树和右子树的高度差不能超过1packageDate_pacage;importjava.util.ArrayList;publicclassAVLTree<KextendsComparable<K,V{privateclassNod
Stella981 Stella981
2年前
LeetCode(98): 验证二叉搜索树
Medium!题目描述:给定一个二叉树,判断其是否是一个有效的二叉搜索树。一个二叉搜索树具有如下特征:节点的左子树只包含小于当前节点的数。节点的右子树只包含大于当前节点的数。所有左子树和右子树自身必须也是二叉搜索树。示例 1:输入:2/\
Wesley13 Wesley13
2年前
Java实现二叉树的前序、中序、后序、层序遍历(非递归方法)
Java实现二叉树的前序、中序、后序、层序遍历(非递归方法)(https://www.oschina.net/action/GoToLink?urlhttp%3A%2F%2Fwww.cnblogs.com%2Fliuyang0%2Fp%2F6271331.html)
Wesley13 Wesley13
2年前
PHP数据结构与算法:二叉树
一、定义二叉树是每个节点最多有两个子树的树结构。通常子树被称作“左子树”(leftsubtree)和“右子树”(rightsubtree)。二、特性1.在二叉树的第i层上至多有2^(i1)个结点(i0)2.深度为k的二叉树至多有2^k1个结点(k0)3.对于任意一棵二叉树,如果其叶结点数为N0,而
Wesley13 Wesley13
2年前
04.重建二叉树 (Java)
题目描述输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6},则重建二叉树并返回。(https://www.oschina.net/action/GoToLink?urlht
Wesley13 Wesley13
2年前
6.重建二叉树(代码未完成)
 题目:输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6},则重建出图2.6所示的二叉树并输出它的头结点。!(https://static.oschina.net/uploads
Wesley13 Wesley13
2年前
98. 验证二叉搜索树
题目描述给定一个二叉树,判断其是否是一个有效的二叉搜索树。假设一个二叉搜索树具有如下特征:节点的左子树只包含小于当前节点的数。节点的右子树只包含大于当前节点的数。所有左子树和右子树自身必须也是二叉搜索树。输入:5/\14 /\ 
菜园前端 菜园前端
11个月前
什么是二叉树?
原文链接:什么是二叉树?树中每个节点最多只能有两个子节点,在JavaScript中一般都是通过Object来模拟二叉树。常用操作前序遍历中序遍历后序遍历前序遍历根左右。口诀:1.访问根节点2.对根节点的左子树进行前序遍历3.对根节点的右子树进行前序遍历通过