备案控制台
探索云世界
开发者社区 开发与运维 文章 正文

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

2022-12-08 91
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 前序、中序、后序线索化二叉树，前序、中序、后序线索化二叉树遍历汇总（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("二叉树为空");
        }
    }
}
文章标签：
Java
算法
关键词：
Java语言
数据结构与算法二叉树
Java版本
数据结构java
算法java
月同学不写Bug
目录
相关文章
阿森要自信
|
16天前
|
算法
【算法与数据结构】二叉树（前中后）序遍历2
【算法与数据结构】二叉树（前中后）序遍历
阿森要自信
16 0
Cool架构
|
23天前
|
存储 算法 Java
Java数据结构与算法-java数据结构与算法（二）
Java数据结构与算法-java数据结构与算法
Cool架构
67 1
无糖可乐嘟嘟
|
25天前
|
数据采集 分布式计算 大数据
Java语言在大数据处理中的应用
传统的大数据处理往往依赖于庞大的数据中心和高性能的服务器，然而随着大数据时代的到来，Java作为一种强大的编程语言正在被广泛应用于大数据处理领域。本文将探讨Java语言在大数据处理中的优势和应用，以及其在分布式计算、数据处理和系统集成等方面的重要作用。
无糖可乐嘟嘟
26 5
一百减一是零
|
1天前
|
前端开发 Java Go
开发语言详解（python、java、Go(Golong)。。。。）
开发语言详解（python、java、Go(Golong)。。。。）
一百减一是零
36 0
源码宝
|
2天前
|
人工智能 前端开发 Java
Java语言开发的AI智慧导诊系统源码springboot+redis 3D互联网智导诊系统源码
智慧导诊解决盲目就诊问题，减轻分诊工作压力。降低挂错号比例，优化就诊流程，有效提高线上线下医疗机构接诊效率。可通过人体画像选择症状部位，了解对应病症信息和推荐就医科室。
源码宝
27 10
认真学习的小雅兰.
|
2天前
|
算法 DataX
二叉树（中）+Leetcode每日一题——“数据结构与算法”“剑指Offer55-I. 二叉树的深度”“100.相同的树”“965.单值二叉树”
二叉树（中）+Leetcode每日一题——“数据结构与算法”“剑指Offer55-I. 二叉树的深度”“100.相同的树”“965.单值二叉树”
认真学习的小雅兰.
5 0
桃李春风一杯酒
|
6天前
|
Java Android开发 C++
Kotlin vs Java：选择最佳语言进行安卓开发
【4月更文挑战第13天】Java曾是安卓开发的主流语言，但Kotlin的崛起改变了这一局面。Google在2017年支持Kotlin，引发两者优劣讨论。Java以其成熟稳定、强大生态和跨平台能力占优，但代码冗长、开发效率低和语言特性过时是短板。Kotlin则以简洁语法、空安全设计和高度兼容Java脱颖而出，但社区和生态系统仍在发展中，可能存在学习曲线和性能问题。选择语言应考虑项目需求、团队熟悉度、维护性、性能和生态系统。无论选择哪种，理解其差异并适应新技术至关重要。
桃李春风一杯酒
17 4
当家滴喵啊
|
11天前
|
算法 安全 Java
java代码 实现AES_CMAC 算法测试
该代码实现了一个AES-CMAC算法的简单测试，使用Bouncy Castle作为安全提供者。静态变量K定义了固定密钥。`Aes_Cmac`函数接受密钥和消息，返回AES-CMAC生成的MAC值。在`main`方法中，程序对给定的消息进行AES-CMAC加密，然后模拟接收ECU的加密结果并进行比较。如果两者匹配，输出"验证成功"，否则输出"验证失败"。辅助方法包括将字节转为16进制字符串和将16进制字符串转为字节。
当家滴喵啊
12 0
是阿超
|
17天前
|
搜索推荐 Java
Java排序算法
Java排序算法
是阿超
18 0
是阿超
|
17天前
|
搜索推荐 Java
Java基础(快速排序算法)
Java基础(快速排序算法)
是阿超
23 4

热门文章

最新文章

  • 1
    【MATLAB】GA_ELM神经网络时序预测算法
  • 2
    RPN(Region Proposal Networks)候选区域网络算法解析（附PyTorch代码）
  • 3
    使用Python实现DBSCAN聚类算法
  • 4
    【软件设计师备考 专题 】算法探索：排序、查找、数值计算和字符串处理（一）
  • 5
    Docker Swarm总结+service创建和部署、overlay网络以及Raft算法（2/5）
  • 6
    C++ Algorithm 库 算法秘境探索（Algorithm Wonderland Exploration）
  • 7
    R语言聚类算法的应用实例
  • 8
    经典控制算法——PID算法原理分析及优化
  • 9
    [YOLOv8/YOLOv7/YOLOv5系列算法改进NO.5]改进特征融合网络PANET为BIFPN（更新添加小目标检测层yaml）
  • 10
    【软件设计师备考 专题 】深入理解数据压缩、递归和图的相关算法
  • 1
    【手撕数据结构】二分查找(好多细节)
    16
  • 2
    【数据结构与算法】—— 手撕红黑树
    34
  • 3
    【排序算法】数据结构排序详解
    41
  • 4
    【链式二叉树】数据结构链式二叉树的（万字详解）
    36
  • 5
    【堆】数据结构堆的实现（万字详解）
    50
  • 6
    【树和二叉树】数据结构二叉树和树的概念认识
    23
  • 7
    【双向链表】数据结构双向链表的实现
    20
  • 8
    数据结构——单链表的基本操作
    11
  • 9
    数据结构——排序算法之快速排序
    33
  • 10
    数据结构——二叉树的链式结构
    34

    • 相关课程

    更多
  • Java面试疑难点解析 - 面试技巧及语言基础
  • Java面试疑难点解析 - 系统架构及项目设计
  • Java编程入门
  • Java面向对象编程
  • Java高级编程

    • 相关电子书

    更多
  • Spring Cloud Alibaba - 重新定义 Java Cloud-Native
  • The Reactive Cloud Native Arch
  • JAVA开发手册1.5.0

    • 相关实验场景

    更多
  • 基于ECS搭建Java Web开发环境
  • 使用Aliyun Java Intializr进行项目开发
  • 搭建Java Web开发环境
  • 部署基于Dragonwell的Java运行环境
  • RSA非对称加密算法
    • 下一篇
    阿里云oss简介和使用流程