AI 助理
备案控制台
开发者社区 开发与运维 文章 正文

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

2022-12-08 119
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 前序、中序、后序线索化二叉树，前序、中序、后序线索化二叉树遍历汇总（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
目录
相关文章
java冯坚持
|
1月前
|
存储 人工智能 算法
数据结构与算法细节篇之最短路径问题：Dijkstra和Floyd算法详细描述，java语言实现。
这篇文章详细介绍了Dijkstra和Floyd算法，这两种算法分别用于解决单源和多源最短路径问题，并且提供了Java语言的实现代码。
java冯坚持
70 3
数据结构与算法细节篇之最短路径问题：Dijkstra和Floyd算法详细描述，java语言实现。
ephemerals__
|
17天前
|
C语言
【数据结构】二叉树（c语言）（附源码）
本文介绍了如何使用链式结构实现二叉树的基本功能，包括前序、中序、后序和层序遍历，统计节点个数和树的高度，查找节点，判断是否为完全二叉树，以及销毁二叉树。通过手动创建一棵二叉树，详细讲解了每个功能的实现方法和代码示例，帮助读者深入理解递归和数据结构的应用。
ephemerals__
66 8
小强在此
|
1月前
|
存储 Java
数据结构第二篇【关于java线性表（顺序表）的基本操作】
数据结构第二篇【关于java线性表（顺序表）的基本操作】
小强在此
31 6
java冯坚持
|
1月前
|
存储 算法 关系型数据库
数据结构与算法学习二一：多路查找树、二叉树与B树、2-3树、B+树、B*树。（本章为了解基本知识即可，不做代码学习）
这篇文章主要介绍了多路查找树的基本概念，包括二叉树的局限性、多叉树的优化、B树及其变体（如2-3树、B+树、B*树）的特点和应用，旨在帮助读者理解这些数据结构在文件系统和数据库系统中的重要性和效率。
java冯坚持
22 0
数据结构与算法学习二一：多路查找树、二叉树与B树、2-3树、B+树、B*树。（本章为了解基本知识即可，不做代码学习）
java冯坚持
|
1月前
|
存储 算法 搜索推荐
数据结构与算法学习十七：顺序储存二叉树、线索化二叉树
这篇文章主要介绍了顺序存储二叉树和线索化二叉树的概念、特点、实现方式以及应用场景。
java冯坚持
25 0
数据结构与算法学习十七：顺序储存二叉树、线索化二叉树
GuGuStudy
|
1月前
|
Java
【用Java学习数据结构系列】震惊，二叉树原来是要这么学习的（二）
【用Java学习数据结构系列】震惊，二叉树原来是要这么学习的（二）
GuGuStudy
27 1
阿客不是客
|
1月前
|
存储 算法
探索数据结构：分支的世界之二叉树与堆
探索数据结构：分支的世界之二叉树与堆
阿客不是客
22 0
java冯坚持
|
1月前
|
存储 算法
数据结构与算法学习十六：树的知识、二叉树、二叉树的遍历(前序、中序、后序、层次)、二叉树的查找(前序、中序、后序、层次)、二叉树的删除
这篇文章主要介绍了树和二叉树的基础知识，包括树的存储方式、二叉树的定义、遍历方法（前序、中序、后序、层次遍历），以及二叉树的查找和删除操作。
java冯坚持
25 0
java冯坚持
|
1月前
|
机器学习/深度学习 存储 缓存
数据结构与算法学习十：排序算法介绍、时间频度、时间复杂度、常用时间复杂度介绍
文章主要介绍了排序算法的分类、时间复杂度的概念和计算方法，以及常见的时间复杂度级别，并简单提及了空间复杂度。
java冯坚持
26 1
数据结构与算法学习十：排序算法介绍、时间频度、时间复杂度、常用时间复杂度介绍
java冯坚持
|
1月前
|
搜索推荐 算法
数据结构与算法学习十四：常用排序算法总结和对比
关于常用排序算法的总结和对比，包括稳定性、内排序、外排序、时间复杂度和空间复杂度等术语的解释。
java冯坚持
20 0
数据结构与算法学习十四：常用排序算法总结和对比

热门文章

最新文章

  • 1
    栈的数组实现_JAVA描述《数据结构与算法分析》
  • 2
    数据结构与算法：链表（源码）！
  • 3
    JS数据结构与算法-链表
  • 4
    20120919-二叉树 数据结构《数据结构与算法分析》
  • 5
    数据结构与算法--链表
  • 6
    Java数据结构与算法分析（八）二叉查找树（BST）
  • 7
    「数据结构与算法Javascript描述」队列
  • 8
    【数据结构与算法】单向链表的实现（下）
  • 9
    数据结构与算法__04--二叉树后序线索化与后序线索化遍历（Java语言版）
  • 10
    每周一练 之 数据结构与算法（LinkedList）
  • 1
    `geopandas`是一个开源项目，它为Python提供了地理空间数据处理的能力。它基于`pandas`库，并扩展了其对地理空间数据（如点、线、多边形等）的支持。`GeoDataFrame`是`geopandas`中的核心数据结构，它类似于`pandas`的`DataFrame`，但包含了一个额外的地理列（通常是`geometry`列），用于存储地理空间数据。
    70
  • 2
    “解锁Python高级数据结构新姿势：图的表示与遍历，让你的算法思维跃升新高度
    44
  • 3
    Redis数据结构—跳跃表 skiplist 实现源码分析
    65
  • 4
    逆袭之路！用 Python 玩转图的 DFS 与 BFS，让数据结构难题无处遁形
    65
  • 5
    Python中的列表（List）和元组（Tuple）是两种重要的数据结构
    56
  • 6
    【数据结构OJ题】链表分割
    32
  • 7
    【数据结构常见七大排序（三）上】—交换排序篇【冒泡排序】And【快速排序】
    46
  • 8
    【数据结构常见七大排序（二）】—选择排序篇【直接选择排序】And【堆排序】
    34
  • 9
    【数据结构常见七大排序（一）】—插入排序篇【直接插入排序】And【希尔排序】
    46
  • 10
    【数据结构OJ题】链表的回文结构
    39

    • 相关课程

    更多
  • Java Web项目实战 - 图书商城
  • Java面试疑难点解析 - 面试技巧及语言基础
  • Java面试疑难点解析 - Java Web开发
  • Java面试疑难点解析 - 系统架构及项目设计
  • Java编程入门
  • Java面向对象编程

    • 相关电子书

    更多
  • “大数据+算法”助力B2B未来商业
  • 数据+算法定义新世界
  • Apache Flink 流式应用中状态的数据结构定义升级

    • 相关实验场景

    更多
  • 使用Swing算法实现商品推荐
  • 阿里云平台上进行Java程序的编译与运行
  • RSA密码算法设计与实现
  • 欧拉图的构造性证明与算法实现
  • 使用Java面向对象编写网络通信程序应用
  • 手动部署Java Web环境（Alibaba Cloud Linux 2）
    • 下一篇
    无影云桌面