考研笔记 | 数据结构 §5. 树和二叉树

§1 树

1. 树是 N (N≥0) 个结点的有限集合，当 N=0 时，称为空树。
2. 对非空树，有：

• 有且仅有一个特定的结点，称为根；
• 当 N＞1 时，其余结点可风味 m (m＞0) 个互不相交的有限集合 $T_1$,$T_2$,……,$T_n$，其中一个集合又是一棵树，并称为子树。

• 树的根结点没有前驱结点，除根结点外仅有一个前驱；
• 树中所有结点可有零至多个结点。

graph LR
  A{祖先节点}---|n层|B(双亲结点)
  B(双亲结点)-->C[结点]
  B(双亲结点)-->D[兄弟结点]
  C(结点)-->E[孩子结点]
  E[孩子结点]-->|n层|F[子孙结点]

5. 树中的一个结点的子结点个数称为该结点的度。
   树中结点最大度数称为树的度。

6. 度大于 0 的结点称为分支结点，度为 0 的结点称为叶子（终端）结点。

7. 1. 结点层次从树根开始定义；
   2. 结点深度从根结点自顶向下累加；
   3. 结点高度从叶结点开始自底向上累加；
   4. 树的高度即为最大深度。
8. 1. 树的结点数等于所有结点的度数加 1；
   2. 度为 m 的树中第 i 层上至多有 $m^i-1$ 个结点 (i≥1);
   3. 高度为 h 的 m 叉树至多有 $\frac {m^n-1}{m-1}$ 个结点
   4. 具有 n 个结点的 m 叉树最小高度是 $\lceil log_m (n (m-1)+1)\rceil$

§2 二叉树

9. 二叉树：每个结点至多只有两棵子树，且有左右之分。

10. 二叉树有五种基本形态

    

11. 第 i 层上至多有 $2^i-1$ 个结点，深度为 $k$ 的二叉树至多有 $2^k-1$ 个结点。

12. 满二叉树：深度为 $k$, 有 $2^k-1$ 个结点。

13. 完全二叉树（最后一层不满）：

• $i≤\lfloor\frac {n}{2}\rfloor$，则 $i$ 为分支结点，否则是叶子；

• 若有度为 1 的结点，只可能有一个，即其仅有左孩子而无右孩子。

14. 二叉排序树：左子树上结点关键字 < 根节点 < 右子树节点。
15. 平衡二叉树：树上任一结点左右子树深度之差不超过 1。
16. 1) 非空二叉树上叶子结点树等于度为 2 的结点数加 1，即 $N_0=N_2+1$；
    2) 非空二叉树上第 $k$ 层最多有 $2^{k-1}$ 个结点（$k≥1$）；
    3) 高度为 $h$ 的二叉树至多有 $2^n-1$ 个结点；
    4)
    • 当 $i$＞1 时，结点 $i$ 的层次为 $\lfloor\frac {i}{2}\rfloor$，若 $i$=1，则为根；
    • $i$ 的左孩子是 $2i$，如果 $2i＞n$，则无左孩子；
    • $i$ 的右孩子是 $2i+1$, 若 $2i+1＞n$, 则无右孩子；
    • $i$ 所在的层次为 $\lfloor\log_2i\rfloor$+1。

• 5. 完全二叉树的高度为 $\lceil\log_2 (n+1)\rceil$ 或 $\lfloor\log_2n\rfloor+1$

§3 二叉树的存储结构

17. 顺序存储：用数组，编号 $i$ 存于 $i-1$ 外。无用的用 0 补全
18. 链式存储结构

• 二叉链表

  typedef struct BTNode{
  DataType data;
  struct BTNode,*lchild,*rchild;
  }BTNode,*BinTree;//二叉键表

• 三叉链表

  typedef struct BTNode{
  DataType data;
  struct BTNode,*lchild,*rchild,*parent;
  }BTNode,*BinTree;//三叉键表

19. 用二叉键表存储 n 个结点的二叉树，共要 (n+1) 个空指针域，
    用三叉键表存储 n 个结点的二叉树，共要 (n+2) 个空指针域。
20. 二叉树的遍历

• 1. 先序遍历，根左右 (NLR)

  void PreOrder(BiTree T){
    if(T!=Null){
      visit(T);
      PreOrder(T->lchild);
      PreOrder(T->rchild);
    }
  }

• 2. 中序遍历，左根右（LNR）

  void InOrder(BiTree T){
    if(T!=Null){			
        InOrder(T->lchild);
        visit(T);
        InOrder(T->rchild);
    }
  }

• 3. 后序遍历，左右根（LRN）

  void PostOrder(BiTree T){
    if(T!=Null){		
      PostOrder(T->lchild);			
      PostOrder(T->rchild);
      visit(T);
    }
  }

• 4. 层次遍历（借助队列）

  void LevelOrder(BiTree){
    InitQueue(Q);//初始化队列
    BiTree P;
    EnQueue(Q,T);//树根入队列
    while(!=IsEmpty(Q){
      DeQueue(Q,P);
      visit(P);
      if(P->lchild!=Null)
     	 EnQueue(Q,P->lchild);
      if(P->rchild!=Null)
     	 EnQueue(Q,P->rchild);
    }
  }

21. 非递归形式遍历

• 中序遍历

  void InOrder(BinTree T){
    InitStrack(S);
    BiTree P=T;
    while(P||!IsEmpty(S)){
      if(P){  
        Push(S,P);//根入栈
        P=p->lchild;//非空则往左走
      }else{
        Pop(S,P);//退栈
        visit(P);
        P=P->rchild;//访问右结点
      }
    }
  }

• 前序遍历

  void PreOrder(BinTree T){
    InitStrack(S);
    BiTree P=T;
    while(P||!IsEmpty(S)){
      if(P){
        visit(P);
        Push(S,P);//根入栈
        P=p->lchild;//非空则往左走
      }else{
        Pop(S,P);//退栈
        P->P->rchild;
        P=P->rchild;//访问右结点
      }
    }
  }

• 后序遍历

  void PostOrder(BinTree T){
    InitStrack(S);
    InitStrack(Tag);
    BiTree P=T;
    while(P||!IsEmpty(S)){  
      if(P){ 
        Push(S,P);
        Push(Tag,1);
        P=p->lchild;
      }else{  
        Pop(S,P);
        Pop(Tag,f);
        if(f==1){
        	Push(S,P);
        	Push(Tag,2);
       	P=P->rchild;//从左子树反回（二次入栈），然后转右子树
        }else{
          visit(P);
          P=Null;//从右子树反回（二次出栈），访问根。P必须置空，使得下一步继续退栈
        }
      }
    }
  }//栈中当前结点的所有祖先

22. 遍历二叉树的引用与思路
    1. 2. 1 3) 1+L 4) 1+R 5) 1+L+R

• 求二叉树结点的个数

  int NodeCount(BinTree T){
    if(T==0) return 0;
    else return 1+NodeCount(T->lchild)+NodeCount(T->rchild);
  }

• 求二叉树叶子结点的个数

  int LeafCount(BinTree T){
    if(T==0) return 0;
    else{
      if(T->lchild==0&&T->rchild==0) return 1;
      else return LeafCount(T->lchild)+LeafCount(T->rchild);
    } 
  }

• 求二叉树的深度

  int Depth(BinTree T){
    if(T==0) return 0;
    else return 1+Max(Depth(T->lchild),Depth(T->rchild);
  }

23. 线索二叉树
    若有左子树，则 ltag=0，否则，ltag=1，指向前驱；
    若有右子树，则 rtag=0，否则，rtag=1，指向后继。
24. 画线索二叉树：先画遍历序列，再画线索。

§4 一般树的存储结构

25. 树的存储结构

• 双亲表示法：存储结点，同时增加指针指向双亲。

  

  可直接找到每个结点的双亲，但求孩子需要遍历真个结构。

• 孩子表示法：将每个孩子结点都用单链表连接起来。​
  方便找子女，但找双亲需要遍历 N 个结点中孩子链表所知的 N 个孩子链表

• 孩子兄弟表示法：每个结点有三个部分，值、第一个孩子、第一个兄弟。
  优点：方便转为二叉树操作，查找孩子。
  缺点：难以查找双亲，可增加 partent 指针

§5 树与二叉树

26. 树与二叉树的转换

树	对应二叉树
根	根
第一个孩子	左孩子
下一个兄弟	右孩子

27. 遍历关系

树	森林	二叉树
先根遍历	先序遍历	先序遍历
后根遍历	中序遍历	中序遍历

28. 树的孩子兄弟链表示法与二叉树的二叉链表示法，本质上是一样的，只是解释不同。即树可用二叉树唯一表示。

29. 区别：

二叉树	树
度至多为 2	无此限制
有左右子树之分	无此限制
允许为空	一般不允许为空

§6 二叉排序树

30. 二叉排序树 (BTS)：特点：左＜根＜右

31. 二叉排序树非递归查找

BSTNode *BST_Search(Btree T,ElemType key,BSTNode *&P){ 
  P=Null;
  while(T!=Null&&key!=T->data){
    P=T;
    if(key<T->data)
    	T=T->lchild;
    else T=T-rchild;
  }return T;
}//查找并返回值为key的结点指针

32. 二叉排序树插入

int BST_Insert(BiTree &T,KeyType k){
	if(T==Null){
		T=(BiTree)malloc sizeof(BSTNode);
		T->key=k;T->lchild=T->rchild=Null;
		return true;
	}else if(k=T->key) return false;
	else if(k<T->key) return BST_Insert(T->lchild,k);
	else return BST_Insert(T->lchild,k);
}

33. 二叉排序树的构造

void Creat_BST(BiTree &T,KeyType str[],int n){
	T=Null;int i=0;
	while(i<n){
		BST_Insert(T,str[i]);
		i++;
	}
}

34. 平衡二叉树

构造方法
LL（右单旋转）	A 的左孩子的左子树插入了新结点
RR（左单旋转）	A 的右孩子的右子树插入了新结点
LR（左右旋转）	A 的左孩子的右子树插入了新结点
RL（右左旋转）	A 的右孩子的左子树插入了新结点

35. 平衡二叉树最大深度为 $O (log_2n)$，平均查找长度 $O (log_2n)$

36. 哈夫曼树：树的带权路径长度最小。

37. 构造：“每次取两个最小的树组成哈夫曼树”。

38. 哈夫曼编码：向左分支为 0，向右分支为 1。

39. 若二叉树采用二叉链表存储，要交换其所有分支结点左右子树的位置，利用后序遍历方法最合适。

40. 二叉树线索后，仍不能有效求解，后序线索二叉树中求后序后继。

41. $ 带权路径长度 =\sum_{i=1}^n 叶结点权值 × 到根节点的距离 \ = 所有分支结点权值之和 - 根节点权值 $

§7 线性表、树、广义表

42. 总说

• 线性表属于约束性最强的线性结构，在非空线性表中，只有一个 “第一个元素”，也只有一个 “最后一个” 元素。出第一个元素外，每个元素都有唯一前驱，除最后一个元素外，每个元素都有唯一后继。
• 树是一种层次结构，有且仅有一个根结点，每个结点可以有多个子女，但只有一个双亲（除根外），从这一意义上说存在一（双亲）对多（子女）的关系。
• 广义表元素既可以是原子，也可以是子表。子表可以为它表共享。

43. 区别与联系：从表中套表意义上说，广义表也是层次结构。从逻辑上讲，树与广义表均属于非线性结构。但在以下意义下，又变为线性结构，如：度为 1 的树，以及元素都是原子的广义表。另外，广义表从元素之间的关系可以看作前驱和后继，也符合线性表，但这时元素有原子，也有子表，即元素不属于同意数据对象。
44. 计算树的表达式求值

• 1）对该二叉树进行后序遍历，得到表达式的后序遍历序列，再按后缀表达式求值；
• 2）递归求出最自述表达式的值，再递归求出右子树表达式的值，最后按根结点运算符（+、-、×、÷）等进行最后求值。