一、树的概念:
树其实是区别于线性表,线性结构的另一种数据结构,本质是结点的有限集。树的定义有两点: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)后序遍历:
其实递归遍历的核心思想是理解递归,关于这一点大家可以去看一下我写的递归和栈的那篇文章,有详细的解释。