1. 常用性质
2. 存储结构
- 2.1 顺序存储结构
- 2.2 链式存储结构
  - 2.2.1 二叉链表存储
  - 2.2.2 三叉链表
3. 遍历二叉树
4. 线索二叉树

1. 常用性质

性质1：二叉树第i层，至多有个结点()
性质2：深度为k的二叉树至多有个结点()
性质3：
性质4：具有n个结点的完全二叉树深度为
性质5：一颗有n个结点的完全二叉树，则对任一结点i有：
- 如果i=1，i是根节点无双亲；i>1双亲是
- 如果2i>n，该结点为叶子结点，无左孩子；否则左孩子为2i
- 如果2i+1>n，该结点为叶子结点，无右孩子;否则右孩子为2i+1

2. 存储结构

2.1 顺序存储结构

实现：按满二叉树的结点层次编号，依次存放二叉树中的数据元素。

#define MAXSIZE 100
//typedef int TElemType;
typedef TElemType SqBiTree[MAXSIZE];
SqBiTree bt;

缺点：结点间的关系蕴含在其存储位置中，浪费空间，尤其是左/右单支树。适合存满二叉树和完全二叉树。

2.2 链式存储结构

2.2.1 二叉链表存储

typedef struct BiNode{
    TElemType data;
    struct BiNode *lchild,*rchild;//左右孩子指针
}BiNode,*BiTree;

一般使用一个指针指向根节点，类似于链表的头指针。

练习
在n个结点的二叉链表中，有_个空指针域？

答案：n+1
分析：**n个结点，每个结点有两个指针域，所以一共有2n个指针域。除了根节点之外，其他n-1个结点每个都有一个双亲结点，也就是这n-1个结点每个占一个指针域，也就是有n-1个指针域不为空。所以问题就变成：
已知一共2n个指针域，有n-1个不为空，求空指针域
答案就是 🌲二叉树 - 图11

2.2.2 三叉链表

typedef struct TriTNode{
    TelemType data;
    struct TriTNode *lchild,*rchild,*parent;
}TriTNode,*TriTree;

3. 遍历二叉树

常见三种遍历方法：先序遍历、中序遍历、后序遍历

little tips：**

前缀表达式（波兰式），后缀表达式（逆波兰式）
若二叉树各结点值不同，前中后序序列都是唯一
有前中或者中后可唯一确定一棵二叉树

3.1 先/后序和中序确定唯一二叉树

点击查看【bilibili】

3.2 先中后序遍历

3.2.1 递归算法

时间复杂度O(n)
空间复杂度O(n)

#include <stdio.h>
#include <stdlib.h>
typedef char ElementType;
typedef struct TNode *Position;
typedef Position BinTree;
struct TNode{
    ElementType Data;
    BinTree Left;
    BinTree Right;
};
BinTree CreatBinTree(); /* 实现细节忽略 */
void InorderTraversal( BinTree BT );
void PreorderTraversal( BinTree BT );
void PostorderTraversal( BinTree BT );
void LevelorderTraversal( BinTree BT );
int main()
{
    BinTree BT = CreatBinTree();
    printf("Inorder:");    InorderTraversal(BT);    printf("\n");
    printf("Preorder:");   PreorderTraversal(BT);   printf("\n");
    printf("Postorder:");  PostorderTraversal(BT);  printf("\n");
    printf("Levelorder:"); LevelorderTraversal(BT); printf("\n");
    return 0;
}
/* 你的代码将被嵌在这里 */
//中序遍历
void InorderTraversal( BinTree BT ){
    if(BT != NULL){
        InorderTraversal(BT->Left);
        printf(" %c",BT->Data);
        InorderTraversal(BT->Right);
    }
}
//先序遍历
void PreorderTraversal( BinTree BT ){
    if(BT != NULL){
        printf(" %c",BT->Data);
        PreorderTraversal(BT->Left);
        PreorderTraversal(BT->Right);
    }
}
//后序遍历
void PostorderTraversal( BinTree BT ){
    if(BT != NULL){
        PostorderTraversal(BT->Left);
        PostorderTraversal(BT->Right);
        printf(" %c",BT->Data);
    }
}

3.2.2 非递归算法

中序遍历的非递归算法
基本思想是利用栈将访问到的根节点存储起来，在遍历到左子树为空的时候，出栈根节点并访问，然后再以相同的方式去访问右子树。

typedef struct TNode *Position;
typedef Position BinTree;
struct TNode{
    ElementType Data;
    BinTree Left;
    BinTree Right;
    int flag;
};
#include <stdio.h>
#include <stdlib.h>
typedef enum { false, true } bool;
typedef char ElementType;
typedef struct TNode *Position;
typedef Position BinTree;
struct TNode{
    ElementType Data;
    BinTree Left;
    BinTree Right;
    int flag;
};
/*------堆栈的定义-------*/
typedef Position SElementType;
typedef struct SNode *PtrToSNode;
struct SNode {
    SElementType Data;
    PtrToSNode Next;
};
typedef PtrToSNode Stack;
/* 裁判实现，细节不表 */
Stack CreateStack();
bool IsEmpty( Stack S );
bool Push( Stack S, SElementType X );
SElementType Pop( Stack S ); /* 删除并仅返回S的栈顶元素 */
SElementType Peek( Stack S );/* 仅返回S的栈顶元素 */
/*----堆栈的定义结束-----*/
BinTree CreateBinTree(); /* 裁判实现，细节不表 */
void InorderTraversal( BinTree BT );
void PreorderTraversal( BinTree BT );
void PostorderTraversal( BinTree BT );
int main()
{
    BinTree BT = CreateBinTree();
    printf("Inorder:");    InorderTraversal(BT);    printf("\n");
    printf("Preorder:");   PreorderTraversal(BT);   printf("\n");
    printf("Postorder:");  PostorderTraversal(BT);  printf("\n");
    return 0;
}
/* 你的代码将被嵌在这里 */
//中序遍历的非递归遍历
void InorderTraversal( BinTree BT ){
    BinTree t;
    Stack s = CreateStack();
    t = BT;
    //p和s不同时为空
    while(p||!IsEmpty(s)){
        if(p){
            Push(s,t);
            t = t->Left;
        }else{
            t = Pop(s);
            printf(" %c",t->Data);
            t = t->Right;
        }
    }
}

3.2.3 层次遍历

基本思想：用一个队列，先将根节点入队列，如果队列不为空的话，然后让根节点出队列，同时输出它并且让它的左结点和右结点分别入队（如果左右结点分别存在的话），重复这个过程。

void LevelorderTraversal( BinTree BT ){
    BinTree QueBT[985];
    int front = 0;
    int tail = 0;
    BinTree t = BT;
    //将头结点入队
    if(BT != NULL){
        QueBT[++tail] = t;
    }
    //队列不为空
    while(front != tail){
        //根节点出队
        t = QueBT[++front];
        //访问根节点
        printf(" %c",t->Data);
        //该结点的左结点入队
        if(t->Left != NULL){
            QueBT[++tail] = t->Left;
        }
        //该结点的右结点入队
        if(t->Right != NULL){
            QueBT[++tail] = t->Right;
        }
    }

3.3 二叉树的建立

根据一段带空结点的先序序列构建二叉树

本质还是递归

3.4 复制二叉树

本质还是递归……

3.5 计算二叉树的深度

思路：

如果是空树，则深度为0。

否则，递归计算左子树的深度为m，递归计算右子树的深度为n，最后深度为m与n中最大值+1

int dep(BinTree t){
  int m = 0;
  int n = 0;
  if(t == NULL){
      return 0;
  }else{
      m = dep(t->Left);
      n = dep(t->Right);
      if(m>n){
          return m+1;
      }else{
          return n+1;
      }
  }
}

3.6 求结点数和叶子结点数

求结点个数
思路：如果是空树，0。否则，结点个数 = 左子树的结点个数 + 右子树的结点个数 + 1；

int NodeCount(BinTree t){
  if(t == NULL){
      return 0;
  }else{
      return NodeCount(t->Left)+NodeCount(t->Right)+1;
  }
}

求叶子结点的个数
思路：空树为0，否则为左子树叶子结点个数 + 右子树叶子结点个数；

int LeadCount(BinTree t){
  if(t == NULL){
      return 0;
  }else if(t->Left == NULL && t->Right == NULL){//只有根结点
      return 1;
  }else{
      return LeadCount(t->Left) + LeadCount(t->Right);
  }
}

4. 线索二叉树

问题提出：
如何寻找特定遍历序列中二叉树结点的前驱结点和后继结点？
通过遍历查找————费时间
再增设前驱后继指针域————费空间
最优解决方案： 利用二叉链表中的空指针域

首先我们回顾一下前面的性质，二叉链表有n+1个指针域

线索二叉树是

如果某个结点的左孩子指针为空，让其指向其在特定序列中的前驱结点，
同理右孩子指向后继结点。
遍历序列首尾的结点指向头指针，
头指针左指针指向根节点，右指针指向尾结点

例如：
某二叉树如下

其中序遍历为：CBEGDFA
线索化之后为

为了区分某个结点的lchild和rchild指向的是孩子结点还是前驱或者后继结点，二叉链表结点增加两个遍历：ltag和rtag

所以现在结点应该为：

最终演示图