顺序存储二叉树 线索化二叉树

顺序存储二叉树 线索化二叉树

顺序存储二叉树

基本概念:

从数据存储来看,数组存储方式和树的存储方式可以相互转换,即数组可以转换成树,树也可以转换成数组

顺序存储二叉树 线索化二叉树
要求:

  • 右图的二叉树的结点,要求以数组的方式来存放 arr : [1, 2, 3, 4, 5, 6, 7]
  • 要求在遍历数组 arr 时,仍然可以以前序遍历,中序遍历和后序遍历的方式完成结点的遍历

顺序存储二叉树的特点:

  • 顺序二叉树通常只考虑完全二叉树
  • arr[n] 的左子节点为 arr[2*n + 1]
  • arr[n] 的右子节点为 arr[2*n + 2]
  • arr[n] 的父节点为 arr[ (n-1) /2 ]
  • n : 表示二叉树中的第n个元素,也就是数组索引

说明:八大排序算法中的堆排序,就会使用到顺序存储二叉树

代码实现:

需求: 给你一个数组 {1,2,3,4,5,6,7},要求以二叉树前序,中序 后续 三种方式进行遍历。

package com.atguigu.tree;

/**
 * @ClassName ArrBinaryTreeDemo
 * @Author Jeri
 * @Date 2022-02-22 21:38
 * @Description 顺序存储二叉树
 */


//编写 ArrBinaryTree 实现顺序存储二叉树遍历
class ArrBinaryTree{
    private int[] arr;//存储数据的数组

    public ArrBinaryTree(int[] arr) {
        this.arr = arr;
    }

    //编写顺序二叉树前序遍历
    public void preOrder(int index){
        //如果数组为空 或者 arr.length == 0 无法遍历
        if(arr == null || arr.length == 0){
            System.out.println("数组为空 无法完成遍历");
            return;
        }

        //输出当前元素
        System.out.printf(arr[index] + " ");
        //向左递归
        if((2*index + 1) < arr.length){
            preOrder(2*index + 1);
        }

        //向右递归
        if((2*index + 2) < arr.length){
            preOrder(2*index + 2);
        }
    }

    //实现重载方法 默认前序遍历从0开始
    public void preOrder(){
        this.preOrder(0);
    }

    //编写顺序二叉树中序遍历
    public void infixOrder(int index){
        //如果数组为空 或者 arr.length == 0 无法遍历
        if(arr == null || arr.length == 0){
            System.out.println("数组为空 无法完成遍历");
            return;
        }

        //向左递归
        if((2*index + 1) < arr.length){
            infixOrder(2*index + 1);
        }

        //输出当前元素
        System.out.printf(arr[index] + " ");

        //向右递归
        if((2*index + 2) < arr.length){
            infixOrder(2*index + 2);
        }
    }

    //实现重载方法 默认前序遍历从0开始
    public void infixOrder(){
        this.infixOrder(0);
    }

    //编写顺序二叉树后序遍历
    public void postOrder(int index){
        //如果数组为空 或者 arr.length == 0 无法遍历
        if(arr == null || arr.length == 0){
            System.out.println("数组为空 无法完成遍历");
            return;
        }
        //向左递归
        if((2*index + 1) < arr.length){
            postOrder(2*index + 1);
        }

        //向右递归
        if((2*index + 2) < arr.length){
            postOrder(2*index + 2);
        }

        //输出当前元素
        System.out.printf(arr[index] + " ");
    }

    //实现重载方法 默认前序遍历从0开始
    public void postOrder(){
        this.postOrder(0);
    }


}
public class ArrBinaryTreeDemo {
    public static void main(String[] args) {
        int[] array = new int[]{1, 2, 3, 4, 5, 6, 7};
        //创建 ArrBinaryTree 对象
        ArrBinaryTree abt = new ArrBinaryTree(array);

		System.out.println("原始数组;------");
        System.out.println(Arrays.toString(array));
        System.out.println();
 
        System.out.println("前序遍历结果:------");
        abt.preOrder();
        System.out.println();

        System.out.println("中序遍历结果:------");
        abt.infixOrder();
        System.out.println();

        System.out.println("后序遍历结果:------");
        abt.postOrder();
        System.out.println();
    }
}

原始数组;------
[1, 2, 3, 4, 5, 6, 7]

前序遍历结果:------
1 2 4 5 3 6 7 
中序遍历结果:------
4 2 5 1 6 3 7 
后序遍历结果:------
4 5 2 6 7 3 1 

线索化二叉树

提出问题:

将数列 {1, 3, 6, 8, 10, 14 } 构建成一颗二叉树

顺序存储二叉树 线索化二叉树
问题分析:

  • 当我们对上面的二叉树进行中序遍历时,数列为 {8, 3, 10, 1, 14,6 }
  • 但是 6, 8, 10, 14 这几个节点的 左右指针,并没有完全的利用上
  • 如果我们希望充分的利用 各个节点的左右指针, 让各个节点可以指向自己的前后节点
  • 解决方案:线索二叉树

基本介绍:

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

中序线索化二叉树的构建

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

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

  • left 指向的是左子树,也可能是指向的前驱节点. 比如 1 节点 left 指向的左子树, 而 10 节点的 left 指向的就是前驱节点
  • right 指向的是右子树,也可能是指向后继节点,比如 1 节点 right 指向的是右子树,而 10 节点的 right 指向的是后继节点.
package com.atguigu.tree;

/**
 * @ClassName ThreadedBinaryTreeDemo
 * @Author Jeri
 * @Date 2022-02-23 10:25
 * @Description 线索二叉树 分为前序 中序 后序
 */


//创建节点类
class Node{
    private int no;
    private Node left;//默认为 null
    private Node right;//默认为 null

    //取值说明:leftType/rightType  0:左右子树  1:前驱 后继节点
    private int leftType;
    private int rightType;

    public Node(int no) {
        this.no = no;
    }

    public int getNo() {
        return no;
    }

    public void setNo(int no) {
        this.no = no;
    }

    public Node getLeft() {
        return left;
    }

    public void setLeft(Node left) {
        this.left = left;
    }

    public Node getRight() {
        return right;
    }

    public void setRight(Node right) {
        this.right = right;
    }

    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;
    }

    @Override
    public String toString() {
        return "Node{" +
                "no=" + no +
                '}';
    }
}

//定义 ThreadedBinaryTree 实现 线索化二叉树
class ThreadedBinaryTree{
    private Node root;

    public void setRoot(Node node){
        this.root = node;
    }

    public Node getRoot() {
        return root;
    }

    //实现线索化 创建临时节点 指向当前节点的前驱节点
    private Node pre = null;


    /*
     * @Description 中序线索化二叉树
     * 中序遍历的数列为 {8, 3, 10, 1, 14, 6}
     * 思路:先找到 node = 8 pre = null,然后按照顺序逐次后移
     * @Date 2022/2/23 10:36
     * @param node 开始节点(根节点)
     */
    public void infixThreadedNodes(Node node){

        //如果 node ==null 不能线索化
        if(node == null) { return ;}

        //线索化左子树
        //使用递归找到 node = 8 这个节点 顺次后移处理
        infixThreadedNodes(node.getLeft());

        //线索化当前节点
        //1.处理前驱节点
        if(node.getLeft() == null){
            //当前节点 左指针为空 使其指向 前驱节点
            node.setLeft(pre);
            //修改其左指针的类型
            node.setLeftType(1);
        }
        //2.处理后继节点
        //当前 node 节点不知道其后继节点
        //但是根据双指针移动策略 在下一次移动中 pre -> node node->node.next
        //所以我们在下一轮 来处理当前节点的后继
        if(pre != null && pre.getRight() == null){
            //设置上一轮节点的后继节点
            pre.setRight(node);
            //修改上一轮节点的指针类型
            pre.setRightType(1);
        }

        //处理节点后 使得 pre 后移
        pre = node;

        //node的移动是根据递归进行 无需手动操作

        //线索化右子树
        infixThreadedNodes(node.getRight());
    }

}

public class ThreadedBinaryTreeDemo {
    public static void main(String[] args) {
        //创建节点对象
        Node node1 = new Node(1);
        Node node2 = new Node(3);
        Node node3 = new Node(6);
        Node node4 = new Node(8);
        Node node5 = new Node(10);
        Node node6 = new Node(14);

        //手动创建二叉树
        node1.setLeft(node2);
        node1.setRight(node3);
        node2.setLeft(node4);
        node2.setRight(node5);
        node3.setLeft(node6);

        //创建线索树对象
        ThreadedBinaryTree tbt = new ThreadedBinaryTree();
        tbt.setRoot(node1);

        //进行中序线索化
        tbt.infixThreadedNodes(tbt.getRoot());

        //测试结果
        System.out.println("测试中序线索化二叉树:------");


        Node leftNode = node5.getLeft();
        Node rightNode = node5.getRight();
        System.out.println("10号结点的前驱结点是 = " + leftNode);// 3
        System.out.println("10号结点的后继结点是 = " + rightNode);// 1
    }
}
测试中序线索化二叉树:------
10号结点的前驱结点是 = Node{no=3}
10号结点的后继结点是 = Node{no=1}

中序线索化二叉树的中序遍历

说明:对前面的中序线索化的二叉树, 进行遍历

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

顺序存储二叉树 线索化二叉树思路分析: 顺着 左线型0 找到节点 8 ,输出节点 8 ,然后顺着 右线性 进行进行查找 右线性 = 1,存在后继节点,node = node.getRight() 继续判断 右线型;否则 右线性 != 1,node 后移 node.getRight(),从头继续

ThreadedBinaryTree 类中增加方法

/*
     * @Description 中序线索化二叉树的中序遍历 
     * @Date 2022/2/23 11:34
     */
    public void infixThreadedNodeList(){
        //定义一个临时变量 存储便利的节点 从 root 开始
        Node node = root;

        while (node != null){
            //顺着左线型 找到 节点8
            while (node.getLeftType() == 0){
                node = node.getLeft();
            }
            //退出循环时 node -> 8

            //打印当前节点
            System.out.println(node);

            //顺着右线型进行查找
            //1. 右线型 == 1 node -> node.next 输出
            //2. 右线型 == 0 node -> node.getRight()
            while (node.getRightType() == 1){
                //当前节点存在后继节点 node 后移
                node = node.getRight();
                System.out.println(node);
            }

            //否则
            node = node.getRight();
        }
    }

ThreadedBinaryTreeDemo类中增加测试代码

        System.out.println("测试中序线索化二叉树的中序遍历:------");
        tbt.infixThreadedNodeList();
测试中序线索化二叉树的中序遍历:------
Node{no=8}
Node{no=3}
Node{no=10}
Node{no=1}
Node{no=14}
Node{no=6}

前序线索化二叉树的构建

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

顺序存储二叉树 线索化二叉树

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

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

ThreadedBinaryTree 类中 增加方法

/*
     * @Description 前序线索化二叉树的构建
     * 前序遍历的数列为 {1,3,8,10,6,14}
     * 思路:先找到 node = 1 pre = null,然后按照顺序逐次后移
     * @Date 2022/2/23 15:53
     */
    public void preThreadedNodes(Node node){
        //如果 node ==null 不能线索化
        if(node == null) { return ;}

        //处理当前节点
        //1.处理前驱节点
        if(node.getLeft() == null){
            //当前节点 左指针为空 使其指向 前驱节点
            node.setLeft(pre);
            //修改其左指针的类型
            node.setLeftType(1);
        }

        //2.处理后继节点
        //当前 node 节点不知道其后继节点
        //但是根据双指针移动策略 在下一次移动中 pre -> node node->node.next
        //所以我们在下一轮 来处理当前节点的后继
        if(pre != null && pre.getRight() == null){
            //设置上一轮节点的后继节点
            pre.setRight(node);
            //修改上一轮节点的指针类型
            pre.setRightType(1);
        }

        //处理节点后 使得 pre 后移
        pre = node;

        //node的移动是根据递归进行 无需手动操作

        //排除 node.getLeft() = pre  的情况 避免无限循环
        if(node.getLeftType() == 0){
            //线索化左子树
            preThreadedNodes(node.getLeft());
        }

        //线索化右子树
        if(node.getRightType() == 0) {
            preThreadedNodes(node.getRight());
        }

    }

ThreadedBinaryTreeDemo 类中增加测试代码

        System.out.println();

        //进行前序线索化
        tbt.preThreadedNodes(tbt.getRoot());
        Node leftNode = node5.getLeft();
        Node rightNode = node5.getRight();
        System.out.println("10号结点的前驱结点是 = " + leftNode);// 8
        System.out.println("10号结点的后继结点是 = " + rightNode);// 6

        System.out.println("前序线索化结束");
10号结点的前驱结点是 = Node{no=8}
10号结点的后继结点是 = Node{no=6}
前序线索化结束

debug下发现 节点 14 的右指针 指向 null 线型为0 与计划不是很符合

前序线索化二叉树的前序遍历

ThreadedBinaryTree类中增加方法

/*
     * @Description 前序线索化二叉树的前序遍历
     * 前序遍历的数列为 {1,3,8,10,6,14}
     * 思路:先找到 node = 1 pre = null,然后按照顺序逐次后移
     * @Date 2022/2/23 15:53
     */
    public void preThreadedNodesList(){
        //定义临时变量 存储遍历的节点 从root开始
        Node node = root;

        while (node != null){

            //打印当前结点
            System.out.println(node);

            //找到最左边的节点
            while (node.getLeftType()==0){
                node=node.getLeft();
                System.out.println(node);
            }

            if (node.getRightType()==1){
                node=node.getRight();
            }else if (node.getRight()==null){
                //线索化前序遍历的最后一个结点的right一定为null,所以遍历完毕 退出循环
                break;
            }
        }

    }

ThreadedBinaryTreeDemo类中增加测试方法

        System.out.println();
        System.out.println("测试前序线索化二叉树的前序遍历:------");
        tbt.preThreadedNodesList();
测试前序线索化二叉树的前序遍历:------
Node{no=1}
Node{no=3}
Node{no=8}
Node{no=10}
Node{no=6}
Node{no=14}

后序线索化二叉树的构建

应用案例说明:将下面的二叉树,进行后序线索二叉树。后序遍历的数列为 {8,10,3,14,6,1}
顺序存储二叉树 线索化二叉树

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

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

ThreadedBinaryTree 类中 增加方法

/*
     * @Description 后序线索化二叉树的构建
     * 后序遍历的数列为 {8, 3, 10, 1, 14, 6}
     * 思路:先找到 node = 8 pre = null,然后按照顺序逐次后移
     * @Date 2022/2/23 10:36
     * @param node 开始节点(根节点)
     */
    public void postThreadedNodes(Node node){
        //如果 node 为空 不能进行线索化
        if(node == null) { return; }

        //先线索化左子树
        postThreadedNodes(node.getLeft());

        //在线索化右子树
        postThreadedNodes(node.getRight());

        //当前节点
        //1.处理前驱节点
        if(node.getLeft() == null){
            //当前节点 左指针为空 使其指向 前驱节点
            node.setLeft(pre);
            //修改其左指针的类型
            node.setLeftType(1);
        }

        //2.处理后继节点
        //当前 node 节点不知道其后继节点
        //但是根据双指针移动策略 在下一次移动中 pre -> node node->node.next
        //所以我们在下一轮 来处理当前节点的后继
        if(pre != null && pre.getRight() == null){
            //设置上一轮节点的后继节点
            pre.setRight(node);
            //修改上一轮节点的指针类型
            pre.setRightType(1);
        }

        //处理节点后 使得 pre 后移
        pre = node;

        //node的移动是根据递归进行 无需手动操作
    }

ThreadedBinaryTreeDemo类中增加测试代码

        //进行后序线索化
        tbt.postThreadedNodes(tbt.getRoot());
        Node leftNode = node5.getLeft();
        Node rightNode = node5.getRight();
        System.out.println("10号结点的前驱结点是 = " + leftNode);// 8
        System.out.println("10号结点的后继结点是 = " + rightNode);// 6

        System.out.println("后序线索化结束");
10号结点的前驱结点是 = Node{no=8}
10号结点的后继结点是 = Node{no=3}
后序线索化结束

后序线索化二叉树的后序遍历

注:参考其他人 自己没有写出来

参考文献:后序线索化二叉树(Java版)

ThreadedBinaryTree类中增加方法

Node类中增加属性

    private Node parent;//表示父节点 后续线索化要用
	public Node getParent() {
        return parent;
    }

    public void setParent(Node parent) {
        this.parent = parent;
    }
/*
     * @Description 后序线索化二叉树
     * 思路:后序遍历开始节点是最左节点
     * @Date 2022/2/23 19:13
     */
    public void postThreadedNodesList(){

        //1.找到后序遍历最开始的节点
        Node node = root;
        while (node != null && node.getLeftType() == 0){
            node = node.getLeft();
        }

        //定义父节点
        Node 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){
                        break;
                    }

                    preNode = node;
                    node = node.getParent();
                }else{
                    //如果从左节点的进入  则找到有子树的最左节点

                    //排除该节点为 root 节点且右子树为空的情况
                    if(node == root && node.getRight() == null){
                        System.out.println(node);
                        return;
                    }else{
                        node = node.getRight();
                        while (node != null && node.getLeftType() == 0){
                            node = node.getLeft();
                        }
                    }
                }
            }
        }
    }

ThreadedBinaryTreeDemo类中增加测试代码

		node2.setParent(node1);
        node3.setParent(node2);
        node4.setParent(node2);
        node5.setParent(node2);
        node6.setParent(node3);
		//进行后序线索化
        tbt.postThreadedNodes(tbt.getRoot());
        System.out.println();
        System.out.println("测试后序线索化二叉树的后序遍历:------");
        tbt.postThreadedNodesList();
测试后序线索化二叉树的后序遍历:------
Node{no=8}
Node{no=10}
Node{no=3}
Node{no=14}
Node{no=6}
Node{no=1}

小结遍历

参考文献:后序线索化二叉树(Java版)

  • 前序线索化二叉树遍历:先沿着左子树处理,找到子树的最左子节点,然后处理right指针指向,以此类推,直到节点的right指针为空,说明是最后一个,遍历完成。
  • 中序线索化二叉树遍历:左根右,因此第一个节点一定是最左子节点,先找到最左子节点,依次沿着right指针指向进行处理(无论是指向子节点还是指向后继节点),直到节点的right指针为空,说明是最后一个,遍历完成。
  • 后序遍历线索化二叉树最为复杂,通用的二叉树数节点存储结构不能够满足后序线索化,因此我们扩展了节点的数据结构,增加了父节点的指针。后序的遍历顺序是:左右根,先找到最左子节点,沿着right后继指针处理,当right不是后继指针时,并且上一个处理节点是当前节点的右节点,则处理当前节点的右子树,遍历终止条件是:当前节点是root节点,并且上一个处理的节点是root的right节点

参考文献

尚硅谷Java数据结构与java算法

上一篇:saltstack部署lnmp


下一篇:webpack 中 loader 配置项 exclude、include 对打包的影响