遍历中序线索二叉树

妖狐艹你老母 2021-07-24 13:34 412阅读 0赞

# 一 需求 #

对下面的中序线索二叉树， 进行遍历。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5ncWl1bWluZw_size_16_color_FFFFFF_t_70][]

# 二 分析 #

因为线索化后， 各个结点指向有变化，因此原来的遍历方式不能使用，这时需要使用新的方式遍历线索化二叉树，各个节点可以通过线型方式遍历，无需使用递归方式，这样也提高了遍历的效率。 遍历的次序应当和中序遍历保持一致。

# 三 代码 #

package com.atguigu.tree.threadedbinarytree;
    
    /**
    * @className: ThreadedBinaryTreeDemo
    * @description: 线索化二叉树
    * @date: 2021/3/20
    * @author: cakin
    */
    public class ThreadedBinaryTreeDemo {
        /**
         * 功能描述：线索化二叉树测试
         *
         * @param args 命令行
         * @author cakin
         * @date 2021/3/20
         */
        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.threadedNodes();
    
            // 当线索化二叉树后，不能再使用原来的遍历方法
            // threadedBinaryTree.infixOrder();
            System.out.println("使用线索化的方式遍历线索化二叉树");
            threadedBinaryTree.threadedList(); // 8, 3, 10, 1, 14, 6
        }
    }
    
    /**
    * @className: ThreadedBinaryTree
    * @description: 实现了线索化功能的二叉树
    * @date: 2021/3/20
    * @author: cakin
    */
    class ThreadedBinaryTree {
        // 根节点
        private HeroNode root;
    
        // 为了实现线索化，定义当前结点的前驱结点的指针
        // 在递归进行线索化时，pre 总是保留前一个结点
        private HeroNode pre = null;
    
        public void setRoot(HeroNode root) {
            this.root = root;
        }
    
        // 重载 threadedNodes
        public void threadedNodes() {
            this.threadedNodes(root);
        }
    
        /**
         * 功能描述：遍历中序线索化二叉树
         *
         * @author cakin
         * @date 2021/3/20
         */
        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();
            }
        }
    
    
        /**
         * 功能描述；中序线索化二叉树算法
         *
         * @param node 就是当前需要线索化的结点
         */
        public void threadedNodes(HeroNode node) {
            // 如果node==null, 不能线索化
            if (node == null) {
                return;
            }
            // 1 先线索化左子树
            threadedNodes(node.getLeft());
            // 2 再线索化当前结点
    
    
            // 处理当前结点的前驱结点
            // 以 8 结点来理解，8 结点的左指针为 null
            if (node.getLeft() == null) {
                // 让当前结点的左指针指向前驱结点
                node.setLeft(pre);
                // 修改当前结点的左指针的类型
                node.setLeftType(1);
            }
    
    
            // 处理后继结点
            // 以 8 结点来理解，当走完上一段代码时，8 结点的左指针为 null,此时是不会走下面代码的，
            // 要等到下一次递归 3 号节点时，才会走下面分支，处理8号节点的后继节点。
            // 也就是说处理8号节点的左右指针是在两次不同的递归中进行了，并且这两次递归是相邻的。
            if (pre != null && pre.getRight() == null) {
                // 让前驱结点的右指针指向当前结点
                pre.setRight(node);
                // 修改前驱结点的右指针类型
                pre.setRightType(1);
            }
            // 每处理完一个结点后，让前驱结点指向当前节点
            pre = node;
    
    
            // 3 最后线索化右子树
            threadedNodes(node.getRight());
        }
    }
    
    /**
    * @className: HeroNode
    * @description: 英雄节点
    * @date: 2021/3/16
    * @author: cakin
    */
    class HeroNode {
        private int no;
        private String name;
        private HeroNode left;  // 默认null
        private HeroNode right;  // 默认null
    
        // 如果leftType 为 0 表示指向的是左子树, 如果 为 1 表示指向前驱结点。
        private int leftType;
        // 如果rightType 为 0 表示指向是右子树, 如果 为 1 表示指向后继结点。
        private int rightType;
    
        public int getLeftType() {
            return leftType;
        }
    
        public void setLeftType(int leftType) {
            this.leftType = leftType;
        }
    
        public int getRightType() {
            return rightType;
        }
    
        public void setRightType(int rightType) {
            this.rightType = rightType;
        }
    
        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 + "]";
        }
    }

# 四 测试 #

使用线索化的方式遍历线索化二叉树
    HeroNode [no=8, name=mary]
    HeroNode [no=3, name=jack]
    HeroNode [no=10, name=king]
    HeroNode [no=1, name=tom]
    HeroNode [no=14, name=dim]
    HeroNode [no=6, name=smith]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5ncWl1bWluZw_size_16_color_FFFFFF_t_70]: /images/20210724/204de900a664415bbe461e606231a31c.png