当前位置：网站首页>（十）树的基础部分（二）

（十）树的基础部分（二）

2022-08-04 05:28:00 【顺毛黑起】

顺序存储二叉树

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

顺序存储二叉树的特点

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

顺序存储二叉树遍历

需求: 给你一个数组 {1,2,3,4,5,6,7}，要求以二叉树前序遍历的方式进行遍历。 前序遍历的结果应当为1,2,4,5,3,6,7

package com.atguigu.tree;

public class ArrBinaryTreeDemo {
    
    public static void main(String[] args) {
    
        int[] arr={
    1,2,3,4,5,6,7};
        ArrBinaryTree arrBinaryTree = new ArrBinaryTree(arr);
        arrBinaryTree.preOrder();//1 2 4 5 3 6 7
    }
}

//编写一个ArrayBinaryTree，实现顺序存储二叉树遍历
class ArrBinaryTree{
    
    private int[] arr;//存储数据，存储二叉树的结点

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

    //重载preOrder
    public void preOrder(){
    
        this.preOrder(0);
    }

    //编写方法，完成顺序存储二叉树的前序遍历

    /** * * @param index 数组的下标 */
    public void preOrder(int index){
    
        if (arr==null || arr.length==0){
    
            System.out.println("数组为空，不能按照二叉树的前序遍历");
        }
        //输出当前这个元素
        System.out.println(arr[index]);
        //向左递归遍历
        if ((index*2+1)<arr.length){
    //防止index越界
            preOrder(2*index+1);
        }
        //向右递归遍历
        if ((index*2+2)<arr.length){
    //防止index越界
            preOrder(2*index+2);
        }
    }
}

线索化二叉树

线索二叉树基本介绍

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

线索二叉树应用案例（创建以及遍历）

应用案例说明：将下面的二叉树，进行中序线索二叉树。中序遍历的数列为 {8, 3, 10, 1, 14, 6}
在这里插入图片描述在这里插入图片描述
说明: 当线索化二叉树后，Node 节点的 属性 left 和 right ，有如下情况:

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

public class ThreadBinaryTreeDemo {
    
    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.threadNodes();

        //测试10号结点
        HeroNode left=node5.getLeft();
        System.out.println("10号结点的前驱结点"+left);
        HeroNode right=node5.getRight();
        System.out.println("10号结点的后继结点"+right);

        //当线索化二叉树后，不能使用原来遍历二叉树的方式再次进行遍历，有可能会出现死循环，造成溢出。
        // 因为结点，有可能原来左或者右为空，而现在有了指向。
        System.out.println("使用线索化的方式遍历线索化二叉树");
        threadedBinaryTree.threadList();// 8 3 10 1 14 6


    }
}

//定义ThreadedBinaryTree实现了线索化功能的二叉树
class ThreadedBinaryTree{
    

    private HeroNode root;

    //为了实现线索化，需要创建指向当前结点的前驱结点的指针
    //在递归进行线索化时，pre总是保留前一个结点
    private HeroNode pre=null;

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

    //重载threadedNodes方法
    public void threadNodes(){
    
        this.threadNodes(root);
    }

    //遍历线索化二叉树
    public void threadList(){
    
        //定义一个变量，存储当前遍历的结点，从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 threadNodes(HeroNode node){
    
        //如果node==null,不能线索化
        if (node==null){
    
            return;
        }

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

        //2.线索化当前节点

        //处理当前结点的前驱结点
        if (node.getLeft()==null){
    
            //让当前结点的左指针指向前驱结点
            node.setLeft(pre);
            //修改当前结点的左指针类型,指向前驱结点
            node.setLeftType(1);
        }
        //处理后继结点 前驱结点的后继结点就是当前结点
        if (pre!=null && pre.getRight()==null){
    
            pre.setRight(node);
            pre.setRightType(1);
        }

        //每处理一个节点后，让当前节点是下一个节点的前驱结点
        pre=node;

        //3.再线索化右子树
        threadNodes(node.getRight());
    }


}


//创建HeroNode结点
class HeroNode {
    
    private int no;
    private String name;
    private HeroNode left;//默认null
    private HeroNode right;//默认null
    //说明
    //1.如果leftType==0表示指向的是左子树，如果leftType==1表示指向的是前驱结点
    //2.如果rightType==0表示指向的是右子树，如果rightType==1表示指向的是后继结点
    private int leftType;
    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 + '\'' +
                '}';
    }
}
原网站

版权声明
本文为[顺毛黑起]所创，转载请带上原文链接，感谢
https://blog.csdn.net/Apikaqiu/article/details/117319963

边栏推荐

猜你喜欢

随机推荐