每个结点最多有俩孩子（二叉树中不存在度大于2的结点）。
二叉树可以是空集合，根可以有空的左子树和空的右子树。
二叉树有左右之分，次序不能颠倒。
二叉树的性质：
1.在二叉树的第i层上至多有2^（i-1）个结点（i>1）。
2.深度为k的二叉树至多有2^k-1个结点（k>=1）。
3.对任何一颗二叉树T，如果其叶子数为n0，度为2的结点数为n2，则n0=n2+1.
4. 具有n个结点的完全二叉树的深度为(log2N)+1。

注意：二叉树不是树的特殊情况，它们是两个概念

5.2.2几种特殊的二叉树

满二叉树：一颗深度为k且有2^k-1个结点的二叉树称为满二叉树。每一层上的结点数都达到最大。叶子全部在最低层。
完全二叉树：深度为k的具有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号为1~n的结点一一对应时，称之为完全二叉树。
二叉排序树
平衡二叉树

5.2.3二叉树的存储结构

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

#define MaxSize 100

struct TreeNode{
   ElemType value; //结点中的数据元素
   bool isEmpty;   //结点是否为空
}

main(){
   TreeNode t[MaxSize];
   for (int i=0; i<MaxSize; i++){
      t[i].isEmpty = true;
   }
}

链式存储

//二叉树的结点

struct ElemType{
   int value;
};

typedef struct BiTnode{
   ElemType data;          //数据域
   struct BiTNode *lchild, *rchild; //左、右孩子指针
}BiTNode, *BiTree;

//定义一棵空树
BiTree root = NULL;

//插入根节点
root = (BiTree) malloc (sizeof(BiTNode));
root -> data = {1};
root -> lchild = NULL;
root -> rchild = NULL;

//插入新结点
BiTNode *p = (BiTree) malloc (sizeof(BiTNode));
p -> data = {2};
p -> lchild = NULL;
p -> rchild = NULL;
root -> lchild = p; //作为根节点的左孩子

5.3二叉树的遍历和线索二叉树

5.3.1二叉树的遍历

先序遍历（根左右）

若二叉树为空，不用操作
若二叉树非空：
- 访问根节点
- 先序遍历左子树
- 先序遍历右子树

typedef struct BiTnode{
   ElemType data;          
   struct BiTNode *lchild, *rchild; 
}BiTNode, *BiTree;

void PreOrder(BiTree T){
   if(T!=NULL){
      visit(T);                 //访问根结点
      PreOrder(T->lchild);      //递归遍历左子树
      PreOrder(T->rchild);      //递归遍历右子树
   }
}

中序遍历（左根右）

若二叉树为空，不用操作
若二叉树非空：
- 先序遍历左子树
- 访问根节点
- 先序遍历右子树

typedef struct BiTnode{
   ElemType data;          
   struct BiTNode *lchild, *rchild; 
}BiTNode, *BiTree;

void InOrder(BiTree T){
   if(T!=NULL){
      InOrder(T->lchild);       //递归遍历左子树
      visit(T);                 //访问根结点
      InOrder(T->rchild);       //递归遍历右子树
   }
}

后续遍历（左右根）

若二叉树为空，不用操作
若二叉树非空：
– 先序遍历左子树
– 先序遍历右子树
– 访问根节点

typedef struct BiTnode{
   ElemType data;          
   struct BiTNode *lchild, *rchild; 
}BiTNode, *BiTree;

void PostOrder(BiTree T){
   if(T!=NULL){
      PostOrder(T->lchild);       //递归遍历左子树    
      PostOrder(T->rchild);       //递归遍历右子树
      visit(T);                 //访问根结点
   }
}

二叉树的层次遍历
算法思想：

初始化一个辅助队列
根节点入队
若队列非空，则队头结点出队，访问该结点，依次将其左、右孩子插入队尾（如果有的话）
重复以上操作直至队列为空

由遍历序列构造二叉树

先序序列 + 中序序列
后序序列 + 中序序列
层序序列 + 中序序列
key: 找到树的根节点，并根据中序序列划分左右子树，再找到左右子树根节点、

5.3.2线索二叉树

线索二叉树的概念与作用
在二叉树的结点上加上线索的二叉树称为线索二叉树，对二叉树以某种遍历方式（如先序、中序、后序或层次等）进行遍历，使其变为线索二叉树的过程称为对二叉树进行线索化。
线索二叉树的存储结构

中序线索二叉树——线索指向中序前驱、中序后继

//线索二叉树结点
typedef struct ThreadNode{
   ElemType data;
   struct ThreadNode *lchild, *rchild;
   int ltag, rtag;                // 左、右线索标志
}ThreadNode, *ThreadTree;

先序线索二叉树——线索指向先序前驱、先序后继
后序线索二叉树——线索指向后序前驱、后序后继

二叉树的线索话

中序线索化

typedef struct ThreadNode{
   int data;
   struct ThreadNode *lchild, *rchild;
   int ltag, rtag;                // 左、右线索标志
}ThreadNode, *ThreadTree;

//全局变量pre, 指向当前访问的结点的前驱
TreadNode *pre=NULL;

void InThread(ThreadTree T){
    if(T!=NULL){
        InThread(T->lchild);    //中序遍历左子树
        visit(T);               //访问根节点
        InThread(T->rchild);    //中序遍历右子树
    }
}

void visit(ThreadNode *q){
   if(q->lchid = NULL){                 //左子树为空，建立前驱线索   
      q->lchild = pre;
      q->ltag = 1;
   }

   if(pre!=NULL && pre->rchild = NULL){ 
      pre->rchild = q;           //建立前驱结点的后继线索
      pre->rtag = 1;
   }
   pre = q;
}

//中序线索化二叉树T
void CreateInThread(ThreadTree T){
   pre = NULL;                //pre初始为NULL
   if(T!=NULL);{              //非空二叉树才能进行线索化
      InThread(T);            //中序线索化二叉树
      if(pre->rchild == NULL)
         pre->rtag=1;         //处理遍历的最后一个结点
   }
}

5.4树、森林

5.4.1树的存储结构

双亲表示法(顺序存储)：每个结点中保存指向双亲的指针
数据域：存放结点本身信息。
双亲域：指示本结点的双亲结点在数组中的位置。

#define MAX_TREE_SIZE 100  //树中最多结点数

typedef struct{      //树的结点定义
   ElemType data; 
   int parent;      //双亲位置域
}PTNode;

typedef struct{                   //树的类型定义
   PTNode nodes[MAX_TREE_SIZE];   //双亲表示
   int n;                         //结点数
}PTree;

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

本质：森林中各个树的根结点之间视为兄弟关系

将树转换成二叉树：

加线：在兄弟之间加一连线
抹线：对每个结点去除其与孩子之间的关系（第一孩子除外）
旋转：以树的根结点为轴心，顺时针转45度
（兄弟相连留长子）

5.4.3树、森林的遍历

树的遍历

先根遍历：若树非空，先访问根结点，再依次对每棵子树进行先根遍历；（与对应二叉树的先序遍历序列相同）

void PreOrder(TreeNode *R){
   if(R!=NULL){
      visit(R);    //访问根节点
      while(R还有下一个子树T)
         PreOrder(T);      //先跟遍历下一个子树
   }
}

5.5树与二叉树的应用

5.5.1二叉排序树（BST）

二叉排序树的定义
左子树结点值<跟结点值<右子树结点值
查找操作

typedef struct BSTNode{
   int key;
   struct BSTNode *lchild, *rchild;
}BSTNode, *BSTree;

//在二叉排序树中查找值为key的结点（非递归）
//最坏空间复杂度：O(1)
BSTNode *BST_Search(BSTree T, int key){
   while(T!=NULL && key!=T->key){        //若树空或等于跟结点值，则结束循环
      if(key<T->key)       //值小于根结点值，在左子树上查找
         T = T->lchild;
      else                  //值大于根结点值，在右子树上查找
         T = T->rchild;
   }
   return T;
}

//在二叉排序树中查找值为key的结点（递归）
//最坏空间复杂度：O(h)
BSTNode *BSTSearch(BSTree T, int key){
   if(T == NULL)
      return NULL;
   if(Kry == T->key)
      return T;
   else if(key < T->key)
      return BSTSearch(T->lchild, key);
   else 
      return BSTSearch(T->rchild, key);
}

5.5.2平衡二叉树（AVL）

平衡二叉树的定义
在插入和删除二叉树的结点时，要保证任意结点的左右子树的高度差的绝对值不超过1，将这样的树称为平衡二叉树。

//平衡二叉树结点
typedef struct AVLNode{
   int key;         //数据域
   int balance;     //平衡因子
   struct AVLNode *lchild; *rchild; 
}AVLNode, *AVLTree;

平衡二叉树的插入
插入新节点后如何调整“不平衡”问题
调整最小不平衡子树

5.5.3哈夫曼树

带权路径长度：从根节点到该结点之间的路径长度与该节点的权的乘积。
哈夫曼树的定义：带权路径最短的树。
哈夫曼树的构造（重点）：构造森林全是根,选用两小造新树，删除两小添新人，重复2、3剩单根。
哈杜曼编码（重点）：

文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/73272.html

数据结构和算法——树

5.1树的基本概念

5.1.1树的定义

5.1.2基本术语

5.1.3树的性质

5.2二叉树的概念

5.2.1 二叉树的定义与特性