原创

树结构

温馨提示:
本文最后更新于 2022年06月18日,已超过 8 天没有更新。若文章内的图片失效(无法正常加载),请留言反馈或直接联系我

树结构

tree结构的存储方式:

  1. 拿出一个数据作为第一个节点(head节点),用第二个数和前面的数进行比较。发现比他大放在右边,比他小放在左边

tree的概念

  • 节点
  • 父节点
  • 子节点
  • 根节点
  • 叶子节点

image-20220503084745159

二叉树的概念

  • 如果每一个父节点都对应最多两个子节点,那么这样的tree称为二叉树

  • 如果该二叉树的所有叶子节点都在最后一层,并且节点总数为2^n-1,n为层数,我们称为满二叉树

  • 如果该二叉树的所有叶子节点都在最后一层或者倒数第二层,而且最后一层的叶子节点在左边连续,倒数第二层的叶子节点在右边连续,我们称为完全二叉树。

image-20220503084849619

顺序存储二叉树的方法

顺序二叉树通常只考虑完全二叉树
第n个元素的左子节点为 2 n + 1
第n个元素的右子节点为 2
n + 2
第n个元素的父节点为 (n-1) / 2

线索化二叉树

n个结点的二叉链表中含有n+1 【公式 2n-(n-1)=n+1】 个空指针域。利用二叉链表中的空指针域,存放指向该结点在某种遍历次序下的前驱和后继结点的指针(这种附加的指针称为"线索")

这种加上了线索的二叉链表称为线索链表,相应的二叉树称为线索二叉树(Threaded BinaryTree)。根据线索性质的不同,线索二叉树可分为前序线索二叉树、中序线索二叉树和后序线索二叉树三种

一个结点的前一个结点,称为前驱结点
一个结点的后一个结点,称为后继结点

正文到此结束