数据结构与算法__07--前序、中序、后序线索化二叉树,前序、中序、后序线索化二叉树遍历(Java语言版本)

简介: 前序、中序、后序线索化二叉树,前序、中序、后序线索化二叉树遍历汇总(Java语言版本)

@[toc]

1 前序

//前序线索化二叉树
public void threadedPreNode(HeroNode node) {
    if (node == null) {
        return;
    }
    //线索化当前节点
    if (node.getLeft() == null) {
        node.setLeft(pre);
        node.setLeftType(1);
    }
    if (pre != null && pre.getRight() == null) {
        pre.setRight(node);
        pre.setRightType(1);
    }
    pre = node;
    //线索化左子树
    if (node.getLeftType() != 1) {
        threadedPreNode(node.getLeft());
    }
    //线索化右子树
    if (node.getRightType() != 1) {
        threadedPreNode(node.getRight());
    }
 
}
 
//前序线索化遍历
public void threadedPreList() {
    //定义一个变量,存储当前遍历的结点,从root开始
    HeroNode node = root;
    while (node != null) {
        //打印当前这个结点
        System.out.println(node);
        while (node.getLeftType() == 0) {
            node = node.getLeft();
            System.out.println(node);
        }
        //如果当前结点的右指针指向的是后继结点,就一直输出
        while (node.getRightType() == 1) {
            //获取到当前结点的后继结点
            node = node.getRight();
            System.out.println(node);
        }
        //替换这个遍历的结点
        node = node.getRight();
 
    }
}

2 后序

2.1 为节点添加父节点

2.1.1 节点中创建方法

//前序遍历添加父节点
public void preOrderAddPar() {
    while (this.getLeft() != null) {
        this.getLeft().setParent(this);
        break;
    }
    while (this.getRight() != null) {
        this.getRight().setParent(this);
        break;
    }
 
    if (this.getLeft() != null) {//2.向左遍历
        this.getLeft().preOrderAddPar();
    }
    if (this.getRight() != null) {//3.向右遍历
        this.getRight().preOrderAddPar();
    }
}

2.1.2 二叉树中创建方法

//前序遍历添加父节点
public void preOrderAddPar() {
    if (this.root != null) {
        this.root.preOrderAddPar();
    } else {
        System.out.println("二叉树为空");
    }
}

2.2 后序线索化及遍历

//后序线索化二叉树   8,10,3,14,6,1
public void threadedPostNode(HeroNode node) {
    if (node == null) {
        return;
    }
    //线索化左子树
    threadedPostNode(node.getLeft());
 
    //线索化右子树
    threadedPostNode(node.getRight());
    //线索化当前节点
    if (node.getLeft() == null) {
        node.setLeft(pre);
        node.setLeftType(1);
    }
    if (pre != null && pre.getRight() == null) {
        pre.setRight(node);
        pre.setRightType(1);
    }
    pre = node;
}
 
//后序遍历线索化二叉树的方法
public void threadedPostList() {//8,10,3,14,6,1
    HeroNode node = root;
    while(node != null && node.getLeftType()!=1) {
        node = node.getLeft();
    }
 
    HeroNode pre = null;
    while(node != null) {
        //右节点是线索
        if (node.getRightType() == 1) {
            System.out.println(node);
            pre = node;
            node = node.getRight();
 
        } else {
            //如果上个处理的节点是当前节点的右节点
            if (node.getRight() == pre) {
                System.out.println(node);
                if (node == root) {
                    return;
                }
 
                pre = node;
                node = node.getParent();
 
            } else {    //如果从左节点的进入则找到有子树的最左节点
                node = node.getRight();
                while (node != null && node.getLeftType() !=1) {
                    node = node.getLeft();
                }
            }
        }
    }
}

3 中序

//重载中序线索化二叉树
public void threadedNode() {
    threadedNode(root);
}
 
//中序遍历线索化二叉树的方法
public void threadedList() {
    //定义一个变量,存储当前遍历的结点,从root开始
    HeroNode node = root;
    while (node != null) {
        //循环的找到leftType == 1的结点,第一个找到就是8结点
        //后面随着遍历而变化,因为当leftType==1时,说明该结点是按照线索化
        //处理后的有效结点
        while (node.getLeftType() == 0) {
            node = node.getLeft();
        }
 
        //打印当前这个结点
        System.out.println(node);
        //如果当前结点的右指针指向的是后继结点,就一直输出
        while (node.getRightType() == 1) {
            //获取到当前结点的后继结点
            node = node.getRight();
            System.out.println(node);
        }
        //替换这个遍历的结点
        node = node.getRight();
 
    }
}
 
//中序线索化二叉树
public void threadedNode(HeroNode node) {
    if (node == null) {
        return;
    }
    //线索化左子树
    threadedNode(node.getLeft());
    //线索化当前节点
    if (node.getLeft() == null) {
        node.setLeft(pre);
        node.setLeftType(1);
    }
    if (pre != null && pre.getRight() == null) {
        pre.setRight(node);
        pre.setRightType(1);
    }
    pre = node;
    //线索化右子树
    threadedNode(node.getRight());
}

4 完整代码

package edu.seu.demo10tree.demothreadedbinarytree;
 
public class Demo01ThreadedBinaryTree {
    public static void main(String[] args) {
        //测试一把中序线索二叉树的功能
        HeroNode root = new HeroNode(1, "tom");
        HeroNode node2 = new HeroNode(3, "jack");
        HeroNode node3 = new HeroNode(6, "smith");
        HeroNode node4 = new HeroNode(8, "mary");
        HeroNode node5 = new HeroNode(10, "king");
        HeroNode node6 = new HeroNode(14, "dim");
 
        //二叉树,后面我们要递归创建, 现在简单处理使用手动创建
        root.setLeft(node2);
        root.setRight(node3);
        node2.setLeft(node4);
        node2.setRight(node5);
        node3.setLeft(node6);
 
        
        ThreadedBinaryTree threadedBinaryTree = new ThreadedBinaryTree();
        threadedBinaryTree.setRoot(root);
 
        //为节点遍历添加父节点
        threadedBinaryTree.preOrderAddPar();
        
//        中序  8, 3, 10, 1, 14, 6
/*        threadedBinaryTree.threadedNode();
        HeroNode leftNode = node5.getLeft();
        HeroNode rightNode = node5.getRight();
        System.out.println("10号结点的前驱结点是="  + leftNode); //3
        System.out.println("10号结点的后继结点是="  + rightNode); //1
        System.out.println("使用线索化的方式遍历 线索化二叉树");
        threadedBinaryTree.threadedList();*/
 
//        前序 1,3,8,10,6,14
/*        threadedBinaryTree.threadedPreNode(root);
        HeroNode leftNode = node5.getLeft();
        HeroNode rightNode = node5.getRight();
        System.out.println("10号结点的前驱结点是=" + leftNode);
        System.out.println("10号结点的后继结点是=" + rightNode);
        System.out.println("使用线索化的方式遍历 线索化二叉树");
        threadedBinaryTree.threadedPreList();*/
 
        //后序8,10,3,14,6,1
        threadedBinaryTree.threadedPostNode(root);
        HeroNode leftNode = node5.getLeft();
        HeroNode rightNode = node5.getRight();
        System.out.println("10号结点的前驱结点是=" + leftNode);
        System.out.println("10号结点的后继结点是=" + rightNode);
 
        System.out.println("使用线索化的方式遍历 线索化二叉树");
        threadedBinaryTree.threadedPostList();
 
    }
}
 
class HeroNode {
    private int no;//英雄编号
    private String name;//姓名
    private HeroNode left;//左子节点
    private HeroNode right;//右子节点
    private HeroNode parent;//父节点
    private int rightType;//表示右子节点:指针:0,后继:1
    private int leftType;//表示左子节点:指针:0  前驱:1
 
    public HeroNode getParent() {
        return parent;
    }
 
    public void setParent(HeroNode parent) {
        this.parent = parent;
    }
 
    public int getRightType() {
        return rightType;
    }
 
    public void setRightType(int rightType) {
        this.rightType = rightType;
    }
 
    public int getLeftType() {
        return leftType;
    }
 
    public void setLeftType(int leftType) {
        this.leftType = leftType;
    }
 
    public HeroNode(int no, String name) {
        this.no = no;
        this.name = name;
    }
 
    //读取与设置私有变量
    public int getNo() {
        return no;
    }
 
    public void setNo(int no) {
        this.no = no;
    }
 
    public String getName() {
        return name;
    }
 
    public void setName(String name) {
        this.name = name;
    }
 
    public HeroNode getLeft() {
        return left;
    }
 
    public void setLeft(HeroNode left) {
        this.left = left;
    }
 
    public HeroNode getRight() {
        return right;
    }
 
    public void setRight(HeroNode right) {
        this.right = right;
    }
 
    //打印输出
 
    @Override
    public String toString() {
        return "HeroNode{" +
                "no=" + no +
                ", name='" + name + '\'' +
                '}';
    }
 
    //前序遍历添加父节点
    public void preOrderAddPar() {
        while (this.getLeft() != null) {
            this.getLeft().setParent(this);
            break;
        }
        while (this.getRight() != null) {
            this.getRight().setParent(this);
            break;
        }
 
        if (this.getLeft() != null) {//2.向左遍历
            this.getLeft().preOrderAddPar();
        }
        if (this.getRight() != null) {//3.向右遍历
            this.getRight().preOrderAddPar();
        }
    }
 
    //前序遍历
    public void preOrder() {
        System.out.println(this);//1.输出父节点
        if (this.getLeft() != null) {//2.向左遍历
            this.getLeft().preOrder();
        }
        if (this.getRight() != null) {//3.向右遍历
            this.getRight().preOrder();
        }
    }
 
    //中序遍历
    public void infixOrder() {
        if (this.getLeft() != null) {
            this.getLeft().infixOrder();
        }
        System.out.println(this);
        if (this.getRight() != null) {//3.向右遍历
            this.getRight().infixOrder();
        }
    }
 
    //后序遍历
    public void postOrder() {
        if (this.getLeft() != null) {
            this.getLeft().postOrder();
        }
        if (this.getRight() != null) {//3.向右遍历
            this.getRight().postOrder();
        }
        System.out.println(this);
    }
 
    //前序遍历查找
    public HeroNode preOrderSearch(int no) {
        System.out.println("前序查找比较次数");
        if (this.getNo() == no) {
            return this;
        }
        HeroNode resHero = null;
        if (this.left != null) {
            resHero = this.left.preOrderSearch(no);
        }
        if (resHero != null) {
            return resHero;
        }
        if (this.right != null) {
            resHero = this.right.preOrderSearch(no);
        }
        return resHero;
    }
 
    //中序遍历查找
    public HeroNode infixOrderSearch(int no) {
        HeroNode resHero = null;
        if (this.left != null) {
            resHero = this.left.infixOrderSearch(no);
        }
        if (resHero != null) {
            return resHero;
        }
        System.out.println("中序查找比较次数");
        if (this.getNo() == no) {
            return this;
        }
        if (this.right != null) {
            resHero = this.right.infixOrderSearch(no);
        }
        return resHero;
    }
 
    //后序遍历查找
    public HeroNode postOrderSearch(int no) {
        HeroNode resHero = null;
        if (this.left != null) {
            resHero = this.left.postOrderSearch(no);
        }
        if (resHero != null) {
            return resHero;
        }
 
        if (this.right != null) {
            resHero = this.right.postOrderSearch(no);
        }
        if (resHero != null) {
            return resHero;
        }
        System.out.println("后序查找比较次数");
        if (this.getNo() == no) {
            return this;
        }
        return resHero;
    }
 
    //删除节点
    public void delHeroNode(int no) {
        if (this.left != null && this.left.getNo() == no) {
            this.left = null;
            return;
        }
        if (this.right != null && this.right.getNo() == no) {
            this.right = null;
            return;
        }
        if (this.left != null) {
            this.left.delHeroNode(no);
        }
        if (this.right != null) {
            this.right.delHeroNode(no);
        }
    }
 
}
 
class ThreadedBinaryTree {
    private HeroNode root;//根节点
    private HeroNode pre = null;
 
    public ThreadedBinaryTree() {
    }
 
    public HeroNode getRoot() {
        return root;
    }
 
    public void setRoot(HeroNode root) {
        this.root = root;
    }
 
    //重载中序线索化二叉树
    public void threadedNode() {
        threadedNode(root);
    }
 
    //中序遍历线索化二叉树的方法
    public void threadedList() {
        //定义一个变量,存储当前遍历的结点,从root开始
        HeroNode node = root;
        while (node != null) {
            //循环的找到leftType == 1的结点,第一个找到就是8结点
            //后面随着遍历而变化,因为当leftType==1时,说明该结点是按照线索化
            //处理后的有效结点
            while (node.getLeftType() == 0) {
                node = node.getLeft();
            }
 
            //打印当前这个结点
            System.out.println(node);
            //如果当前结点的右指针指向的是后继结点,就一直输出
            while (node.getRightType() == 1) {
                //获取到当前结点的后继结点
                node = node.getRight();
                System.out.println(node);
            }
            //替换这个遍历的结点
            node = node.getRight();
 
        }
    }
 
    //中序线索化二叉树
    public void threadedNode(HeroNode node) {
        if (node == null) {
            return;
        }
        //线索化左子树
        threadedNode(node.getLeft());
        //线索化当前节点
        if (node.getLeft() == null) {
            node.setLeft(pre);
            node.setLeftType(1);
        }
        if (pre != null && pre.getRight() == null) {
            pre.setRight(node);
            pre.setRightType(1);
        }
        pre = node;
        //线索化右子树
        threadedNode(node.getRight());
    }
 
    //后序线索化二叉树   8,10,3,14,6,1
    public void threadedPostNode(HeroNode node) {
        if (node == null) {
            return;
        }
        //线索化左子树
        threadedPostNode(node.getLeft());
 
        //线索化右子树
        threadedPostNode(node.getRight());
        //线索化当前节点
        if (node.getLeft() == null) {
            node.setLeft(pre);
            node.setLeftType(1);
        }
        if (pre != null && pre.getRight() == null) {
            pre.setRight(node);
            pre.setRightType(1);
        }
        pre = node;
    }
 
    //后序遍历线索化二叉树的方法
    public void threadedPostList() {//8,10,3,14,6,1
        HeroNode node = root;
        while(node != null && node.getLeftType()!=1) {
            node = node.getLeft();
        }
 
        HeroNode preNode = null;
        while(node != null) {
            //右节点是线索
            if (node.getRightType() == 1) {
                System.out.println(node);
                preNode = node;
                node = node.getRight();
 
            } else {
                //如果上个处理的节点是当前节点的右节点
                if (node.getRight() == preNode) {
                    System.out.println(node);
                    if (node == root) {
                        return;
                    }
 
                    preNode = node;
                    node = node.getParent();
 
                } else {    //如果从左节点的进入则找到有子树的最左节点
                    node = node.getRight();
                    while (node != null && node.getLeftType() !=1) {
                        node = node.getLeft();
                    }
                }
            }
        }
    }
 
    //前序线索化二叉树
    public void threadedPreNode(HeroNode node) {
        if (node == null) {
            return;
        }
        //线索化当前节点
        if (node.getLeft() == null) {
            node.setLeft(pre);
            node.setLeftType(1);
        }
        if (pre != null && pre.getRight() == null) {
            pre.setRight(node);
            pre.setRightType(1);
        }
        pre = node;
        //线索化左子树
        if (node.getLeftType() != 1) {
            threadedPreNode(node.getLeft());
        }
        //线索化右子树
        if (node.getRightType() != 1) {
            threadedPreNode(node.getRight());
        }
 
    }
 
    //前序线索化遍历
    public void threadedPreList() {
        //定义一个变量,存储当前遍历的结点,从root开始
        HeroNode node = root;
        while (node != null) {
            //打印当前这个结点
            System.out.println(node);
            while (node.getLeftType() == 0) {
                node = node.getLeft();
                System.out.println(node);
            }
            //如果当前结点的右指针指向的是后继结点,就一直输出
            while (node.getRightType() == 1) {
                //获取到当前结点的后继结点
                node = node.getRight();
                System.out.println(node);
            }
            //替换这个遍历的结点
            node = node.getRight();
 
        }
    }
 
    //前序遍历添加父节点
    public void preOrderAddPar() {
        if (this.root != null) {
            this.root.preOrderAddPar();
        } else {
            System.out.println("二叉树为空");
        }
    }
    //前序遍历
    public void preOrder() {
        if (this.root != null) {
            this.root.preOrder();
        } else {
            System.out.println("二叉树为空");
        }
    }
 
    //中序遍历
    public void infixOrder() {
        if (this.root != null) {
            this.root.infixOrder();
        } else {
            System.out.println("二叉树为空");
        }
    }
 
    //后序遍历
    public void postOrder() {
        if (this.root != null) {
            this.root.postOrder();
        } else {
            System.out.println("二叉树为空");
        }
    }
 
    //前序遍历查找
    public HeroNode preOrderSearch(int no) {
        if (root != null) {
            return root.preOrderSearch(no);
        } else {
            return null;
        }
    }
 
    //中序遍历查找
    public HeroNode infixOrderSearch(int no) {
        if (root != null) {
            return root.infixOrderSearch(no);
        } else {
            return null;
        }
    }
 
    //后序遍历查找
    public HeroNode postOrderSearch(int no) {
        if (root != null) {
            return this.root.postOrderSearch(no);
        } else {
            return null;
        }
    }
 
    //删除节点
    public void delHeroNode(int no) {
        if (root != null) {
            if (root.getNo() == no) {
                root = null;
            } else {
                root.delHeroNode(no);
            }
        } else {
            System.out.println("二叉树为空");
        }
    }
}
相关文章
|
1月前
|
前端开发 Java
java实现队列数据结构代码详解
本文详细解析了Java中队列数据结构的实现,包括队列的基本概念、应用场景及代码实现。队列是一种遵循“先进先出”原则的线性结构,支持在队尾插入和队头删除操作。文章介绍了顺序队列与链式队列,并重点分析了循环队列的实现方式以解决溢出问题。通过具体代码示例(如`enqueue`入队和`dequeue`出队),展示了队列的操作逻辑,帮助读者深入理解其工作机制。
|
2月前
|
存储 负载均衡 算法
基于 C++ 语言的迪杰斯特拉算法在局域网计算机管理中的应用剖析
在局域网计算机管理中,迪杰斯特拉算法用于优化网络路径、分配资源和定位故障节点,确保高效稳定的网络环境。该算法通过计算最短路径,提升数据传输速率与稳定性,实现负载均衡并快速排除故障。C++代码示例展示了其在网络模拟中的应用,为企业信息化建设提供有力支持。
87 15
|
2月前
|
监控 算法 安全
基于 PHP 语言深度优先搜索算法的局域网网络监控软件研究
在当下数字化时代,局域网作为企业与机构内部信息交互的核心载体,其稳定性与安全性备受关注。局域网网络监控软件随之兴起,成为保障网络正常运转的关键工具。此类软件的高效运行依托于多种数据结构与算法,本文将聚焦深度优先搜索(DFS)算法,探究其在局域网网络监控软件中的应用,并借助 PHP 语言代码示例予以详细阐释。
56 1
|
3月前
|
运维 监控 算法
监控局域网其他电脑:Go 语言迪杰斯特拉算法的高效应用
在信息化时代,监控局域网成为网络管理与安全防护的关键需求。本文探讨了迪杰斯特拉(Dijkstra)算法在监控局域网中的应用,通过计算最短路径优化数据传输和故障检测。文中提供了使用Go语言实现的代码例程,展示了如何高效地进行网络监控,确保局域网的稳定运行和数据安全。迪杰斯特拉算法能减少传输延迟和带宽消耗,及时发现并处理网络故障,适用于复杂网络环境下的管理和维护。
|
5月前
|
存储 监控 算法
员工上网行为监控中的Go语言算法:布隆过滤器的应用
在信息化高速发展的时代,企业上网行为监管至关重要。布隆过滤器作为一种高效、节省空间的概率性数据结构,适用于大规模URL查询与匹配,是实现精准上网行为管理的理想选择。本文探讨了布隆过滤器的原理及其优缺点,并展示了如何使用Go语言实现该算法,以提升企业网络管理效率和安全性。尽管存在误报等局限性,但合理配置下,布隆过滤器为企业提供了经济有效的解决方案。
125 8
员工上网行为监控中的Go语言算法:布隆过滤器的应用
|
1月前
|
存储 Java 编译器
Java 中 .length 的使用方法:深入理解 Java 数据结构中的长度获取机制
本文深入解析了 Java 中 `.length` 的使用方法及其在不同数据结构中的应用。对于数组,通过 `.length` 属性获取元素数量;字符串则使用 `.length()` 方法计算字符数;集合类如 `ArrayList` 采用 `.size()` 方法统计元素个数。此外,基本数据类型和包装类不支持长度属性。掌握这些区别,有助于开发者避免常见错误,提升代码质量。
80 1
|
2月前
|
存储 算法 安全
企业员工数据泄露防范策略:基于 C++ 语言的布隆过滤器算法剖析[如何防止员工泄密]
企业运营过程中,防范员工泄密是信息安全领域的核心议题。员工泄密可能致使企业核心数据、商业机密等关键资产的流失,进而给企业造成严重损失。为应对这一挑战,借助恰当的数据结构与算法成为强化信息防护的有效路径。本文专注于 C++ 语言中的布隆过滤器算法,深入探究其在防范员工泄密场景中的应用。
59 8
|
2月前
|
存储 监控 算法
基于 PHP 语言的滑动窗口频率统计算法在公司局域网监控电脑日志分析中的应用研究
在当代企业网络架构中,公司局域网监控电脑系统需实时处理海量终端设备产生的连接日志。每台设备平均每分钟生成 3 至 5 条网络请求记录,这对监控系统的数据处理能力提出了极高要求。传统关系型数据库在应对这种高频写入场景时,性能往往难以令人满意。故而,引入特定的内存数据结构与优化算法成为必然选择。
47 3
|
3月前
|
算法 安全 Go
公司局域网管理系统里的 Go 语言 Bloom Filter 算法,太值得深挖了
本文探讨了如何利用 Go 语言中的 Bloom Filter 算法提升公司局域网管理系统的性能。Bloom Filter 是一种高效的空间节省型数据结构,适用于快速判断元素是否存在于集合中。文中通过具体代码示例展示了如何在 Go 中实现 Bloom Filter,并应用于局域网的 IP 访问控制,显著提高系统响应速度和安全性。随着网络规模扩大和技术进步,持续优化算法和结合其他安全技术将是企业维持网络竞争力的关键。
82 2
公司局域网管理系统里的 Go 语言 Bloom Filter 算法,太值得深挖了
|
3月前
|
存储 缓存 监控
企业监控软件中 Go 语言哈希表算法的应用研究与分析
在数字化时代,企业监控软件对企业的稳定运营至关重要。哈希表(散列表)作为高效的数据结构,广泛应用于企业监控中,如设备状态管理、数据分类和缓存机制。Go 语言中的 map 实现了哈希表,能快速处理海量监控数据,确保实时准确反映设备状态,提升系统性能,助力企业实现智能化管理。
54 3

热门文章

最新文章