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

2023-10-07 20:02:04

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

顺序存储二叉树
线索化二叉树
参考文献

顺序存储二叉树

基本概念：

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

要求：

右图的二叉树的结点，要求以数组的方式来存放 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算法

码农公寓