绑定完请刷新页面
取消
刷新

分享好友

×
取消 复制
数据结构——树
2020-05-20 15:15:21

一、树的概念:

树其实是区别于线性表,线性结构的另一种数据结构,本质是结点的有限集。树的定义有两点:1)有且仅有一个特定的称为根(root)的结点;2)当结点数量>1时,其余结点可分为若干个互不相交的有限集,其中每个集合也可以看作一颗树,称之为根的子树。

1.度(结点的分类):

结点拥有的子树的数量是为树的度。

如上图所示,B结点的度为1,因为他只拥有根为D的一颗子树,而D的度为3,因为他拥有G、H、I 三颗只有根的子树,这就是结点的度,大家可以思考一下A结点的度是多少?

一颗树的度则是这棵树中度最多的结点的度的值,上面这颗树的度则是D结点的度,为3。

2.结点之间的关系:

结点的子树的根称之为该结点的孩子(child结点)

该结点衍生出来的结点称之为该结点的父母(parent结点)

由同一个结点衍生出的同一层结点互相称之为兄弟(sibling)

由同一个结点之下的所有结点称之为子孙,例如B的子孙有D、G、H、I 结点。

3.树的层&深度:

如图所示,结点的层次从根算起,根为第一层,根的孩子为第二层以此类推。

一棵树的深度是树中结点层次最大的值称为树的深度,或高度。


二、树的存储结构:

双亲孩子表示法:

把树种的所有结点的值依次组成一个单链表,一个结点种定义三个域,分别是数据域、父母指针域、长子(第一个孩子)指针域,如果这个长子有兄弟的话,则指针域指向下一个存储兄弟位置的指针域,否则就为空。

二、二叉树:

1.二叉树的定义:和树的定义类似,但是有一个特点:由一个根节点和两颗互不相交的,分别称为根节点的左子树和右子树的二叉树组成。(二叉树是递归定义)

2.二叉树的特点:1)每个结点最多有两颗子树;2)左子树与右子树有顺序,即使一颗树中只有一个子树,也需要去判断是左子树还是右子树。

3.一些特殊的二叉树:1)斜树:所有结点都只有左子树或所有结点都只有右子树的二叉树称为斜树(斜树其实就是单链表!);2)满二叉树:如果一棵二叉树的所有分支结点都存在左右子树,并且所有的叶子结点都在同一层,则称之为满二叉树;

3)完全二叉树:如果每个结点按层序编号与相同层数的满二叉树编号一致的话,则这棵树称为满二叉树。

2.二叉树的性质:

1)在二叉树的第n层上最多有2^(n - 1)个结点。比如第一层:1个结点,第二层:2个 以此类推。

2)深度为k的二叉树至多有2^k - 1 个结点,例如图6-5-5的满二叉树有四层,结点有15个。数学归纳法可以证明。

3)一颗二叉树的叶子结点树为n,度为2的结点数量为m,则 n = m + 1

证明过程:设一颗二叉树的所有结点为n,度为1的结点为n1,度为2的结点是n2,叶子节点为n0,则:n = n1 + n2 + n0;因为二叉树只有度为1或2的结点和叶子节点。而一颗二叉树的所有连线可以根据二叉树图像直观推出:n1 + n2 * 2 ;度为1的结点只有一条连线,度为2的结点有两条连线,而一颗二叉树的连线等于结点的数量减1,所以课可以列出式子: n1 + n2 + n0 - 1 = n1 + 2n2 可以得出性质3

4)具有n个结点的完全二叉树深度为:log2n + 1可以根据性质2推出来。

5)对于一颗结点数量为n的完全二叉树,n为树的深度,i为按树的层为结点编号,则:1.i = 1则此结点为根结点;2.若i > 2n 要么此结点的左孩子是2i,否则不存在左孩子;3.与2类似,若i结点存在右孩子,则右孩子序号为 2i + 1;

3.二叉树的存储结构(重要):

1)顺序存储结构:将二叉树中的每一个结点按照满二叉树的层次序号进行编号,将空着的编号进行留空,将结点中的数据存入数组对应编号中,这样可以做成二叉树的顺序存储结构。

但是缺点是浪费存储空间,举个例子:斜二叉树的顺序存储结构会是怎么样的呢?

如图所示,浪费了非常多的存储空间,所以顺序存储结构只适用于完全二叉树。

2)二叉链表:

首先树结点定义与结点定义类似,但是指针域有两个,分别是lchild(左孩子)和rchild(右孩子)。如图所示:

树的定义与单链表定义有相似之处,就是必须要有根节点。

树的创造方法:(while方法,非递归)

用类似于栈的思想进行树的创建,其实和递归类似,递归也是用到栈。

4.二叉树的遍历:

众所周知二叉树的三种遍历方法:前序遍历、中序遍历、后序遍历;其实还有一种层序遍历,就是按照一层一层从左到右的顺序依次遍历树。、

1)前序遍历:

2)中序遍历:

3)后序遍历:

其实递归遍历的核心思想是理解递归,关于这一点大家可以去看一下我写的递归和栈的那篇文章,有详细的解释。

分享好友

分享这个小栈给你的朋友们,一起进步吧。

zbdba
创建时间:2020-05-20 14:39:41
数据库架构/内核
展开
订阅须知

• 所有用户可根据关注领域订阅专区或所有专区

• 付费订阅:虚拟交易,一经交易不退款;若特殊情况,可3日内客服咨询

• 专区发布评论属默认订阅所评论专区(除付费小栈外)

栈主、嘉宾

查看更多
  • zbdba
    栈主

小栈成员

查看更多
  • 一号管理员
  • gaokeke123
  • kaluola
戳我,来吐槽~