第七章：树

# 第七章：树

# 概念

树是n个结点的有限集合，n=0时，称为空树，而任意非空树应满足：
1. 有且仅有一个特定的称为根的结点
2. 当n>1时，其余结点可分为m（m>0）个互不相交的有限集合，其中每一个集合本身又是一棵树，称为根结点的子树
祖先结点和子孙结点
双亲结点和孩子结点
兄弟结点
度：树中的一个结点的子结点的个数
树的度：树中最大的度
分支结点：度大于0
叶子结点：度等于0
结点的层次：从上往下数，从1开始
高度：从下往上数
深度：从上往下数
树的高度（深度）是树中结点的最大层数
有序树和无序树
路径：树中两个结点之间的路径是有这两个结点之间经过的结点序列构成的。路径一定是自上而下的。
路径长度：路径中所经历的边的个数。如A->B->C，路径长度是2
森林：m(m>0)棵互不相交的树的集合。

# 性质

树中的结点数等于所有结点的度数+1
度为m的树中第i层上至多有个结点（i>1）
高度为h的m叉树至多有个结点
具有n个结点的m叉树的最小高度为

# 二叉树

# 概念

二叉树是n(n>=0)个结点的有限集合
1. n=0时，二叉树为空
2. n>0时，由根结点和两个互不相交的被称为根的左子树和右子树组成，左子树和右子树也分别是一棵二叉树。

# 性质

，，两式相消得
非空二叉树上第k层至多有个结点
高度为h的二叉树至多有个结点
对完全二叉树按从上到下、从左到右的顺序依次编号1,2,...,n，则有以下关系：
- 当i>1时，结点i的双亲结点标号为i/2，即当i为偶数是，其双亲结点的编号为i/2，他是双亲结点的左孩子，当i为奇数时，其双亲结点的编号为(i-1)/2，他是双亲结点的右孩子
- 当2i<=n时，结点i的左孩子编号为2i，否则无左孩子
- 当2i+1<=n时，结点i的右孩子编号为2i+1，否则无右孩子
结点i所在的层次为
具有n个（n>0）结点的完全二叉树的高度为（取下限）或（取上限）

# 满二叉树

# 定义

一棵高度为h，且含有个结点的二叉树称为满二叉树
对于编号为i的结点，若存在，其双亲的编号为，左孩子为，右孩子为

# 完全二叉树

# 定义

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

# 性质

若，则结点i为分支节点，否则为叶子结点
叶子结点只可能在最大的两层出现，对于最大层次的叶子结点，都依次排在最左边的位置
度为1的结点若存在，则可能有一个，且编号最大的分支节点，并孩子结点一定是左结点

# 二叉排序树

# 定义

对于任意结点若存在左子树或右子树，则其左子树上所有结点的关键字均小于该结点，右子树上所有结点的关键字均大于该结点

# 平衡二叉树

# 定义

树上任意结点的左子树和右子树的深度之差不超过1

# 顺序存储

用一组连续的存储单元依次自上而下、自左而右存储完全二叉树上的结点元素
顺序存储最坏情况会浪费很多存储空间，比较适合存储完全二叉树

# 链式存储

用链表来存放一棵二叉树，二叉树中每个结点用链表的一个链结点来存储

# 定义

/* 结点的结构体 */
typedef struct BiTNode
{
  int data;
  struct BiTNode *next, *lchild, *rchild;
}BiTNode, *BiTree;

1
2
3
4
5
6

# 二叉树的遍历

按某条搜索路径访问树中的每个结点，树的每个结点均被访问一次，有且只访问一次
先序遍历：根左右
中序遍历：左根右
后序遍历：左右根
例子遍历下图：

# 先序遍历

使用递归算法

/* 先序遍历，结果：124536 */
void PreOrder(BiTree T)
{
  if(T != NULL)
  {
    visit(T);
    PreOrder(T->lchild);
    PreOrder(T->rchild);
  }
}

1
2
3
4
5
6
7
8
9
10

使用非递归算法
1. 初始扫描根结点，进栈
2. 出栈一个结点并访问它
3. 如果该结点有右孩子结点或左孩子结点，进栈其孩子结点
4. 重复步骤2，直到栈空

/* 先序遍历（非递归） */
void InOrder2(BiTree T)
{
  LiStack S;
  InitStack(&S);
  BiTree p = T;
  if(p != NULL)
  {
    Push(&S, p);
    while (!StackEmpty(S))
    {
      Pop(&S, p);
      visit(p);
      if(p->rchild)
      {
        Push(&S, p);
      }
      if(p->lchild)
      {
        Push(&S, p);
      }
    }
  }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

# 中序遍历

使用递归算法

/* 中序遍历，结果：425163 */
void InOrder(BiTree T)
{
  if(T != NULL)
  {
    InOrder(T->lchild);
    visit(T);
    InOrder(T->rchild);
  }
}

1
2
3
4
5
6
7
8
9
10

非递归算法
1. 初始时依次扫描根结点的所有左侧结点并将它们一一进栈
2. 出栈一个结点，访问它
3. 扫描该结点的右孩子结点并将其进栈
4. 依次扫描右孩子结点的所有左侧结点并一一进栈
5. 反复该过程直到栈空为止

/* 中序遍历（非递归） */
void InOrder2(BiTree T)
{
  LiStack S;
  InitStack(&S);
  BiTree p = T;
  while (p || !StackEmpty(S))
  {
    if(p)
    {
      Push(&S, p);
      p = p->lchild;
    }
    else
    {
      Pop(&S, p);
      visit(p);
      p = p->rchild;
    }
  }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

# 后序遍历

/* 后序遍历，结果：452631 */
void PostOrder(BiTree T)
{
  InOrder(T->lchild);
  InOrder(T->rchild);
  visit(T);
}

1
2
3
4
5
6
7

# 层次遍历

初始将根结点入队
判断队列是否为空，如果不为空将出队第一个结点
访问该结点
如果该结点有左孩子结点或右孩子结点，则将其孩子结点入队
重复步骤2.3.4
直到队列为空为止

/* 层次遍历，结果：123456 */
void levelOrder(BiTree T)
{
    InitQueue(Q);
    BiTree p;
    EnQueue(Q, T);
    while(!isEmpty(Q))
    {
        OutQueue(Q, p);
        visit(p);
        if(p->lchild != NULL)
        	EnQueue(p->lchild);
        if(p->rchild != NULL)
            EnQueue(p->rchild);
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

# 二叉树的建立

/* 二叉树的建立 */
void CreateBiTree(BiTree *T)
{
  int ch;
  scanf("%d", ch);
  if(ch == 9999)
    *T = NULL;
  else
  {
    *T = (BiTNode *)malloc(sizeof(BiTNode));
    (*T)->data = ch;
    CreateBiTree(&(*T)->lchild);
    CreateBiTree(&(*T)->rchild);
  }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

# 树的存储结构

# 双亲表示法

优点：寻找双亲结点效率高
缺点：寻找孩子结点效率低

# 孩子表示法

优点：寻找孩子结点效率高
缺点：寻找双亲结点效率低

# 孩子兄弟表示法

优点：寻找孩子结点效率高、方便实现树转为二叉树
缺点：寻找双亲结点效率低

# 树、森林与二叉树的转换

# 树转二叉树

加线，所有兄弟结点之间加一根线
去线，只保留第一个孩子结点的连线
调整

# 森林转二叉树

按照树转二叉树的方法把每一棵树转为二叉树
第一颗二叉树不动，依次把后一棵二叉树作为根结点的右孩子结点

# 二叉树转树

加线，将所有右孩子结点与其双亲结点的双亲结点相连接
去线，删除原来结点中与右孩子结点的连线
调整

# 二叉树转森林

去线，删除所有与右孩子结点的连线，得到一些二叉树
转换，利用二叉树转树的方法将所有二叉树转为树

# 哈夫曼树

# 带权路径长度（WPL）

# 哈夫曼树

# 概念

哈夫曼树也称最优二叉树，含有n个带权叶子结点带权路径长度最小的二叉树

# 构造方法

将n个结点作为n棵仅含有一个根结点的二叉树，构成森林F
生成一个新结点，并从F中找出根结点权值最小的两棵树作为它的左右子树，新结点的权值为两棵子树根结点的权值之和，至此有了一棵新树
从F中删除这两棵树，把新树加入到F中
重复2,3步骤，直到F中只有一棵树为止

# 性质

每个初始结点都会成为叶子结点，双支结点都为新生成的结点
权值越大离根结点越近，反之权值越小离根结点越远
哈夫曼树中没有结点的度为1
n个叶子结点的哈夫曼树的结点总数为2n-1，其中度为2的结点数为n-1

#数据结构 #考研

上次更新: 2020/11/05, 15:11:00

← 第六章：串第八章：图→