数据结构学习笔记＜4＞ 二叉树

# 一、什么是树

# 1. 树的定义

树（Tree）：n（n≥0）个结点构成的有限集合。
当 n=0 时，称为空树；
对于任一棵非空树（n>0）, 它具备以下性质：

1. 树中有一个称为 “根（Root）” 的特殊结点，用 r 表示。
2. 其余结点可分为 m（m>0）个互不相交的有限集 T1，T2，……，Tm, 其中每个集合本身又是一棵树，称为原来树的 “子树（SubTree）”。
3. 子树是不相交的
4. 除了根结点外，每个结点有且仅有一个父结点；
5. 一个 N 个结点的树有 N-1 条边。

# 2. 树的一些基本术语

1. 结点的度（Degree）： 结点拥有子结点的数量
2. 树的度： 最大的结点的度称为树的度
3. 叶结点（Leaf）： 度为 0 的结点
4. 父结点（Parent）： 如果有上一个结点，则称这个上一结点是它的父结点，如果没有上一结点，则这个属性则无父结点。
5. 子结点（Child）： 若 A 结点是 B 结点的父结点，则称 B 结点是 A 结点的子结点；子节点也称孩子结点
6. 兄弟结点（Sibling）： 具有同一父结点的各结点彼此是兄弟结点。
7. 路径和路径长度： 从结点 n1 到 nk 的路径为一个节点序列 n1，n2，……，nk，ni 是 ni+1 的父结点。路径所包含边的个数为路径的长度
8. 祖先结点（Ancestor）： 沿树根到某一结点路径上的所有节点都是这个结点的祖先结点
9. 子孙结点（Descendant）： 某一结点的子树中所有结点是这个结点的子孙
10. 结点的层次（Level）： 规定根结点在 1 层，其它任一结点的层数是其父结点的层数加 1。
11. 树的深度（Depth）： 树中所有结点的最大层次是这棵树的深度。
12. 森林： m 棵不相交的树的集合

# 二、树的表示

# 1. 儿子 - 兄弟表示法

# 三、二叉树

# 1. 定义

二叉树 T: 一个有穷的结点集合。
这个结点可以为空
若不为空，则它是由根结点和称为其左子树 TL 和右子树 TR 的两个不相交的二叉树组成
二叉树具体五种基本形态 a 空树 b 只有一个结点 c 有一个结点和左子树 d 有一个结点和左子树 e 有一个结点和左右子树

PS：二叉树的子树有左右顺序之分

几种特殊二叉树

二叉树的抽象数据类型定义
类型名称：二叉树
数据对象集：一个有穷的结点集合。
若不为空，则由根结点和其左、右二叉子树组成。
操作集：BT∈BinTree，Item∈ElementType，重要操作有：

1. Boolean IsEmpty (BinTree BT); // 判别 BT 是否为空
2. void Traversal (BinTree BT); // 遍历，按某顺序访问某个结点；
3. BinTree CreatBinTree (); // 创建一个二叉树

常用的遍历方法有：

• void PreOrderTraversal(BinTree BT); // 先序 --- 根、左子树、右子树
• void InOrderTraversal(BinTree BT); // 中序 --- 左子树、根、右子树
• void PostOrderTraversal(BinTree BT); // 后序 --- 左子树、右子树、根
• void LevelOrderTraversal(BinTree BT); // 层次遍历，从上到下、从左到右

# 2. 二叉树的几个重要性质

• 一个二叉树第 i 层的最大节点数为 2^i-1，i≥1。
• 深度为 k 的二叉树有最大结点总数为 2^k-1，k≥1。
• 对任何非空二叉树 T，若 n0 表示叶结点的个数、n2 是度为 2 的非叶结点个数，那么两者满足关系 n0=n2+1。
• 具有 n 个结点的完全二叉树的深度 k 必为 log₂n+1

# 3. 二叉树的存储结构

# 1、顺序存储结构

完全二叉树：按从上至下、从左到右顺序存储 n 个结点的完全二叉树的结点父子关系

• 非根结点（序号 i > 1）的父结点的序号是 [i / 2] ;(向下取整)

• 结点（序号为 i）的左孩子的序号是 2i (2i ≤ n，否则没有左孩子)

• 结点（序号为 i）的右孩子的序号是 2i+1 (2i + 1 ≤ n，否则没有右孩子)

  一般二叉树也可采用这种顺序存储结构，但是会造成空间浪费

  满二叉树：除最后一层无任何子节点外，每一层上的所有结点都有两个子结点的二叉树，区别于完全二叉树

# 2、链式存储

# (1) 定义

typedef struct TreeNode *BinTree;

typedef BinTree Position;

struct TreeNode {

  ElementType Data;

  BinTree Left;

  BinTree Right;

}

# (2) 遍历（递归实现）

# 先序遍历

1. 先访问根结点；
2. 先序遍历其左子树；
3. 先序遍历其右子树。

void PreOrderTraversal(BinTree BT) {

 if(BT) {

  printf("%d", BT->Data);

  PreOrderTraversal( BT->Left);

  PreOrderTraversal( BT->Right);

 }

}

# 中序遍历

1. 中序遍历其左子树
2. 访问根结点
3. 中序遍历其右子树。

void InOrderTraversal(BinTree BT) {

 if(BT) {

  InOrderTraversal( BT->Left);

  printf("%d", BT->Data);

  InOrderTraversal( BT->Right);

 }

}

# 后序遍历

1. 后序遍历其左子树
2. 后序遍历其右子树。
3. 访问根结点

void PostOrderTraversal(BinTree BT) {

 if(BT) {

  PostOrderTraversal( BT->Left);

  PostOrderTraversal( BT->Right);

  printf("%d", BT->Data);

 }

}

# (2) 遍历（非递归实现）

基本思路：使用堆栈或队列

# 中序遍历非递归遍历算法

• 遇到一个结点，就把它压栈，并去遍历它的左子树；
• 当左子树遍历结束后，从栈顶弹出这个结点并访问它；
• 然后按其右指针再去中序遍历该结点的右子树。

void InOrderTraversal(BinTree BT) {

 BinTree T = BT;

 Stack S = CreatStack(MaxSize);// 创建并初始化堆栈 S

 while( T || !IsEmpty(S) ) {

  while(T) {// 一直向左并将沿途结点压入堆栈

   Push(S, T);

   T = T->Left;

  }

  if( !IsEmpty(S) ) {

   T = Pop(S); // 结点弹出堆栈

   printf("%5d", T->Data);// 访问结点

   T = T->Right;// 转向右子树

  }

 }

}

# 层序遍历

• 需要一个存储结构保存暂时不访问的结点（堆栈、队列）
  队列实现：遍历从根节点开始，首先将根节点入队，然后开始执行循环：结点出队、访问该节点、其左右儿子入队
  1. 根结点入队；
  2. 从队列中取出一个元素；
  3. 访问该元素所指结点；
  4. 若该元素所指结点的左、右孩子结点非空，将其左、右孩子的指针顺序入队。

void LevelOrderTraversal(BinTree BT) {

 Queue Q;  BinTreee T;

 if ( !BT ) return; // 若是空树直接返回

 Q = CreateQueue(MaxSize);// 创建并初始化队列 Q

 AddQ(Q, BT);

 while( !IsEmpty(Q) ) {

  T = DeleteQ(Q);

  printf("%d\n", T->Data);// 访问结点

  if(T->Left) AddQ(Q, T->Left);// 将左孩子放入队列

  if(T->Right) AddQ(Q, T->Right);// 将右孩子放入队列

 }

}

补充知识
数据管理的基本操作之查找：根据某个给定关键字 K，从集合 R 中找出关键字与 K 相同的记录，分为静态查找与动态查找
静态查找：集合中记录是固定的，没有插入和删除操作，只有查找。
法 1：顺序查找 （哨兵概念：在数组的边界上设一个值，碰到哨兵循环就可以结束了，可以少一个分支判断）复杂度 O (n);
法 2：二分查找 （前提：数组连续且有序）
动态查找：集合中记录时动态变化的，除查找外还可能发生插入和删除