数据结构 408-5-1&2

# 树

# 树的基本概念

树：从树根生长，逐级分支

空树：节点数为 0 的树

非空树的特性：

• 有且仅有一个根节点

• 没有后继的结点称为 "叶子结点"(或终端结点)

• 有后继的结点称为 "分支结点"(或非终端结点)

• 除了根结点外，任何一个结点都有且仅有一个前驱

• 每个结点可以有 0 个或多个后继

树是 n ($n\ge 0$) 个结点的有限集合，n=0 时，称为空树，这是一种特殊情况。在任意一颗非空树中应满足：

• 有且仅有一个特定的称为根结点

• 当 n>1 时，其余结点可分为 m (m>0) 个互不相交的有限集合$T_1,T_2,...,T_m$，其中每个集合本身又是一棵树，并且称为根节点的子树

• 树是一种递归定义的数据结构

# 结点关系

祖孙结点、子孙结点、双亲结点 (父节点)、孩子结点、兄弟节点、堂兄弟节点

两节点间路径 (只能从上往下)

路径长度 (经过几条边)

结点的层次 (深度)—— 从上往下数

结点的高度 —— 从下往上数

树的高度 (深度)—— 总共多少层

结点的度 —— 有几个孩子 (分支)

• 非叶子节点的度 > 0，叶子节点的度 = 0

树的度 —— 各结点的度的最大值

# 有序树 vs 无序树

有序树：逻辑上看，树中结点的各子树从左至右是有次序的，不能互换

无序树：逻辑上看，树中结点的各子树从左至右是无次序的，可以互换

具体看用树存储的数据，是否需要用结点的左右位置反映某些逻辑关系

# 森林

森林是 m (m>0) 棵互不相交的树的集合

考点：森林转化成树

# 树的性质

考点 1：结点数 = 总度数 + 1

考点 2：度为 m 的树，m 叉树的区别

• 树的度 —— 各结点的度的最大值
• m 叉树 —— 每个节点最多只能有 m 个孩子的树

考点 3：度为 m 的树第 i 层至多有$m^{i-1}$ 个节点 ($i\ge1$)，m 叉树第 i 层至多有$m^{i-1}$ 个结点 ($i\ge1$)

考点 4：高度为 h 的 m 叉树至多有$\dfrac{m^h-1}{m-1}$ 个节点

考点 5：高度为 h 的 m 叉树至少有 h 个结点，高度为 h、度为 m 的树至少有$h+m-1$ 个结点

考点 6：具有 n 个结点的 m 叉树的最小高度为$\lceil log_m(n(m-1)+1)\rceil$

高度最小的情况 —— 所有结点都有 m 个孩子

# 二叉树

# 二叉树的基本定义与基本术语

# 二叉树基本概念：

二叉树是 n ($n\ge 0$) 个结点的有限集合：

• 或者为空二叉树，即 n=0
• 或者由一个根节点和两个互不相交的被称为跟的左子树和右子树组成。左子树和右子树又分别是一颗二叉树
• 特点：
  • 每个结点至多只有两颗子树
  • 左右子树不能颠倒 (二叉树是有序树)
  • 注意区别：度为 2 的有序树

特殊二叉树：

• 满二叉树：一颗高度为 k，且含有$2^h-1$ 个结点的二叉树

  • 特点：
  • 只有最后一层有叶子结点
  • 不存在度为 1 的节点
  • 按层序从 1 开始编号，结点 i 的左孩子为 2i，右孩子为 2i+1；结点 i 的父节点为$\lfloor i/2\rfloor$ (如果有)

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

  • 特点：
  • 只有最后两层可能有叶子节点
  • 最多只有一个度为 1 的结点
  • 同满二叉树第三条
  • $i\le\lfloor n/2\rfloor$ 为分支节点，$i\ge\lfloor n/2\rfloor$ 为叶子节点

• 二叉排序树：一颗二叉树或者是空二叉树，或者是具有如下性质的二叉树：

  • 左子树上所有结点的关键字均小于根结点的关键字
  • 右子树上所有结点的关键字均大于根结点的关键字
  • 左子树和右子树又各是一棵二叉排序 树
  • 二叉排序树可用于元素的排序、搜索

• 平衡二叉树：树上任一结点的左子树和右子树的深度之差不超过 1

  • 平衡二叉树能有更高的搜索效率

# 二叉树的性质

考点 1：设非空二叉树中度为 0、1 和 2 的结点个数分别为$n_0,n_1,n_2$，则$n_0=n_2+1$ (叶子结点比二分支结点多一个)

• 假设树中总结点数为 n，则
  • $n=n_0+n_1+n_2$
  • $n=n_1+2n_2+1$ (树的结点个数 = 总度数 + 1)

考点 2：二叉树第 i 层至多有$2^{i-1}$ 个结点 ($i\ge 1$)，m 叉树第 i 层至多有$2^{m-1}$ 个结点 ($i\ge 1$)

考点 3：高度为 h 的二叉树至多有$2^h-1$ 个结点 (满二叉树)，高度为 h 的 m 叉树至多有$\dfrac{m^h-1}{m-1}$ 个结点

# 完全二叉树的性质

考点 1：具有 n (n>0) 个结点的完全二叉树的高度为 h 为$\lceil log_2(n+1)\rceil$ 或$\lfloor log_2n\rfloor+1$，高度为 h 的满二叉树共有$2^h-1$ 个结点

第 i 个结点所在层次为$\lceil log_2(n+1)\rceil$ 或$\lfloor log_2n\rfloor+1$

考点 2：对于完全二叉树，可以由结点数 n 推出度为 0、1、2 的结点个数为$n_0,n_1,n_2$

• 完全二叉树最多只有一个度为 1 的结点，即$n_1=1\ or\ 0$
• $n_0=n_2+1$，$n_0+n_2$ 一定是奇数
• 若完全二叉树由 2k 个结点，则必有$n_1=1,n_0=k,n_2=k-1$
• 若完全二叉树由 2k-1 个结点，则必有$n_1=0,n_0=k,n_2=k-1$

# 二叉树的存储结构

# 顺序存储

#define MaxSize 100
struct TreeNode{
    ElemType value; //结点中的数据元素
    bool isEmpty; //结点是否为空
};
TreeNode t[MaxSize];
//定义一个长度为MaxSize的数组t，按照从上至下、从左至右的顺序依次存储完全二叉树的各个结点
for(int i=0;i<MaxSize;i++)
    t[i].isEmpty=true; //初始化时所有节点标记为空

二叉树的顺序存储中，一定要把二叉树的结点编号与完全二叉树对应起来

• i 的左孩子 ——2i
• i 的右孩子 ——2i+1
• i 的父亲节点 ——$\lfloor i/2\rfloor$

最坏情况：高度为 h 且只有 h 个结点的单支树 (所有结点只有右孩子)，也至少需要$2^h-1$ 个存储单元

结论：二叉树的顺序存储结构，只适合存储完全二叉树

# 链式存储

//二叉树的存储(链式存储)
typedef struct BiTNode{
    ElemType data; //数据域
    struct BiTNode *lchild,*rchild; //左、右孩子指针
	struct BiTNode *parent; //父节点指针
}BiTNode,*BiTree;
//定义一棵空树
BiTree root=NULL;
//插入根结点
root=(BiTree)malloc(sizeof(BiTNode));
root->data={1};
root->lchild=NULL;
root->rchild=NULL;
//插入新节点
BiTNode *p=(BiTNode*)malloc(sizeof(BiTNode));
p->data={2};
p->lchild=NULL;
p->rchild=NULL;
root->lchild=p; //作为根结点的左孩子

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