树的定义

树是一种非线性的数据结构。它是n个结点的有限集合，一棵非空树具有以下的特点：
（1）有且只有一个称为根(root)的结点。
（2）当n>1时，其余n-1个结点可以划分为m个有限集合T1、T2......Tm，且这m个有限集合不相交，我们称其中的Ti为根的子树。

当n=0时，称为空树；当n>0时，称为非空树。树的逻辑结构如图所示：

树

在介绍树之前，需要先了解一些有关树的概念：
树的节点：指包含一个数据元素以及指向其他结点的分支信息。
结点的度：结点子树的个数称为结点的度。例如图中B有2棵子树，则B的度数为2；E的子树为0，它的度数就是0。
树的度：树中各结点度的最大值就是树的度。
孩子与双亲：结点的子树的根称为孩子，而该结点称为双亲。
兄弟：同一个双亲的孩子之间称为兄弟。
树的层次：从根结点起，根结点为第1层，根结点的孩子结点为第2层，以此类推。
数的深度：树中所有结点的层次最大值称为树的深度。
有序树与无序树：如果树中各棵子树之间是有先后次序的称为有序树，反之则称为无序树。
森林：m棵互不相交的树构成一个森林。

树的抽象类型定义如下：

Tree ADT{
    数据对象；
    数据关系；

    基本操作：
        InitTree(&T)
            操作结果：将T初始化为一棵空树
        CreateTree(&T)
            初始条件：树T不存在
            操作结果：创建树T
        DestroyTree(&T)
            初始条件：树T不存在
            操作结果：销毁树T
        TreeEmpty(T)
            初始条件：树T存在
            操作结果：如果T是空树，则返回1；否则返回0
        Root(T)
            初始条件：树T存在，e是T中的某个结点
            操作结果：如果树非空，则返回树的根结点，否则返回NULL
        Parent(T,e)
            初始条件：树T存在
            操作结果：如果e不是根结点，则返回该结点的双亲，否则返回NULL
        FirstChild(T,e)
            初始条件：树T存在，e是T中的某个结点
            操作结果：如果e不是叶子结点，则返回该结点的第一个孩子结点，否则返回NULL
        NextSibling(T,e)
            初始条件：树T存在，e是T中的某个结点
            操作结果：如果e不是其双亲结点的最后一个孩子结点，则返回它的下一个兄弟结点，否则返回NULL
        InsertChild(&T,p,Child)
            初始条件：树T存在，p指向T中的某个结点
            操作结果：在树T中，指针p指向T中的某个结点，将非空树child插入T中，使child为p指向的结点的子树
        DeleteChile(&T,p,i)
            初始条件：树T存在，p指向T中的某个结点
            操作结果：在树T中，指针p指向T的某个结点，将p所指向的结点的第i棵子树删，若删除成功返回1，否则返0
        TraverseTree(T)
            初始条件：树T存在
            操作结果：按照某种次序对树中每个结点进行访问（如输出），即树的遍历
        TreeDepth(T)
            初始条件：树T存在
            操作结果：如果树非空，返回树的深度，如果是空树，则返回0
}

树的存储结构

1. 双亲表示法

双亲表示法是利用一组连续的存储单元存储树的每一个结点，并利用一个指示器表示结点的双亲结点在树中的相对位置。如图所示：

data	parent

其中data存放数据元素信息，parent存放该结点的双亲在数组中的下标（我们将树的根结点的双亲位置用-1来表示)。

采用双亲表示法的树的类型定义如下：

#define MaxSize 200
typedef struct{  //定义结点的结构
    DataType data;  
    int parent;
}PNode;
typedef struct{  //双亲表示法类型的定义
    PNode node[MaxSize];
    int num;  //结点的个数
}PTree;

2. 孩子表示法

孩子表示法是将双亲结点的孩子构成一个链表，然后让双亲结点指向这个链表，这样的链表称为孩子链表。为此，需要设计两个结点结构，一个是孩子链表的结点，其中child是数据域，next是指针域；另一个则是表头数组的表头结点，data存储结点的数据信息，firstchild存储孩子链表的头指针。

树的孩子表示法的类型定义如下：

#define MaxSize 200
typedef struct CNode{
    int child;
    struct CNode *next;  //指向下一个结点
}ChildNode;
typedef struct{
    DataType data;
    ChildNode *firstchild;  //孩子链表指针
}DataNode;
typedef struct{
    DataNode node[MaxSize];  //结点的个数，根结点在顺序表中的位置
    int num,root;
}CTree;

---

二叉树的相关概念

二叉树的定义

二叉树是由n个结点构成的另一种树结构。它的特点是每个结点最多只有两棵子树，并且二叉树是有左右之分的（左孩子和右孩子），次序不能颠倒。

在二叉树中，任何一个结点的度只可能是0、1或2。

二叉树

下面介绍两种特殊的二叉树：

1.满二叉树

每层结点都是满的二叉树称为满二叉树，即在满二叉树中每一层的结点都具有最大的结点个数。在满二叉树中每个结点的度只能为0或2，不会出现度为1的结点。

满二叉树

2.完全二叉树

对满二叉树的结点进行连续编号，约定从根结点开始，自上而下，从左到右进行编号。在一棵具有m个结点的二叉树中，若每个结点都与满二叉树的编号从1到m一一对应时，则称为完全二叉树。

完全二叉树

二叉树的性质

二叉树具有以下重要的性质：
性质一：二叉树的第k层上至多有2^(k-1)个结点。
性质二：深度为k的二叉树最多有2^k-1个结点。
性质三：对于任何一棵二叉树T，如果度为0结点数为n0，度为2的结点数为n2，则有n0=n2+1。
性质四：具有n个结点的完全二叉树的深度为[log2( n)]+1（[x]表示不大于x的最大整数）。

二叉树的存储表示与实现

二叉树具有顺序存储和链式存储两种存储方式，其中链式存储是其最常用的方式。

1. 二叉树的顺序存储

若对一棵二叉树按照层次从上到下，从左到右进行编号，则对于完全二叉树来说每个结点的编号可以通过二叉树的性质计算得到，因此完全二叉树中的结点可以依次存放在一维数组中。

完全二叉树的顺序存储

按照同样的方法，若将非完全二叉树的结点也按照同样的方式进行编号存放在一维数组中。为了能够正确反映二叉树结点之间的逻辑关系，还需要在一维数组中空出二叉树中不存在的结点位置（我这里用^来表示）。

非完全二叉树 数组存储
可以看出如果采用顺序存储的方法，则对于许多的非完全二叉树来说构造数组是很浪费存储空间的。

2. 二叉树的链式存储

根据二叉树的定义，我们可以使用链表的方式来存储二叉树，即每个结点包括指向左孩子的指针域、数据域和指向右孩子的指针域。

链式存储

其中，data域存放某结点的数据信息；lchild与rchild分别存放指向左孩子和右孩子的指针，当左孩子或右孩子不存在时，相应指针域值为空（用符号∧或NULL表示）。利用这样的结点结构表示的二叉树的链式存储结构被称为二叉链表。

二叉链表
二叉树的链式存储的结点结构类型：

typedef struct Node{
    DataType data;  //数据域
    struct Node *lchild;  //左孩子结点
    struct Node *rchild;  //右孩子结点
}*BitTree,BitNode;

二叉树的基本操作的实现

（1）初始化二叉树InitBitTree

void InitBitTree(BitTree *T){
    *T=NULL;
}

（2）创建二叉树CreateBitTree

void CreateBitTree(BitTree *T){
    DataType ch;
    cin>>ch;
    if(ch=='#'){
        *T=NULL;
    }
    else{
         *T=(BitTree)malloc(sizeof(BitNode));  //开始生成根
        if(!(*T)){  //如果生成根失败则退出
            exit(-1);
        }
        (*T)->data=ch;  //给数据域赋值
        CreateBitTree(&((*T)->lchild));  //构造左子树（递归）
        CreateBitTree(&((*T)->rchild));  //构造右子树
    }
}

（3）销毁二叉树DestroyBitTree

void DestroyBitTree(BitTree *T){
    if(*T){
        if((*T)->lchild){  //采用递归的方式
            DestroyBitTree((*T)->lchild);
        }
        if((*T)->rchild){
            DestroyBitTree((*T)->rchild);
        }
        free(*T);
        *T=NULL;
    }
}

（4）二叉树的插入InsertChild

int InsertChild(BitTree p,int LR,BitTree c){
//p指初始的树，LR指插入的左右位置，c为要插入的结点
    if(p){  //如果p指向的二叉树非空
        if(LR==0){  //如果LR为0，则代表插入的是左边
            c->rchild=p->lchild;  //p原来的左子树成为c的右子树
            p->lchild=c;  //p的左子树成为结点c
        }
    }
    else{  //LR为1，则代表插入的是右边
        c->rchild=p->rchild;  //p原来的右子树成为c的右子树
        p->rchild=c;  //p的右子树成为c
    }
}

（5）删除二叉树的子树DeleteLeftChild

void DeleteLeftChild(BitTree p,int LR){
    if(p){
        if(LR==0){  //如果LR为0则删除左子树
            DestroyBitTree(&(p->lchild));
        }
        else{  //LR为1则删除右子树
            DestroyBitTree(&(p->rchild));
        }
    }
}

遍历二叉树

遍历二叉树是指按照某种规律对二叉树的每个结点进行访问，使得每个结点仅被访问一次的操作。二叉树的遍历不同于线性表的遍历，对于二叉树来说，每个结点有两棵子树，因而需要一种规律，使得二叉树的结点能够排列在一个线性队列上，从而便于遍历。如果用D、L、R遍历根结点，遍历左子树和遍历右子树，如果限定先左后右的次序，就会有3中遍历方案:DLR（先序遍历）、LDR（中序遍历）和LRD（后序遍历）。

下面来分别介绍这3种遍历方式。

1. 先序遍历二叉树

先序遍历的递归定义是：如果二叉树为空，则不执行操作。反之则先访问根结点，然后先序遍历左子树，最后先序遍历右子树。

先序遍历二叉树的递归算法如下：

void PreOrderTraverse(BitTree T){
    if(T){
        printf("%c",T->data);  //访问根结点
        PreOrderTraverse(T->lchild);  //先序遍历左子树
        PreOrderTraverse(T->rchild);  //先序遍历右子树
    }
}

2. 中序遍历二叉树

中序遍历的递归定义是：如果二叉树为空，则不执行操作。反之则先中序遍历左子树，然后访问根结点，最后中序遍历右子树。

中序遍历二叉树的递归算法如下：

void InOrderTraverse(BitTree T){
    if(T){
         InOrderTraverse(T->lchild);  //中序遍历左子树
         printf("%c",T->data);  //访问根结点
         InOrderTraverse(T->rchild);  //中序遍历右子树
    }
}

3. 后序遍历二叉树

后序遍历的递归定义是：如果二叉树为空，则不执行操作。反之则先后序遍历左子树，然后后序遍历右子，最后树访问根结点。

后序遍历二叉树的递归算法如下：

void PostOrderTraverse(BitTree T){
    if(T){
         PostOrderTraverse(T->lchild);  //后序遍历左子树
         PostOrderTraverse(T->rchild);  //后序遍历右子树
         printf("%c",T->data);  //访问根结点
    }
}

4.层次遍历二叉树

层次遍历输出二叉树的结点可以利用队列来实现，即先定义一个队列queue用来存放结点的信息。从根结点出发，依次把每一层的结点入队，当一层结点入队完毕之后，将队头元素出队，输出该结点，然后判断结点是否存在左右孩子，如果存在，则将左右孩子入队。重复执行以上操作直到队空为止。

层次遍历输出二叉树的算法如下：

void LevelPrint(BiTree T){
    BiTree queue[MaxSize];  //先创建一个队列
    BitNode *p;  //创建一个头结点
    int front,rear;  //队头和队尾
    front=rear=-1;
    rear++;   //rear=0
    queue[rear]=T;  //设置头
    while(front!=rear){  //当队列不为空时
        front=(front+1)%MaxSize;  //头结点后移
        p=queue[front];  //取出队头的元素然后输出
        printf("%c",p->data);
        if(p->lchild!=NULL){  //当左孩子不为空时
            rear=(rear+1)%MaxSize;  //尾结点后移
            queue[rear]=p->lchild;  //插入头结点的左孩子
        }
        if(p->rchild!=NULL){  //当右孩子不为空时同理
            rear(rear+1)%MaxSize;
            queue[rear]=p->rchild;
        }
    }
}

遍历二叉树的应用

1.计算二叉树的所有结点数

计算二叉树的所有结点数要用递归来进行计算，计算时主要有3中情况：
（1）当二叉树为空时其结点为0。
（2）当二叉树只有根结点，即左右子树均为空时，二叉树的结点数为1。
（3）其他情况下，就是将二叉树的左子树结点数加上右子树结点数后再加1，就是二叉树的所有结点数。

代码实现如下：

int AllNodes(BitTree T){
    if(!T){  //空树则返回0
        return 0;
    }
    else if(!T->lchild&&!T->rchild){  //如果只有根结点则返回1
        return 1;
    }
    else{
        return AllNodes(T->lchild)+AllNodes(T->rchild)+1;  //左右结点数相加再加1
    }
}

2.计算二叉树的深度

计算二叉树的深度要分3种情况：
（1）当二叉树为空时其深度为0。
（2）当二叉树只有根结点，即左右子树均为空时，二叉树的深度为1。
（3）其他情况下，先求出二叉树的左子树的最大值，再求出二叉树右子树的最大值，选出两者之中的最大值再加1就是二叉树的深度。

算法实现如下：

int BitTreeDepth(BitTree T){
    if(T==NULL){
        return 0;
    }
    else{
        return BitTreeDepth(T->lchild) > BitTreeDepth(T->rchild) ? 1+BitTreeDepth(T->lchild) : BitTreeDepth(T->rchild)+1;
    }
}

3.二叉树的查找

二叉树的查找是一种动态的查找方法，它的思想是遍历二叉树的左右子树，当查找到与要求查找的数相同时，就返回二叉树的结点指针。

查找的算法如下：

BiTree SearchBst(BiTree T,DataType x){
    if(T->data==x) return T;
    else{
        if(T->lchild) SearchBst(T->lchild,x);  //查找左子树
        if(T->rchild) SearchBst(T->rchild,x);  //查找右子树
    }

最优二叉树——哈夫曼树

1.哈夫曼树的定义

在介绍哈夫曼树之前，先介绍几个与哈弗曼树有关的定义。
（1）路径与路径长度：路径是指在树中，从一个结点到另一个结点所走过的路程。路径长度是一个结点到另一个结点的分支数目。树的路径长度是指从树的树根到每一个结点的路径长度的和。
（2）树的带权路径长度：在一棵树中，如果其结点上附带有一个权值，通常把该结点的路径长度与该结点上的权值之积称为该结点的带权路径长度。关于权的定义可以看这里。我们用WPL来表示带权路径长度。

求带权路径长度的例子

哈弗曼树就是带权路径长度最小的树，也称为最优二叉树。