二叉树的不同形式：顺序存储二叉树 & 线索化二叉树

﹏ヽ暗。殇╰゛Y 2023-07-17 15:48 6阅读 0赞

# 顺序存储二叉树 #

从数据存储来看，数组存储方式和树的存储方式可以相互转换，即数组可以转换成树，树也可以转换成数组，看右面的示意图。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NneXVhbnNoaQ_size_16_color_FFFFFF_t_70]

顺序存储二叉树的特点:

1.  顺序二叉树通常只考虑完全二叉树
2.  第n个元素的左子节点为 2 \* n + 1
3.  第n个元素的右子节点为 2 \* n + 2
4.  第n个元素的父节点为 (n-1) / 2
5.  n : 表示二叉树中的第几个元素(按0开始编号如图所示)

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NneXVhbnNoaQ_size_16_color_FFFFFF_t_70 1]

# 线索化二叉树 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NneXVhbnNoaQ_size_16_color_FFFFFF_t_70 2]

当我们对上面的二叉树进行中序遍历时，数列为 \{8, 3, 10, 1, 6, 14 \}，但是 6, 8, 10, 14 这几个节点的 左右指针，并没有完全的利用上.

## 基本介绍 ##

1.  n个结点的二叉链表中含有n+1 【公式 2n-(n-1)=n+1】 个空指针域。利用二叉链表中的空指针域，存放指向该结点在某种遍历次序下的前驱和后继结点的指针（这种附加的指针称为"线索"）
2.  这种加上了线索的二叉链表称为线索链表，相应的二叉树称为线索二叉树(Threaded BinaryTree)。根据线索性质的不同，线索二叉树可分为前序线索二叉树、中序线索二叉树和后序线索二叉树三种

## 实现步骤 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NneXVhbnNoaQ_size_16_color_FFFFFF_t_70 3]

上图二叉树中序遍历的结果：\{8, 3, 10, 1, 14, 6\}  
说明: 当线索化二叉树后，Node节点的 属性 left 和 right ，有如下情况:

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

# 实现代码 #

## 顺序存错二叉树 ##

package com.hong.tree;
    
    /**
     * 顺序二叉树通常只考虑完全二叉树
     * 第n个元素的左子节点为  2 * n + 1
     * 第n个元素的右子节点为  2 * n + 2
     * 第n个元素的父节点为  (n-1) / 2
     */
    public class SequentialBinaryTree { 
    
        private Node root;
        private int[] arr;
    
        public SequentialBinaryTree(int[] arr){ 
            this.arr = arr;
            root = new Node(arr[0]);
            build(root, 0);
        }
    
        /**
         * 递归创建顺序存储二叉树
         * @param parent 当前节点
         * @param index 当前节点对应数组的下标
         */
        private void build(Node parent, int index){ 
            if (index >= arr.length){ 
                return;
            }
    
            // 第n个元素的左子节点为  2 * n + 1
            // 第n个元素的右子节点为  2 * n + 2
            int left = 2 * index + 1;
            int right = 2 * index + 2;
    
            if (left >= arr.length){ 
                return;
            } else{ 
                parent.left = new Node(arr[left]);
            }
    
            if (right >= arr.length){ 
                return;
            } else{ 
                parent.right = new Node(arr[right]);
            }
    
            build(parent.left, left);
            build(parent.right, right);
        }
    
        /**
         * 前序遍历：先打印父节点，再打印左子节点，最后打印右子节点
         * 需要基于创建二叉树才能执行
         * @param root
         */
        public void preOrder(Node root){ 
            System.out.println(root.val);
            if (root.left != null){ 
                preOrder(root.left);
            }
            if (root.right != null){ 
                preOrder(root.right);
            }
        }
    
        /**
         * 前序遍历：无需基于二叉树的建立，只需要通过数组即可实现遍历
         * @param index
         */
        public void preOrder(int index){ 
            System.out.println(arr[index]);
            int left = 2 * index + 1;
            int right = 2 * index + 2;
            if (left < arr.length){ 
                preOrder(left);
            }
            if (right < arr.length){ 
                preOrder(right);
            }
    
        }
    
        public static void main(String[] args) { 
            int[] arr = { 1,2,3,4,5,6,7};
            SequentialBinaryTree tree = new SequentialBinaryTree(arr);
    //        tree.preOrder(tree.root);
            tree.preOrder(0);
        }
    
    
        public class Node{ 
            public int val;
            public Node left = null;
            public Node right = null;
    
            public Node(int val){ 
                this.val = val;
            }
        }
    }

## 线索化二叉树 ##

package com.hong.tree;
    
    
    /**
     * 以顺序二叉树为例，对应中序遍历，将其线索化
     */
    public class ThreadTree { 
    
    
        Node root;
        Node pre = null; // 用于记录前驱节点
    
        public ThreadTree(int[] arr){ 
            root = new Node(arr[0]);
            build(root, 0, arr);
        }
    
        /**
         * 将二叉树进行中序线索化
         * @param node
         */
        public void buildThread(Node node){ 
            if (node.left != null){ 
                buildThread(node.left);
            }
            // 将当前叶子节点的左子树链接为前驱节点
            if (pre != null && node.left == null){ 
                node.left = pre;
                node.leftThread = true;
            }
            // 将前驱叶子节点的右子树链接为当前节点
            if (pre != null){ 
                if (pre.right == null){ 
                    pre.right = node;
                    pre.rightThread = true;
                }
            }
            pre = node;
    
            if (node.right != null){ 
                buildThread(node.right);
            }
        }
    
        /**
         * 递归创建顺序存储二叉树
         * @param parent 当前节点
         * @param index 当前节点对应数组的下标
         */
        private void build(Node parent, int index, int[] arr){ 
            if (index >= arr.length){ 
                return;
            }
    
            // 第n个元素的左子节点为  2 * n + 1
            // 第n个元素的右子节点为  2 * n + 2
            int left = 2 * index + 1;
            int right = 2 * index + 2;
    
            if (left >= arr.length){ 
                return;
            } else{ 
                parent.left = new Node(arr[left]);
            }
    
            if (right >= arr.length){ 
                return;
            } else{ 
                parent.right = new Node(arr[right]);
            }
    
            build(parent.left, left, arr);
            build(parent.right, right, arr);
        }
    
        /**
         * 将中序线索化二叉树进行中序遍历
         */
        public void show(){ 
            Node left = root;
            while (left.left != null){ 
                left = left.left;
            }
            while (true){ 
                System.out.println(left.val);
                left = left.right;
                if (left == root){ 
                    System.out.println(left.val);
                    break;
                }
            }
    
            Node right = root.right;
            while (right.left != root && !right.leftThread){ 
                right = right.left;
            }
            while (true){ 
                System.out.println(right.val);
                right = right.right;
                if (right.right == null){ 
                    System.out.println(right.val);
                    break;
                }
            }
    
        }
    
        public class Node{ 
            public int val;
            public Node left = null;
            public Node right = null;
            public boolean leftThread; // 左子树是否进行线索化
            public boolean rightThread;
    
            public Node(int val){ 
                this.val = val;
            }
    
    
        }
    
        public static void main(String[] args) { 
            int[] arr = { 1, 3, 6, 8, 10, 14};
            ThreadTree tree = new ThreadTree(arr);
            tree.buildThread(tree.root);
            System.out.println();
            tree.show();
        }
    }

欢迎关注同名公众号：“我就算饿死也不做程序员”。  
交个朋友，一起交流，一起学习，一起进步。![在这里插入图片描述][2020043011495060.jpg]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NneXVhbnNoaQ_size_16_color_FFFFFF_t_70]: /images/20230528/716bfbded1fa4a23966e7e84cb657490.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NneXVhbnNoaQ_size_16_color_FFFFFF_t_70 1]: /images/20230528/b160fe4a861f4d3b9f6358e5e0a32e2f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NneXVhbnNoaQ_size_16_color_FFFFFF_t_70 2]: /images/20230528/3162ee56eb6846b4a66fd47825c642e9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NneXVhbnNoaQ_size_16_color_FFFFFF_t_70 3]: /images/20230528/ed68fa51521f4f4490e36fef43d125d5.png
[2020043011495060.jpg]: /images/20230528/e2552300a0d14bdda40e663786cd2a60.png