数据结构实验报告——二叉树

• 实验目的与要求
• 实验步骤与内容
• 问题与说明
• 备注
• 程序清单

实验目的与要求

1.了解树的概念

2.会使用树的基本操作

3.理解先序，中序，后序遍历的不同

4.理解树的递归和非递归，以及层次遍历方法

实验步骤与内容

树的概念

树是n个节点组成的集合T，n=0的称为空树。有且只有一个特殊的节点称为根节点，若n>1时，其余的节点被分成m个互不相交的子集，T1，T2，T3，T4…Tm，其中每个子集本身又是一颗树，称其为根的子树(Subtree).

基本术语

(1)结点(node)：一个数据元素，及其若干子树的分支;

(2)节点的度(dergee),树的度：节点所拥有的子树的棵数称为节点的度，树中节点度的最大值为树的度。

(3)叶子(leaf)节点：度为0的节点称为叶子节点。

(4)孩子(child)节点，双亲(parent)节点，兄弟节点。

(5)层次-堂兄弟节点：根节点层次为1，其余为双亲节点层次加 1。

(6)节点层次路径，祖先节点，子孙节点：从根开始，到达节点p所经过的所有节点为p的所有层次路径有且只有一条，p层次路径上的所有节点（p除外）都称为p的祖先，以某一节点为根的子树中的任意节点，称为该节点的子孙节点。

(7)树的深度（depth）：树中节点最大的层次值，又称高度。树的深度是指层次上是由上到下递增的，而树的高度，叶子节点的高度为一，双亲节点的高度为叶子节点加1，是从上往下递增的。树的高度等于根节点的高度，等于所有子节点高度最大值+1.
对于节点来说深度和高度不同，而树的深度和高度相同。

(8)有序树，无序树。

(9)森林（forest）：m棵互不相交的树的集合，将一棵树的根节点去掉剩下的就是森林。

树的表示形式

（1）倒悬树（最常用的表示形式）
（2）嵌套几何（自行想想文氏图）
（3）广义表
（4）凹入法

树的抽象数据类型

ADT Tree{
    数据对象D：具有相同数据类型的数据元素的集合
    数据关系R：若D为空集则称为空树...
}ADT Tree；

二叉树

二叉树的定义

Binary Tree:n=0为空树,(1)有且只有一根（2）n>1时，其余分成两个互不相交的子集，T1，T2分别为左右子树，二叉树的定义是递归的。

二叉树的基本形态

（1）空二叉树
（2）单节点二叉树
（3）右子树为空的二叉树
（4）左子树为空的二叉树
（5）左右都不为空

二叉树的性质

性质1：在非空二叉树中第i层上至多有2^(i-1)个节点

proof:

i=1时只有一个节点,成立;

i>1时处在第i-1层上至多有2^((i-1)-1)个节点

由归纳法可知i-1层上有2^(i-2)个节点,所以下一层节点数为两倍即2^(i-1).

性质2:深度为k的二叉树至多有2^k-1个节点

proof:

2^0+2^1+…+2^(k-1)=2^k-1;

性质3:对于任何一颗二叉树其叶子节点为n0,度为2的节点数为n2,n0=n2+1

proof:

设二叉树中度为1的节点为n1个,二叉树总结点数为N,则有N=n0+n1+n2,再看二叉树中节点的分支数,设B为二叉树中的分支总数,有N=B+1,而B=n1+2*n2即推出N=B+1=n+2*n2+1,结合总结点数可推出n0=n2+1。

性质4n个节点的完全二叉树深度为floor(log2n)+1.

满二叉树与完全二叉树:

Full Binary Tree:一颗深度为k且有2^k-1个节点的二叉树。

Complete Binary Tree:如果深度为k,由n个节点的二叉树,当且仅当每一个节点都与深度为k的满二叉树中编号从1到n的节点一一对应,该二叉树称为完全二叉树。深度为k的满二叉树中编号从1到n的前n个节点构成了一颗深度为k的完全二叉树（2^(k-1)≤n≤2^k-1）。

满二叉树的特点：每层MAX数，都有左右子树，编号从上到下，从左到右递增。

完全二叉树是满二叉树的一部分，满二叉树是完全二叉树的一种特例。

完全二叉树的特点：深度为k，则所有叶子节点都在第k或第k-1层，对于任意一节点，如果其右子树的最大层次为1，则左子树的最大为i或i-1。

proof：

假设深度为k的完全二叉树则根据性质2有2^(k-1)-1＜n≤2^k-1或2^(k-1)≤n<2^k.

取对数得k-1<log2n<k所以k=floor(log2n)+1另一种形式k=ceil(log2(n+1))。

性质5：若对一颗有n个节点的完全二叉树（深度为floor（log2n）+1）的节点按层（从第1层到第floor（log2n）+1层）自左至右进行编号，则对于编号为i（1≤i≤n）的节点：

（1）若i=1，则节点i是二叉树的根，无双亲节点；否则，若i＞1，其双亲节点floor（i/2）；

（2）如果2i>n，则节点i为叶子节点，无左孩子，否则，则其孩子节点是2i；

（3）如果2i+1>n，则节点i无右孩子；否则其右孩子节点编号是2i+1。

proof：

i=1时，由定义知，左孩子编号为2，右孩子节点为3；

2>n则二叉树左孩子不存在，若3>n则右孩子不存在。当2j+1≤n，右孩子节点为2j+1若2j+1＞n，则没有右孩子节点。

i=j+1时，由完全二叉树性质知（2j+1）+1=2（j+1）。

i＞1时设编号为i的节点的双亲节点的编号为m由（2）有左孩子i=2m即m=floor（1/2）右孩子i=2m+1，即m=floor((m-1)/2)i>1时双亲节点为floor（i/2）。

树的性质

性质1：树中节点数等于所有节点数的度数加1.

度之和等于分支数，分支数等于n-1，n=度之和+1

性质2：度为m的树中第i层至多有m^(i-1)个节点，这里有i≥1

性质3：高度为h的m次树至多有（m^n-1)/(m-1)个节点

性质4：具有n个节点的m次树的最小高度为ceil（logm（n(m-1)+1））。

二叉树的顺序和链式存储

1.顺序存储结构

类型定义：

#define MAX_SIZE 100
typedef Elemtype subitree[MAX_SIZE];

完全二叉树编号为i的节点在下标为i-1的数组元素中。一般二叉树，扩展成完全二叉树，最坏的情况下深度为k且只有k个节点的二叉树要2^k-1的一维数组。

2.链式存储结构

（1）节点的类型及定义

二叉节点

typedef struct BTNode {
    ElemType data;
    struct BTNode *Lchild,*Rchild;
}BTNode,*Btnode;

三叉链表

typedef struct BTNode3{
    ElemType data;
    struct BTNode3 *Lchild,*Rchild,*parent;
}BTNode3;

性质：若一个二叉树如果有n个节点，则二叉链表必须含有2n个指针域，其中必有n+1个空的链域。
证明：分支数B=n-1即非空链域有n个，空链域有2n-（n-1）=n+1个。

二叉树的遍历（Traversing Binary Tree）

按指定规律对每个节点访问一次且仅访问一次，对于线性结构来说遍历完全只有一条搜索路径。

二叉树的基本组成

root，Lchild，Rchild，依次遍历就是遍历了二叉树，可以产生六种不同的遍历方式LDR，RDL，DLR，DRL，LRD，RLD。
DLR为先序遍历，LDR为中序遍历，LRD为后序遍历。

二叉树表达式（a+b * (c-d)-e/f)

先序：- + a * b - c d / e f

中序：a + b * c - d - e / f

后序：a b c d - * + e f / -

先序遍历的算法

递归算法

void PreorderTraverse(BTNode *T){
    if(T!=NULL){
        visit(T->data);
        PerorderTraverse(T->Lchild);
        PerorderTraverse(T->Rchild);
    }
}

非递归算法

设T是指向二叉树根节点的指针变量，非递归算法是若二叉树为空，则返回，否则令p=T：

（1）访问p所指向的节点；

（2）q=p->Rchild，若q不为空则q进栈；

（3）p=p->Lchild，若p不为空，转（1），否则转（4）；

（4）退栈到p转（1）直到栈空为止。

#define MAX_NODE 50
void PreorderTraverse(BTNode *T){
    BTNode *Stack[MAX_NODE],*p=T,*q;
    int top =0;
    if(T==NULL) printf("Binary Tree is Empty!\n");
    else{
        do{
            visit(p->data);
            q=p->Rchild;
            if(q!=NULL) stack[++top]=q;
            p=p->Lchild;
            if(p==NULL){
                p=stack[top];
                top--;
            }
        }while(top>0);
    }
}

void PreOrder(BTNode *b){
    BTNode *St[MAXSIZE],*p;
    int top=-1;
    top++;
    St[top]=b;
    while(top>-1){
        p=St[top];
        top--;
        printf("%c",p->data);
        if(p->rchild!=NULL){
            top++;
            St[top]=p->rchild;
        }
        if(p->lchild!=NULL){
            top++;
            St[top]=p->lchild;
        }
    }
}

void Preorder2(BTNode) *b){
    BTNode *St[MAXSIZE],*p;
    int top=-1;
    p=b;
    while(top>-1 || p!=NULL){
        while(P!=NULL){
            printf("%c",p->data);
            top++;
            St[top]=p;
            p=p->Lchild;
        }
        if(top>-1){
            p=St[top];
            top--;
            p=p->Rchild;
        }
    }
}

中序遍历的算法

递归算法

void InorderTraerse(BTNode *T){
    if(T!=NULL){
        InorderTraverse(T->Lchild);
        visit(T->data);
        InorderTraverse(T->Rchild);
    }
}

非递归算法

设T是指向二叉树根节点的指针变量，非递归算法：

若二叉树为空，则返回；否则令p=T

（1）若p不为空，p进栈，p=p->Lchild；

（2）否则（即p为空），退栈到p，访问p所指向的节点；

（3）p=p->Rchild转到（1）；
直到栈空为止。

#define MAX_NODE 50
void InorderTraverse(BTNoode &T){
    BTNode *Stack[MAX_NODE],*p=T;
    int top=0,bool=1;
    if(T==NULL)
        printf("Binary Tree is Empty");
    else {
        do{
            while(p!=NULL){
                stack[++top]=p;
                p=p->Lchild;
            }
            if(top==0)
                bool=0;
            else {
                p=stack[top];
                top--;
                visit(p->data);
                p=p->Rchild;
            }
        }while(bool!=0)
    }
}

Status InorderTrsverse2(BiTree T,Status (*visit)(TElemType)){
    Sqstack S;
    BiTree p;
    InitStack(S);
    push(S,T);
    while(!stackEmpty(s)){
        while(OK==GetTop(S,p)&&p)
            push(S,q->Lchild);
        Pop(S,p);
        if(!stackEmpty(S)){
            Pop(S,p);
            if(ERROR==visit(p->data)) return ERROR;
            push(S,p->Rchild);
        }
    }
    return OK;
}

Status InorderTraverse3(BiTree T,Status (*visit)(TelemType)){
    SqStack S;
    BiTree p;
    InitStack(S);
    while(p||!stackEmpty(S)){
        if(p){
        push(S,p);
        p=p->Lchild);
        }else {
            pop(S,p);
            if(ERROR==visit(p->data)) return ERROR;
            p=p->Rchild;
    }
    return OK;
}

后序遍历的算法

递归算法

void PostorderTraverse(BTNode *T){
    if(T!=NULL){
        PostorderTraverse(T->Lchild);
        PostorderTraverse(T->Rcjild);
        visit(T->data);
    }
}

非递归算法

在后序遍历中，根节点总是最后被访问的，设立一个状态标志tag：

设立两个堆栈的S1，S2，S1保存节点，S2保存节点的状态tag，S1和S2共用一个栈顶的指针。
设T是指向根节点的指针，若BiTree为Empty，return，否则p=T；

（1）第一次经过根p不访问；p进栈S1，tag赋值0，进栈S2，p=p->Lchild；

（2）若p非空转到（1），否则取状态值tag；

（3）若tag，对S1不访问不出栈，修改tag=1，取S1栈顶元素右子树转（1）

（4）若tag=1，S1退栈访问节点，直到栈空。

#define MAX_NODE 50
void PostprderTraverse(BTNode *T){
    BTNode *S1[MAX_NODE],*p=T;
    int S2[MAX_NODE],top=0,bool=1;
    if(T==NULL)
        printf("Tree is Empty");
    else {
        do{
            while(p!=NULL){
                St[++top]=p;
                S2[top]=0;
                p=p->Lchid;
            }
            if(top==0) bool=0;
            else if(S2[top]==0){
                p=S1[top]->Rchid;
                S2[top]=1;
            }
            else {
                p=S1[top];
                top--;
                visit(p->data);
                p=NULL;
            }
        }while(bool==0);
    }
}

层次遍历二叉树

typedef struct {
    BiTreeNode *ptr;
    enum tag{L,R};
}

l利用队列的性质来进行遍历

（1）队首元素出队到p；

（2）访问p所指向节点；

（3）p所指向的节点的左右子节点依次入队，直到队列为空；

#define MAX_NODE 50
void LevelorderTraverse(BTNode *T){
    BTNode *Queue[MAX_NODE],*p=T;
    intn front=0,rear=0;
    if(p!=NULL){
        Queue[++rear]=p; //根节点入队
        while(front<rear){
            p=Queue[++front];
            visit(p->data);
            if(p->Lchild!=NULL)
                Queue[++rear]=p;//左节点入队
            if(p->Rchild!=NULL)
                Queue[++rear]=p;//右节点入队
        }
    }
}

两个推论

若已知一棵二叉树的前序序列和中序序列则可以唯一确定这课二叉树

若已知一棵二叉树的中序序列和后序序列则可以唯一确定这课二叉树

证明：归纳法：1.当n=1时显然成立；2.假定当n<=k时，结论成立；3.当n=k+1时，假定前序序列和中序序列分别为[a1,a2,…,an]和[b1,b2,…,bn].

如过中序序列与前序序列a1相同的元素为bj，

（1）若j=1时，二叉树无左子树，由[a2,a3,…,an]和[b1,b2,…,bn]可以唯一确定右子树；

（2）若j=n时，二叉树无右子树，由[a2,a3,…,an]和[b1,b2,…,bn]可以唯一确定左子树；

（3）若如2≤j≤m-1，则子树[a2,..aj]，[b1,…,bj-1]确定左子树和[aj+1,…an]，[bj+1,…bn]确定右子树。

BTNode *CreateBT(char *pre,char *in,int n){
    BTNode *S;
    char *p;
    int k;
    if(n<=0) return NULL;
    S=(BTNode *)malloc(sizeof(BTNode));
    s->data=*pre;
    for(p=in;p<in+n;p++)
        if(*p==*pre)
            break;
    k=p-in;
    S->Lchild = CreateBT(pre+1,in,k);
    S->Rchild = CreateBT(pre+k+1,p+1,n-k-1);
    return S;
}

二叉树遍历算法的应用

1.二叉树的二叉链表创建

（1）按满二叉树的方式建立

按满二叉树的方式对节点，输入i，ch；建立过程中借助一个一维数组S[n]编号为i的指针保存在S[i]中。

#define MAX_NODE 50
typedef struct BTNode{
    char data;
    struct BTNode *Lchild,*Rchild;
}BTNode;

BTNode *Create_BTree(void){
    BTNode *T,*P,*S[MAX_NODE];
    char ch;
    int i,j;
    while(1){
        scanf("%d",&i);
        if(i==0) 
            break;
        else {
            ch=getchar();
            p=(BTNode *)malloc(sizeof(BTNode));
            p->data=ch;
            p->Lchild=p->Rchild=NULL;
            S[i]=p;
            if(i==1)
                T=p;
            else{
                j=i/2;
                if(i%2==0)
                    S[j]->Lchild=p;
                else S[j]->Rchild=p;
            }
        }
    }
    return T;
}

(2)按先序遍历方式建立

对一颗二叉树进行扩充，就可以得到二叉树所扩充的二叉树

二叉树的扩充方法在节点有一个空链域处增加一个扩充的节点（总是叶子节点），

char类型：扩充节点值为“？”；int类型：扩充节点值为0或-1；
若扩充节点，令根的指针为NULL；
若是（正常）节点值：动态地为根指针分配一个节点将该值赋给根节点，然后递归地创建根的左子树和右子树。

#define NULLKY '?'
#define MAX_NODE 50
typedef struct BTNode {
    char data;
    struct BTNode *Lchild,*Rchild;
}BTNode;

BTNode *Preorder_Create_BTree(BTNode *T){
    char ch;
    ch=getchar();
    getchar();
    if(ch==NULLKY){
        T=NULL;
        return T;
    }else {
        T=(BTNode *)malloc(sizof(BTNode));
        T->data=ch;
        Preorder_Create_BTree(T->Lchild);
        Preorder_Create_BTree(T->Rchild);
        return T;
    }
}

求叶子节点数

可以直接利用先序遍历二叉树算法求二叉树叶子节点只要修改visit()函数即可

#define MAX_NODE 50
int serach_leaves(BTNode *T){
    BTNode *Stack[MAX_NODE],*p=T;
    int top=0,num=0;
    if(T!=NULL){
        stack[++top]=p;
        while(top>0){
            p=stack[top--];
            if(p->Lchild==NULL && p->Rchild==NULL)
                num++;
            if(p->Rchikd !=NULL)
                stack[++top]=p->Rchild'
            if(p->Lchild !=NULL)
                stack[++top]=p->Lchild;
        }
    }
    return num;
}

求二叉树深度

采用层次遍历的方法计算深度

#define MAX_NODE 50
int serach_depth(BTNode *T){
    BTNode *Queue[MAX_NODE],*p=T;
    int front=0,rear=0,depth=0,level;//level 总是指向访问层的最后一个节点
    if(T!=NULL){
        Queue[++rear]=p;//根节点入队
        level=rear;//根是第一层的最后一个节点
    }
    while(front<rear){
        p=Queue[++front];
        if(p->Lchild!=NULL)
            Queue[++rear]=p;  //入队
        if(p->Rchild!=NULL)
            Queue[++rear]=p;  //入队
        if(front==level){//正在访问的是最后一个节点
            depth++;
            level=rear;
        }
    }
}

线索二叉树

遍历二叉树，将非线性化转化为线性化

指针域里如果有左孩子，则Lchild指向左孩子，如果没有则指向直接前驱；指针域里如果有右孩子，则Rchild指向右孩子，如果没有则指向直接后继。对于这种情况我们加tag域，Ltag，Rtag如果tag为0则表明指针域内是节点，tag为1则表明指针域内是直接前驱或直接后继。线索链表中，线索是指指向前后的指针。

typedef struct BiThrNode{
    ElemType data;
    struct BiThrNode *Lchild,*Rchild;
    int Ltag,Rtag;
}BiThrNode;

后序遍历

若为根节点，则节点直接后继为空；如果是父节点的左孩子且父节点无右孩子，直接后继为父节点；若是父节点的左节点且父节点有右孩子，直接后继为右孩子按后序遍历的第一个节点。

添加一个头节点head，Lchild域和Rchild域附设指针last，工作指针的前驱

#define MAX_NODE 50
typedef enmu{Link,Thread} PointerTag;
typedef struct BiThrNode{
    ElemType data;
    struct BiTreeNode *Lchild,*Rchild;
    PointerTag Ltag,Rtag;
}BtThrNode;

先序线索化二叉树

void preorder_Threading(BiThrNode *T){
    BiThrNode *stack[MAX_NODE];
    BiThrNode *last=NULL,*p;
    int top=0;
    if(T!=NULL){
        stack[++top]=T;
        while(top>0){
            p=stack[top--];
            if(p->Lchikd)!=NULL) p->Ltag=0;
            else {
                p->Ltag=1;
                p->Lchild=last;
            }
            if(last!=NULL){
                if(last->Rchild!=NULL)
                    last->Rtag=0;
                else {
                    last->Rtag=1;
                    last->Rchild=p;
                }
            }
            last=p;
            if(p->Rchild!=NULL) stack[++top]=p->Rchild;
            if(p->Lchild!=NULL) stack[++top]=p->Lchild;
        }
        last->Rtag=1;//最后为叶子节点
    }
}

中序线索化二叉树

void inorder_Threading(BiThrNode *T){
    BiThrNode *stack[MAX_NODE];
    BiThrNode *last=NULL,*p=T;
    while(p!=NULL||top>0){
        if(p!=NULL){
            stack[++top]=p;
            p=p->Lchild;
        }else{
            p=stack[top--];
            if(p->Lchild!=NULL) p->Ltag=0;
            else { 
                p->Ltag=1;
                p->Lchild=last;
            }
            if(last!=NULL){
                if(last->Rchild!=NULL) last->Rtag=0;
                else {
                    last->Rtag=1;
                    last->Rchild=p;
                }
                last=p;
                p=p->Rchild;
            }
            last->Rtag=1;
        }
    }
}

线索二叉树的先序遍历

void Preorder_Thread_bt(BiThrNode *T){
    BiThrNode *p=T;
    while(p!=NULL){
        visit(p->data);
        if((p->Ltag==0) p=p->Lchild;
        else p=p->Rchild;
    }
}

线索二叉树的中序遍历

void inorder_Thread_bt(BiThrNode *T){
    BiThrNode *p;
    if(T!=NULL){
        p=T;
        while(p->Ltag==0)
            p=p->Lchild;
        while(p!=NULL){
            visit(p->data);
            if(p->Rtag==1)
                p=p->Rchild;
            else {
                p=p->Rchild;
                while(p->Ltag==0)
                    p=p->Lchild;
            }
        }
    }
}

树和森林

1.双亲表示法（顺序） 节点中加指示器

#define MAX_SIZE 100;
typedef struct PTNode{
    ElemType data;
    int parent;
}PTNode;
typedef struct {
    PTNode Nodes[MAX_SIZE];
    int root;
    int num;
}Ptree;

2.孩子链表表示法

（1）定长节点结构

指针域的数目是树的du；特点：指针域浪费显著，但是结构简单。

（2）不定长节点结构

操作不变

（3）复合链表结构

对于每个节点，孩子节点用单链表表示

#define MAX_NODE 100
typedef struct listnode{
    int childnode;
    struct  listnode  *next
}CTNode; //表节点
typedef struct {
    ElemType data;
    CTNode *firstchild;
}HNode; //头节点
type
    HNode nodes[MAX_SIZE];
    int root;
    int num;
}CLinkList; //头节点链表

3.孩子兄弟表示法（二叉树）

typedef struct CSnode{
    ElemType data;
    struct CSnode *firstchild,*nextsibing;
}CSNode;

物理结构相同，指针解释不同

有定义，任何一颗树都有一颗右子树为空的二叉树对应；

1.树转二叉树

（1）加虚线，在树的每层按从左至右的顺序在兄弟节点间加线

（2）去掉实线除了最左边的第一个子节点父节点与子节点的连线全部去掉

2.二叉树转树

（1）加虚线，父节点与自己所有的右孩子连线

3.森林转二叉树

二叉树的右子树必为空

森林中的第二棵树的根节点作为第一棵树的兄弟节点，则可导出森林。

设F=[T1,T2,…,Tn]是森林集合，二叉树B=（root，LB，RB）

（1）若n=0，则B是空树
（2）若n>0，则二叉树B的根节点是森林下的根节点。

二叉树转森林

将二叉树的根节点与其右节点以及右子树方向的所有右子节点的连线全部去掉，得到若干孤立的二叉树，每棵就是原来的二叉树。

树的遍历

（1）先序遍历：先访问根节点，然后依次先序遍历完每棵子树，树的先序遍历就是对树转变成的二叉树的先序遍历；树的后序遍历就是对树转变成的二叉树的中序遍历

森林的遍历

F=[T1,T2,..,Tn]是森林，对F的遍历有两种方法

（1）先序遍历：按先序遍历树的方式依次遍历F中的每棵树

（2）中序遍历，按后序遍历的方式依次遍历F中的每棵树

树的应用

二叉排序树（BST）

二叉排序（搜索）树（Binary Sort Tree）或（Binary Serach Tree）的定义为：二叉排序树是空树或者是满足下列性质的二叉树。

（1）若左子树不为空，则左子树上所有的节点的值（关键字）都小于根节点的值；

（2）若右子树不为空，则右子树上所有的节点的值（关键字）都大于根节点的值；

（3）左右子树都分别是二叉搜索树。

结论：若按中序遍历一颗二叉排序树，所得到的节点序列是一个递增序列

BST仍用二叉链表存储

typedef struct Node{
    KeyType Key;
    struct Node *Lchild,*Rchild;
}BSTNode;

BST树的查找

给定k值比较相等则成功

（1）k小于根节点，则k位于左子树；

（2）k大于根节点，则k位于右子树。

递归算法

BSTNode *BST_Search(BSTNode *T,KeyType key){
    if(T==NULL) return NULL;
    else {
        if(EQ(T->key,kry)) return T;
        else if(LT(key,T->Key))
            return  BST_Serach(T->Lchild,key);
        else 
            return BST_Serach(T->Rchild,key);
    }
}

非递归算法

BSTNode *BST_Serach(BSTNode *T,KeyType key){
    BSTNode p=T;
    while(P!=NULL && !EQ(p->key,key)){
        if(LT(key,p->key)
            p=p->Lchild;
        else 
            p=p->Rchild;
        if(EQ(p->key,key))
            return p;
        else 
            return NULL;
    }
}

平均查找长度ASL和logn（树的深度）等数量级。

BST树的插入

（1）节点值相等不需要插入操作；
（2）x.key< T->key ,x插入左子树；
（3）x.key> T->key ,x插入右子树。

void Insert_BST(BSTNode *T,keyType key){
    BSTNode *x;
    x=(BSTNode *)malloc (sizeof(BSTNode));
    x->key=key;
    x->Lchild=x->Rchild=NULL;
    if(T==NULL) T=x;
    else{
        if(EQ(t->key,x->key)) return ;
        else if(LT(x->key,T->key))
            Insert_BST(T->Lchild,key);
        else 
            Insert_BST(T->Rchild,key);
    }
}

非递归算法

void Insert_BST(BSTNode *T,keyType key){
    BSTNode *x,*p,*q;
    x=(BSTNode *)malloc(sizeof(BSTNode));
    x->key=key;
    x->Lchikd=x->Rchild=NULL;
    if(T==NULL) T=x;
    else {
        p=T;
        while(p!=NULL){
            if(EQ(p->key,x->key)
                return ;
            q=p;
            if(LT(x->key,p->key))
                p=p->Lchild;
            else p=p->Rchild;
        }
        if(LT(x->key,q->key))
            q->Lchild=x;
        else q->Rchild=x;
    }
}

对于一个无序序列可以通过构造一颗BST树来达到排序的目的。

#define ENDKEY 65535
BSTNode *Create_BST(){
    keyType key;
    BSTNode *T=NULL:
    scanf("%d",&key);
    while(key!=ENDKEY){
        Insert_BST(T,key);
        scanf("%d",&key);
    }
    return T;
}

BST树的删除

1.若是叶子节点，直接删除；

2.若p只有一颗子树，直接用其左（右）子树取代即可；

3.节点既有左子树又有右子树

用p的直接前驱代替p，即从p的左子树中值最大的S放在p，然后删除S，S是左子树中最右的节点且没有右子树删除同2；用p的直接后继代替p，即从p的右子树中值最小的S放在p，然后删除S，S是右子树中最左的节点且没有左子树删除同2；

void Delete_BST(BSTNode *T,keyType key){
    BSTNode *p=T,*f=NULL,*q,*s;
    while(p!=NULL&&!EQ(p->key,key)){
        f=p;
        if(LT(key,p->key))  p=p->Lchild;
        else  p=p->Rchild;
    }
    if(p==NULL) return ;
    s=p;
    if(p->Lchild!=NULL && p->Rchild!=NULL){
        f=p;
        s=p->Lchild;
        while(s->Rchild != NULL){
            f=s;
            s=s->Rchild;
        }
        p->key=s->key;
        p->otherinfo=s->otherinfo;
    }
    if(s->Lchild!=NULL) q=s->Lchild;
    else q=s->Rchild;
    if(f==NULL) T=q;
    else if(f->Lchild==s) f->Lchild=q;
    else f->Rchild=q;
    free(s);
}

平衡二叉树AVL

平衡二叉树是空树或（1）左右子树深度之差的绝对值不大于1；（2）左子树和右子树也是AVL。平衡因子（Balance Factor）二叉树上节点的左子树深度减去其右子树的深度，因此AVL每个点的平衡因子只有1，0，-1。否则不是AVL，若果一颗二叉树既是BST又是AVL则称为平衡二叉排序树。

节点定义：

typedef struct BNode{
    KeyType key;
    int Bfactor; //平衡因子
    ...
    struct BNode *Lchild,*Rchild;
}BSTNode;

在AVLBST是查找过程一样，给定k值比较次数不会超过D，设深度为h，AVLBST最少节点树为Nn。平均查找长度为O（log2 n）

平衡化旋转

如果一颗平衡二叉树中插入新节点，造成了不平衡，必须调整树的结构，使之平衡化，平衡化有两类：

（1）单旋（LL和RR）

（2）双旋（LR和RL）

插入一个新节点后，从插入位置回溯检查各点的平衡因子；

如果在某节点发现高度不平衡，停止，沿回溯路径取两层节点；

如果处一条直线，则单旋；

如果是一条折线，则双旋平衡化。

左单旋（RR）：在A的右子女c的右子树E中插入新节点，将A拉到c的左子树，c的左子树变成A的右子树。

AVL的插入

（1）判别不平衡

（2）找到不平衡的最小子树；

（3）判断旋转类型。

AVL的删除

1.最多只有一个子女节点：直接将子女节点接上，如果没有子女节点指NULL，将以节点X为根的子树高度减一；

2.如果有两个子女节点：找到直接前驱y，把y传递给x，转移为删除y；

3.必须沿x通向root的路径反向追踪高度对于各个点的影响。

霍夫曼树（Huffman）

最优二叉树
1.节点路径：从Node到Node
2.路径长度：路上的分支数
3.树的路径长度：从根到每一个点的长度之和
4.节点的带权路径长度：从该点到根节点之间长度与权的乘积
5.树的带权路径长度：所有叶子节点的带权路径长度之和WPL=w1*/1+w2*/2+...+wn*/n=Σwi*/i
6.Huffman树是WPL最小的树

霍夫曼树的构造

（1）根据n个权值[w1,w2,..,wn]构成n个二叉树的集合，F=[T1,T2,..,Tn],其中每棵只有root，没有左右子树；

（2）从F中找最小权值的两个作为左右子树，且新树根为两树权值之和；

（3）F中删除两个树，并将合成的新树加入F；

（4）重复（2）（3），注：权值小的作为左子树，权值大的作为右子树，如果相等则让深度小的作为左子树，深度大的作为右子树，这样可以保证Huffman树的唯一性。

霍夫曼编码

保证任意一个字符的编码都不是另一个编码的前缀，Huffman权值可以构造长度不等且译码不产生二义性的编码。由于每个字符都是叶子节点，所以不会有前缀相同的编码。

霍夫曼树的实现

Huffman中没有度为1的节点

一颗有n个叶子节点的Huffman树中共有2n-1个节点可存于2n-1的数组中，2n-1=2（n-1）+1原因：求一个字符的编码需要从叶子节点出发走一条从叶子到根的路径

#define MAX_NODE 200
tyoedef struct{
    unsigned int Weight;
    unsigned int Parent,Lchild,Rchild;
}HTNode;

Huffman树的生成

void Create_Huffman(unsigned n,HTNode HT[],unsigned m){
    unsigned int w;
    int k,j;
    for(k=1;k<m;k++){
        if(k<=n){
            scanf("%d",&w);
            HT[k].weight=w;
        }else HT[k].weight=0;
        HT[k].Parent=HT[k].Lchild=HT[k].Rchild=0;
    }
    for(k=n+1;k<m;k++){
        unsigned w1=32767,w2=w1;
        int p1=0,p2=0;
        for(j=1;j<=k-1;j++){
            if(HT[k].Parent==0){
                if(HT[j].Weight<w1){
                    w2=w1;
                    p2=p1;
                    w1=HT[j].Weight;
                    p1=j;
                }else if(HT[j].Weight<w2){
                    w2=HT[j].Weight;
                    p2=j;
                }
            }
            HT[k].Lchild=p1;
            HT[k].Rchild=p2;
            HT[p1].Parent=k;
            HT[p2].Parent=k;
        }
    }
}

huffman编码算法

根据权值，对叶子节点有两种处理方式

（1）从叶子节点到根节点处理，求每个叶子节点的对应编码；

（2）从根遍历整个树求所有编码；

求编码是先设一个通用的指向字符的指针变量，求得编码后再复制。

void Huff_coding(unsigned n,Hnode HT[],unsigned m){
    int k,sp,fp;
    char *cd ,*HT[m];
    cd=(char *)malloc(sizeof(char));
    cd[n]='\0';
    for(k=1;k<n+1;k++){
        sp=n;
        p=k;
        fp=HT[k].parent;
        for(;fp!=0;p=fp,fp=HT[p].parent)//从叶子到根节点
            if(HT[fp].parent==Lchild) cd[--sp]='0';
            else cd[--sp]='1';
            HT[k]=(char *)malloc(sizeof(char));
            trcpy(HT[k],&cd[sp]);
    }
    free(cd);
}

问题与说明

备注

CLion开发环境，C语言实现

程序清单