树结构和线性结构的比较
线性结构	树结构
第一个数据元素无前驱	根节点无双亲
最后一个数据元素无后继	叶子结点无孩子
其他数据元素：一个前驱，一个后继	其他结点（中间结点）：一个双亲，多个孩子
一对一	一对多

2 二叉树

1 满二叉树：深度为k且有个结点的二叉树。

每一层上的结点数都是最大结点（每层都满）。
叶子结点全部都在最底层。

2 完全二叉树：深度为k的，具有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中的结点一一对应。

叶子只可能分布在层次最大的两层上。
对任一结点，若其右子树的最大层次为i，则其左子树的最大层次必为i或i+1。

【注】在满二叉树中，从最后一个结点开始，连续去掉任意个结点，即是一颗完全二叉树。

2.1 二叉树的性质

性质1 在二叉树的第i层上至多有 $2^{i-1}$ 个结点（i≥1）。

性质2 深度为k的二叉树至多有 $2^{k}-1$ 个结点（k≥1）。

性质3 对任何一颗二叉树T，如果其叶子数为，度为2的结点数为，则。

性质4 具有n个结点的完全二叉树的深度为。

（：称作x的底，表示不大于x的最大整数，反之，表示不小于x的最小整数）

（表明完全二叉树结点数n与深度k之间的关系）

性质5 如果有一棵有n个结点的完全二叉树的结点按层序编号，则对任一结点i（1≤≤n):

双亲(parent)是结点 i/2
左孩子(lchild)是结点 2i
右孩子(rchild)是结点 2i+1

（表明完全二叉树双亲结点编号与孩子结点编号之间的关系）

2.2 二叉树的存储结构

1）顺序存储结构

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

顺序存储缺点：深度为k的且只有k个结点的单支树需要长度为 $2^{k}-1$ 的一维数组。浪费空间，适合存放满二叉树和完全二叉树。?

2）链式存储结构（常用）

? ? ? 2.1 二叉链表

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

图?

? ? ? 2.2 三叉链表*?

typedef struct TriNode{
   TElemType data;                   //结点数据域
   struct TriNode *lchild,*parent,*rchild;    //双亲左右孩子指针
}TriNode,*TriTree;

2.3 遍历二叉树

规定先左后右，则有三种情况：

（若二叉树为空，则空操作），否则：

根左右，DLR——先序遍历(PrdOrderTraverse)；
左根右，LDR——中序遍历(InOrderTraverse)；
左右根，LRD——后序遍历(PostOrderTraverse)；

?由二叉树的先序序列和中序序列，或由二叉树的后序序列和中序序列可以确定唯一一颗二叉树。

?（由先序序列确定根，由中序序列确定左右子树）

【代码部分】

1）先序遍历

Status PrdOrderTraverse (BiTree T){
     if(T==NULL) return OK;             //若二叉树非空
     else
     {
         cout<<T->data;                 //访问根节点
         PrdOrderTraverse(T->lchild);   //先序遍历左子树
         PrdOrderTraverse(T->rchild);   //先序遍历右子树
     }
}

void Pre(BiTree *T){

? ? if(T!=NULL)

? ? {

? ? ?printf ("%d\t",T->data);

? ? ?pre (T->lchild);

? ? ?pre (T->rchild);

? ? }

}

2）中序遍历

Status InOrderTraverse (BiTree T){
     if(T==NULL) return OK;             //若二叉树非空
     else
     {
         InOrderTraverse(T->lchild);   //中序遍历左子树
         cout<<T->data;                 //访问根节点
         InOrderTraverse(T->rchild);   //中序遍历右子树
     }
}

3）后序遍历

Status PostOrderTraverse (BiTree T){
     if(T==NULL) return OK;             //若二叉树非空
     else
     {
         PostOrderTraverse(T->lchild);   //后序遍历左子树
         PostOrderTraverse(T->rchild);   //后序遍历右子树
         cout<<T->data;                 //访问根节点
     }
}

?从递归的角度看，去掉输出语句，三种算法完全相同，访问的路径相同，访问结点的时机和顺序不同。每个结点经过3次。

遍历算法的分析：

时间效率： $O_{\left ( n \right )}$ （每个结点只访问一次）
空间效率： $O_{\left ( n \right )}$ （栈占用的最大辅助空间）

4）中序遍历非递归算法

用栈的思想实现中序遍历。

基本思想：

建立一个栈；
根结点进栈，遍历左子树；
根结点出栈，输出根节点，遍历右子树。

Status InOrderTraverse (BiTree T){
    BiTree p;
    InitStack (S);
    p=T;                             //初始化一个空栈，指针p指向根节点
    q=new BiTNode;                   //申请结点q，用来存放栈顶出的元素
    while(p||!StackEmpty(S))         //所有元素出栈
    {
       if(p)                         //p非空
        {
          Push(S,p);                 //根指针进栈
          p=p->lchild;               //遍历左子树
        else                         //p非空
        {
          Pop(S,q);
          printf( "%c",q->data);
          cout<<q->data;             //访问根节点
          p=q->rchild;               //遍历右子树
        }
    }                                //while
    return OK;
}

5) 层次遍历

（用队列的思想实现遍历）

【基本思想】

根结点进队；
队不空时循环。从队列中列出一个结点*p，：若有左孩子结点，将左孩子入队；若有右孩子结点，则将右孩子入队。

【定义】?

typedef struct{
     BTNode data[MaxSize];   //存放队中元素
     int front,rear;         //队头和队尾指针
}SqQueue;                    //顺序循环队列类型

二叉树层次遍历算法：?

void LecelOrder(BTNode *b){
     BTNode *p;    SqQueue *qu;
     InitQueue(qu);

2.4 二叉树遍历的应用

1）建立二叉链表

按先序遍历序列建立二叉树的二叉链表。? ? ? ? ? ? ? ? ??

?【例】已知先序序列为：ABCDEF:

? ABC##DE#G##F###

Status CreateBiTree(BiTree &T){
   cin>>ch;
   if(ch=="#") T=NULL;
   else {
         if (!(T=(BiTNode*)malloc(sizeof(BiTNode))))
         T=new BiTNode;       //
         T->data=ch;
         CtrateBiTree(T->lchild);   //
         CtrateBiTree(T->rchild);   //
        }
}

2）复制二叉树

【算法步骤】

如果是空树，递归结束；否则：

申请一个新结点空间，复制根节点。
递归复制左子树。
递归复制右子树。

Status CreateBiTree(BiTree &T){

3）计算二叉树深度

【算法步骤】

如果是空树，深度为0，递归结束，否则：

递归计算左子树的深度m；
递归计算右子树的深度n；
如果m大于n,二叉树的深度为m+1，否则为n+1。

Status CreateBiTree(BiTree &T){

4）计算二叉树结点总数

【算法步骤】

如果是空树，则结点个数为0；
否则，结点个数为左子树的结点个数+右子树的结点个数+1

Status NodeCount(BiTree &T){
   if(T=NULL)
      return 0;                           //空树结点为0
   else
       return NodeCount(T->lchild)+
              NodeCount(T->rchild)+1;     //结点个数=左子树结点个数+右子树结点个数+1
}

2.5?线索二叉树

利用二叉链表中的空指针域：

?如果某结点左孩子为空，则将空的左孩子指针域改为指向其前驱；
?如果某结点右孩子为空，则将空的右孩子指针域改为指向其后继；

对二叉链表中每个结点增设两个标志域ltag 和 rtag ：

ltag=0——lchild 指向该结点的左孩子
ltag=1——lchild 指向该结点的前驱
rtag=0——rchild 指向该结点的右孩子
rtag=1——rchild 指向该结点的后继

结点结构：

lchild

ltag

data

rtag

tchild

typedef struct BiThrNode
{
   int data;
   int ltag,rtag;                      //定义左右标志
   struct  BiThrNode *lchild,rchild;   //定义左右孩子指针
} BiThrNode, * BiThrTree;