数据结构：树的基本概念（二叉树，定义性质，存储结构）

1.树

1.基本概念

树是n (n>=0）个结点的有限集合，n =0时，称为空树，这是一种特殊情况。
在任意一棵非空树中应满足:
①有且仅有一个特定的称为根的结点。
②当n>1时，其余结点可分为m (m>0）个互不相交的有限集合T1,T2…… Tm，其中每个集合本身又是一棵树，并且称为根结点的子树。
③树是一种递归定义的数据结构。

1.空树

结点数为0的树。

2.非空树

①有且仅有一个根节点
②没有后继的结点称为“叶子结点”(或终端结点)
③有后继的结点称为“分支结点”(或非终端结点）
④除了根节点外，任何一个结点都有且仅有一个前驱
⑤每个结点可以有0个或多个后继。

2.基本术语

1.结点之间的关系描述

①祖先结点
②子孙结点
③双亲结点（父节点）
④孩子结点
⑤兄弟结点
⑥堂兄弟结点
⑦路径：只能从上而下
⑧路径长度：经过几条边

2.结点、树的属性描述

①结点的层次（深度)：从上往下数（默认从1开始)
②结点的高度：从下往上数
③树的高度（深度）：总共多少层
④结点的度：有几个孩子（分支)
⑤树的度：各结点的度的最大值

3.有序树、无序树

①有序树――逻辑上看，树中结点的各子树从左至右是有次序的，不能互换
②无序树――逻辑上看，树中结点的各子树从左至右是无次序的，可以互换

4.森林

森林是m ( m≥0）棵互不相交的树的集合。

3.树的常考性质

①结点数=总度数+1

②度为m的树、m叉树的区别
树的度：各结点的度的最大值
m叉树：每个结点最多只能有m个孩子的树

③度为m的树第i层至多有$m^{i-1}$个结点( i≥1)
④高度为h的m叉树至多有$\frac{m^h-1}{m-1}$个结点。(等比数列求和)
⑤高度为h的m叉树至少有h个结点。
高度为h、度为m的树至少有h+m-1个结点。
⑥具有n个结点的m叉树的最小高度为$[lo{g}_m^{(n(m-1)+1)}]$(向上取整)

2.二叉树

1.基本概念

二叉树是n (n≥0）个结点的有限集合:
①或者为空二叉树，即n = 0。
②或者由一个根结点和两个互不相交的被称为根的左子树和右子树组成。
左子树和右子树又分别是一棵二叉树。
特点:①每个结点至多只有两棵子树②左右子树不能颠倒(二叉树是有序树)

2.特殊二叉树

1.满二叉树

一棵高度为h，且含有$2^h-1$个结点的二叉树

特点:
①只有最后一层有叶子结点
②不存在度为1的结点
③按层序从1开始编号，结点i的左孩子为2i，右孩子为2i+1;
结点i的父节点为[i/2] (向下取整)

2.完全二叉树

当且仅当其每个结点都与高度为h的满二叉树中编号为1~n的结点一一对应时，称为完全二叉树。

特点:
①只有最后两层可能有叶子结点
②最多只有一个度为1的结点
③按层序从1开始编号，结点i的左孩子为2i，右孩子为2i+1;
④i≤ [n/2]为分支结点，i>[n/2]为叶子结点(向下取整)

3.二叉排序树

一棵二叉树或者是空二叉树，或者是具有如下性质的二叉树:
左子树上所有结点的关键字均小于根结点的关键字;
右子树上所有结点的关键字均大于根结点的关键字。
左子树和右子树又各是一棵二叉排序树。(左小右大)

二叉排序树可用于元素的排序、搜索。

4.平衡二叉树

树上任一结点的左子树和右子树的深度之差不超过1。
平衡二叉树能有更高的搜索效率。

3.常考性质

①:设非空二叉树中度为0、1和2的结点个数分别为n0,n1,和n2，则n0= n2+ 1。(叶子结点比二分支结点多一个)
树的结点数=总度数+1
②二叉树第i层至多有$2^{i-1}$个结点（ i≥1)
③高度为h的二叉树至多有$2^h—1$个结点（满二叉树)
④具有n个(n >0）结点的完全二叉树的高度h为$[lo{g}_2^{(n+1)}](向上取整)或[lo{g}_2^n]+1（向下取整）$
⑤若完全二叉树有2k个（偶数）个结点，则必有n1=1，n0 = k, n2 = k-1；
若完全二叉树有2k-1个（奇数）个结点，则必有n1=0，n0 = k, n2 = k-1.

4.二叉树的存储结构

1.顺序存储

二叉树的顺序存储中，一定要把二叉树的结点编号与完全二叉树对应起来。
利用完全二叉树，父节点与孩子结点的关系，存放在指定数组下标。

最坏情况:高度为h 且只有h个结点的单支树（所有结点只有右孩子），也至少需要$2^h-1$个存储单元。
结论:二叉树的顺序存储结构，只适合存储完全二叉树。

2.链式存储

n个结点的二叉链表共有n+1个空链域。

使用三叉链表――方便找父结点。