前序、中序、后序线索化二叉树

梦里梦外; 2022-12-29 04:54 139阅读 0赞

### **为什么要线索化二叉树** ###

先看一个问题

将数列 \{1, 3, 6, 8, 10, 14  \} 构建成一颗二叉树.  n+1=7

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1Nzk2MjA4_size_16_color_FFFFFF_t_70][]

问题分析:

1、当我们对上面的二叉树进行中序遍历时，数列为 \{8, 3, 10, 1, 6, 14 \}

2、但是 6, 8, 10, 14 这几个节点的 左右指针，并没有完全的利用上.

3、如果我们希望充分的利用 各个节点的左右指针， 让各个节点可以指向自己的前后节点,怎么办?

4、解决方案-线索二叉树

### 线索化二叉树基本介绍 ###

1、n个结点的二叉链表中含有n+1  【公式 2n-(n-1)=n+1】 个空指针域。利用二叉链表中的空指针域，存放指向该结点在某种遍历次序下的前驱和后继结点的指针（这种附加的指针称为"线索"）

2、这种加上了线索的二叉链表称为线索链表，相应的二叉树称为线索二叉树(Threaded BinaryTree)。根据线索性质的不同，线索二叉树可分为前序线索二叉树、中序线索二叉树和后序线索二叉树三种

3、一个结点的前一个结点，称为前驱结点 一个结点的后一个结点，称为后继结点

创建节点

class HeroNode {
        private int no;
        private String name;
        private HeroNode left;
        private HeroNode right;
        private HeroNode parent;
        //true 表示是线索化节点
        //false 表示不是线索化节点
        private boolean ThreadedLeft = false;
        private boolean ThreadedRight = false;
    
        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;
        }
    
        public HeroNode getParent() {
            return parent;
        }
    
        public void setParent(HeroNode parent) {
            this.parent = parent;
        }
    
        public boolean isThreadedLeft() {
            return ThreadedLeft;
        }
    
        public void setThreadedLeft(boolean threadedLeft) {
            ThreadedLeft = threadedLeft;
        }
    
        public boolean isThreadedRight() {
            return ThreadedRight;
        }
    
        public void setThreadedRight(boolean threadedRight) {
            ThreadedRight = threadedRight;
        }
    
        @Override
        public String toString() {
            return "HeroNode{" +
                    "no=" + no +
                    ", name='" + name + '\'' +
                    '}';
        }
    }

### 中序线索化二叉树 ###

应用案例说明：将下面的二叉树，进行中序线索二叉树。中序遍历的数列为 \{8, 3, 10, 1, 14, 6\}

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1Nzk2MjA4_size_16_color_FFFFFF_t_70 1][]

说明: 当线索化二叉树后，Node节点的 属性 left 和 right ，有如下情况:

1、left 指向的是左子树，也可能是指向的前驱节点. 比如 ① 节点 left 指向的左子树, 而 ⑩ 节点的 left 指向的就是前驱节点.

2、right指向的是右子树，也可能是指向后继节点，比如 ① 节点right 指向的是右子树，而⑩ 节点的right 指向的是后继节点.

中序线索化的过程

1、按照中序遍历的顺序，第一个遍历到的节点是8，8节点的左指针为空，所以令8节点的左指针指向它的前驱节点也就是null

pre和node后移

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1Nzk2MjA4_size_16_color_FFFFFF_t_70 2][]

2、继续中序遍历到3节点，它的左指针不为null

pre为8节点，它的右指针为空，所以让他的右指针指向它的后继节点，也就是3，

pre和node后移

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1Nzk2MjA4_size_16_color_FFFFFF_t_70 3][]

3、继续遍历到10节点，它的左指针为空，所以指向它的前驱节点

pre为3节点它的右指针不为空

pre和node后移

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1Nzk2MjA4_size_16_color_FFFFFF_t_70 4][]

4、继续遍历到1节点，它的左指针不为空

pre节点为10节点，它的右指针为空，所以指向后继节点1

pre和node后移

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1Nzk2MjA4_size_16_color_FFFFFF_t_70 5][]

5、继续遍历到14节点，因为它的左指针不为空，所以指向它的前驱节点1

pre节点为1节点，它的右指针不为空

pre和node后移

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1Nzk2MjA4_size_16_color_FFFFFF_t_70 6][]

6、继续遍历到6节点，它的左指针为空

pre节点为14节点，因为它的右指针为空，所以指向它的后继节点6

pre和node后移

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1Nzk2MjA4_size_16_color_FFFFFF_t_70 7][]

以上就是一个中序线索化节点的过程，下面请看代码实现

private void infixThreadedNode(HeroNode node) {
            if (node == null) {
                return;
            }
            //线索化左节点
            infixThreadedNode(node.getLeft());
            //线索化当前节点
            if (node.getLeft() == null) {
                node.setLeft(pre);
                node.setThreadedLeft(true);
            }
            if (pre != null && pre.getRight() == null) {
                pre.setRight(node);
                pre.setThreadedRight(true);
            }
            pre = node;
            //线索化右节点
            infixThreadedNode(node.getRight());
        }

中序线索化遍历

public void infixThreadedList() {
            HeroNode node = root;
            while (node != null) {
                while (!node.isThreadedLeft()) {
                    node = node.getLeft();
                }
                System.out.println(node);
                while (node.isThreadedRight()) {
                    node = node.getRight();
                    System.out.println(node);
                }
                node = node.getRight();
            }
        }

### 前序线索化二叉树 ###

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1Nzk2MjA4_size_16_color_FFFFFF_t_70 8][]

代码实现

private void preThreadedNode(HeroNode node) {
            //线索化当前节点
            if (node == null)
                return;
            if (node.getLeft() == null) {
                node.setLeft(pre);
                node.setThreadedLeft(true);
            }
            if (pre != null && pre.getRight() == null) {
                pre.setRight(node);
                pre.setThreadedRight(true);
            }
            pre = node;
            //线索化左节点
            if (!node.isThreadedLeft()) {
                preThreadedNode(node.getLeft());
            }
            //线索化右节点
            if (!node.isThreadedRight()) {
                preThreadedNode(node.getRight());
            }
        }

前序线索化遍历

public void preThreadedList() {
            HeroNode node = root;
            while (node != null) {
                if (!node.isThreadedLeft()) {
                    System.out.println(node);
                    node = node.getLeft();
                }
                System.out.println(node);
                node = node.getRight();
            }
        }

### 后序线索化二叉树 ###

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1Nzk2MjA4_size_16_color_FFFFFF_t_70 9][]

代码实现

private void postThreadedNode(HeroNode node) {
            if (node == null)
                return;
            postThreadedNode(node.getLeft());
            postThreadedNode(node.getRight());
            if (node.getLeft() == null) {
                node.setLeft(pre);
                node.setThreadedLeft(true);
            }
            if (pre != null && pre.getRight() == null) {
                pre.setRight(node);
                pre.setThreadedRight(true);
            }
            pre = node;
        }

后序线索化遍历

public void postThreadedList() {
            HeroNode node = root;
            while (node != null && !node.isThreadedLeft()) {
                node = node.getLeft();
            }
            pre = null;
            while (node != null) {
                if (node.isThreadedRight()) {
                    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.isThreadedLeft()) {
                            node = node.getLeft();
                        }
                    }
                }
            }
        }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1Nzk2MjA4_size_16_color_FFFFFF_t_70]: /images/20221120/3f2b979250214e2b8a1f9c337c4b55aa.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1Nzk2MjA4_size_16_color_FFFFFF_t_70 1]: /images/20221120/fd07945da4e744daad871df082c088e2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1Nzk2MjA4_size_16_color_FFFFFF_t_70 2]: /images/20221120/47c95871aa004b44acaaddda77e21de3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1Nzk2MjA4_size_16_color_FFFFFF_t_70 3]: /images/20221120/f66a669de0f64523934ef1cb31f5ef87.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1Nzk2MjA4_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20201220150813757.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1Nzk2MjA4,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1Nzk2MjA4_size_16_color_FFFFFF_t_70 5]: https://img-blog.csdnimg.cn/20201220150953436.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1Nzk2MjA4,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1Nzk2MjA4_size_16_color_FFFFFF_t_70 6]: https://img-blog.csdnimg.cn/20201220151309483.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1Nzk2MjA4,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1Nzk2MjA4_size_16_color_FFFFFF_t_70 7]: https://img-blog.csdnimg.cn/20201220151436721.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1Nzk2MjA4,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1Nzk2MjA4_size_16_color_FFFFFF_t_70 8]: https://img-blog.csdnimg.cn/20201220152153498.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1Nzk2MjA4,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1Nzk2MjA4_size_16_color_FFFFFF_t_70 9]: https://img-blog.csdnimg.cn/20201220152523412.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1Nzk2MjA4,size_16,color_FFFFFF,t_70