IT数码 购物 网址 头条 软件 日历 阅读 图书馆
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
图片批量下载器
↓批量下载图片,美女图库↓
图片自动播放器
↓图片自动播放器↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁
 
   -> 数据结构与算法 -> 数据结构与结构——二叉树(2) -> 正文阅读

[数据结构与算法]数据结构与结构——二叉树(2)

目录

一、顺序存储二叉树

1.基本说明

2.代码实现

二、线索化二叉树

代码实现

三、遍历线索化二叉树

?

一、顺序存储二叉树

1.基本说明

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

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

顺序存储二叉树的特点:

1)顺序二叉树通常只考虑完全二叉树

2)第n个元素的左子节点为2*n+ 1

3)第n个元素的右子节点为2 *n+2

4)第n个元素的父节点为(n-1)/ 2

5) n:表示二叉树中的第几个元素(按О开始编号如图所示)

2.代码实现

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

class ArrBinaryTree{
    private int[] arr; // 储存数据结点的数组
    public ArrBinaryTree(int[] arr){
        super();
        this.arr = arr;
    }
    //重载preOrder
    public void preOder(){
        this.preOder(0);
    }
    //编写一个方法,完成顺序存储二叉树的前序遍历
    /**
     *
     * @param index  数组的下标
     */
    public void preOder(int index) {
        //如果数组为空,或者arr.length = 0
        if (arr == null || arr.length == 0) {
            System.out.println("数组为空,不能按照二叉树的前序遍历!");
        }
        //输出当前这个元素
        System.out.println(arr[index]);
        //向左递归遍历
        if (index * 2 + 1 < arr.length) {
            preOder(2 * index + 1);
        }
        //向右递归
        if (index * 2 + 2 < arr.length) {
            preOder(2 * index + 2);
        }
    }
}

测试:

public static void main(String[] args) {
    int[] arr = {1,2,3,4,5,6,7};
    //创建一个ArrayBinaryTree
    ArrBinaryTree arrBinaryTree = new ArrBinaryTree(arr);
    arrBinaryTree.preOder();  //1,2,4,5,3,6,7
}

二、线索化二叉树

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

说明:

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

?

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

? ? ? ? 2) right指向的是右子树,也可能是指向后继节点,比如①节点 right 指向的是右子树,而⑩节点的right 指向的是后继节点。

代码实现

1.在节点类中增加新的节点属性(以及对应的get 和 set 方法)

private HeroNode left;  //默认为null
private HeroNode right; //默认为null
//说明:
//1.如果leftType = 0 表示指向的式左子树
//2.如果LeftType = 1 编辑室指向前驱节点
//rightType同理
private int LeftType;
private int RightType;

2.再在定义二叉树时,实现二叉树的线索化
? ? ? ? 1)首先定义一个前驱指针

//为了实现线索化,需要创建给指向当前结点的前驱节点的指针
//pre总是保留前一个结点
private HeroNode preNode = null;

? ? ? ? 2)编写对二叉树进行线索化(中序)

public void threadeNodes(HeroNode node){  //对节点进行线索化
    //1.判断当前结点是否为空,若为空,则无法线索化
    if(node == null){
        return;
    }
    //2.1 先线索化左子树
    threadeNodes(node.getLeft());
    //2.2 再线索化当前节点【!!!】
    //2.2.1处理当前节点的前驱节点
    if (node.getLeft() == null){
        //使当前结点的左指针指向前驱节点
        node.setLeft(preNode);
        //修改当前节点的left指针类型,指向前驱节点的类型
        node.setLeftType(1);
    }
    //2.2.2 处理后序结点
    if (preNode != null && preNode.getRight() == null){
        //使当前结点的左指针指向前驱节点
        preNode.setRight(node);
        //修改当前节点的left指针类型,指向前驱节点的类型
        preNode.setRightType(1);
    }
    //!!!2.2.3 每处理一个结点后,让当前节点是下一个结点的前驱系欸但
    preNode = node;
    //2.3 最后线索化右子树
    threadeNodes(node.getRight());
}

3.在测试调用threadeNodes方法时,为了方便,可以重载threadeNodes方法,从而直接使用结点对象调用该方法

//重载 threadeBinaryNode 方法
public void threadeNodes() {
    this.threadeNodes(root);
}

三、遍历线索化二叉树

可以直接在定义二叉树类中实现

//遍历线索化二叉树的方法
public void TreadeList(HeroNode heroNode){
    //定义一个变量,临时存储当前遍历的结点
    HeroNode node = root;
    while (node != null){
        //循环找到 LeftType = 1 的结点
        //后面随着遍历而变化,因为当 LeftType = 1 的时候,说明该结点按照线索化处理后的有效结点
        while(node.getLeftType() == 0){
            node = node.getLeft();
        }
        //打印当前结点
        System.out.println(node);
        //如果当前结点的右指针指向的是后继结点,则说明是该结点的父结点
        while(node.getRightType() == 1){
            node = node.getRight();
            System.out.println(node);
        }
        //不等于1时就替换遍历结点
        node = node.getRight();
    }
}

可以debug来做一个解析过程。

  数据结构与算法 最新文章
【力扣106】 从中序与后续遍历序列构造二叉
leetcode 322 零钱兑换
哈希的应用:海量数据处理
动态规划|最短Hamilton路径
华为机试_HJ41 称砝码【中等】【menset】【
【C与数据结构】——寒假提高每日练习Day1
基础算法——堆排序
2023王道数据结构线性表--单链表课后习题部
LeetCode 之 反转链表的一部分
【题解】lintcode必刷50题<有效的括号序列
上一篇文章      下一篇文章      查看所有文章
加:2022-10-31 12:25:10  更:2022-10-31 12:27:32 
 
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁

360图书馆 购物 三丰科技 阅读网 日历 万年历 2024年12日历 -2024/12/28 2:03:43-

图片自动播放器
↓图片自动播放器↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  IT数码
数据统计