【数据结构】树与二叉树

树的定义和基本术语

定义

树是n(n>=0)个结点的有限集。

(1)有且仅有一个特定的称为根的结点

(2)n>1时，其他结点可以分为m个不相交的有限集，其中每个集合也构成一颗树，称为根的子树。

特点

(1)树的根结点没有前驱，其他结点有且仅有一个前驱。

(2)树中任何一个结点可以有零或多个后继结点。

术语

1.结点(node)

2.结点的度(degree)

3.树的度

4.叶子或终端结点

5.非终端结点

6.父(双)亲结点(parent)

7.儿(孩)子结点(child)

8.兄弟结点(sibling)

9.路径

10.祖先

11.子孙(后代)

12.结点的层数(level)

12.树的深度(depth)或高度

14.有序树和无序树

15.森林(forest): 是m(m>=0)棵互不相交的树的集合

树的表示方法

1.图

2.嵌套集合

3.广义表形式： (A(B(D),C))

4.凹入表示法

树的有关概念

树的抽象数据类型

ADT Tree{
    数据对象D:D是具有相同特性的元素的集合。
  数据关系R:若D为空集,则称为空树;否则:
                  (1)在D中存在唯一的称为根的数据元素，则R集为空;
                (2)当n>1时,其余结点n>1时，其他结点可以分为m个不相交的有限集，其中每个集合也是一颗符合本定义的树，称为根root的子树。
  基本操作P:查找类、插入类、删除类操作。                                 
}

树的基本操作类

查找类

Root(T)//求树的根结点
Value(T,cur_e)//求当前结点的元素值
Parent(T,cur_e)//求当前结点的双亲结点
LeftChild(T,cur_e)//求当前结点的最左孩子
RightSibling(T,cur_e)//求当前结点的右兄弟
TreeEmpty(T)//判断树是否为空
TreeDepth(T)//求树的高度
TraverseTree(T,Visit())//遍历

插入类

InitTree(&T)//初始化置空树
CreateTree(&T,definition)//按定义构造树
Assign(T,cur_e,value)//为当前结点赋值
InsertChild(&T,&p,i,c)//将c为根的树插入为结点p的第i棵子树

删除类

ClearTree(&T)//清空树
DestroyTree(&T)//销毁树的结构
DeleteChild(&T,&p,i)删除结点p的第i棵子树

二叉树的定义

定义

二叉树(Binary Tree)是n(n>=0)个结点的集合，这个集合可以是空集，可以是一个结点，或者是由一个根结点和两棵称为左子树和右子树的互不相交的二叉树组成。

特点

1.可以为空，即不含结点

2.每个结点至多有二棵子树(二叉树中不存在度大于2的结点)

3.二叉树是有序树，子树有左右之分，次序不能任意颠倒；允许有些结点只有左子树或右子树

五种基本形态

如图：

二叉树与树的区别

每个结点至多两个子树，且有左右之分

二叉树的性质

1.在二叉树的第i(i>=1)层上至多有$2^{i-1}$个结点

2.深度为k的二叉树最多有$2^k$-1个结点

3.对任意二叉树T，如果终端结点数为n~0~(度数为0的结点树),n~1~,n~2~分别表示度数为1，2的结点个数，则n~0~=n~2~+1

满二叉树：

一个二叉树的叶子结点都在最后一层上，且不存在度数为1的结点

设高为k则有$2^k$-1个结点

特点：

1.对给定的高度，满二叉树有最多结点

2.不存在度为1的结点

3.每个分支都有两颗高度相同的子树

4.叶子结点都在最后一层

(重点)完全二叉树：如果存在一颗二叉树，对树中结点自上而下，自左而右连续编号，若编号为i的结点的位置与满二叉树中i的结点的位置相同，则称此二叉树为完全二叉树。

特点：

1.叶子结点只可能在层树最大的两层上出现

2.对任意结点，若有右子树则必有左子树

3.具有n个结点的完全二叉树深度为$\lfloor log_2n\rfloor$+1（向下取整）或者$\lceil log_2(n+1)\rceil$(向上取整)

4.对于一个具有n个结点的完全二叉树，其结点按层序编号，则对任意结点k~i~(1$\leq$i$\leq$n)：

已知编号i(1$\leq$i$\leq$n)，双亲结点是$\lfloor i/2 \rfloor$

已知编号i(1$\leq$i$\leq$n/2)，左孩子结点为2i

已知编号i(1$\leq$i$\leq$(n-1)/2)，左孩子结点为2i+1

已知编号i(i为奇数,且1<i<n),左兄弟结点为i-1

已知编号i(i为偶数,且1<i<n),左兄弟结点为i+1

二叉树的存储结构

顺序存储结构

利用完全二叉树的性质，可以将完全二叉树存入向量b[n]中。

#define MAX_TREE_SIZE 100
typedef TElemType SqBiTree[MAX_TREE_SIZE];
SqBiTree bt;//和TElemType bt[100]相同

1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
31	23	12	66	$\emptyset$	05	17	70	62	$\emptyset$	$\emptyset$	$\emptyset$	88	$\emptyset$	55

顺序存储方式对于畸形二叉树，浪费空间

链式存储结构

每个结点中，设置两个链域指向左孩子和右孩子，一个数据域，若没有左孩子或右孩子，则指针指向NULL

struct TElemType{
  int key;
};
typedef struct BiTNode{
    TElemType data
    struct BiTNode *lch,*rch;
}BiTNode,*BiTree;

n个结点的二叉树中，共有n+1个空域

二叉链表很难找到双亲

三叉链表(带双亲的二叉链表) 含四个域：数据域，左指针域，右指针域，双亲域

struct TElemType{
  int key;
};
typedef struct BiTNode{
    TElemType data;
    struct BiTNode *lch,*rch,*parent;
}BiTNode,*BiTree;

二叉树的生成

递归创建

BiTNode* CreateBiTree(int* a, int n, int &i,int size)
{
    if (i<size&&a[i]!=n)
    {
        BiTNode* newNode = InitBtNode(a[i]);
        i++;
        newNode->lch = CreateBiTree(a, n, i,size);
        i++;
        newNode->rch = CreateBiTree(a, n, i,size);
        return newNode;
    }
    return NULL;
}

销毁：

void DestoryBiTree(BiTree &root)
{
    if (NULL==root)
    {
        return;
    }
    DestoryBiTree(root->lch);
    DestoryBiTree(root->rch);
    free(root);
    root = NULL;
}

遍历二叉树

样例：

前序遍历(先根遍历)

1.若二叉树为空，则返回；

若不空：

2.访问根结点；

3.前序遍历左子树

4.前序遍历右子树

先根，再左，后右

遍历结果：

1 2 4 8 9 5 10 11 3 6 12 7

前序遍历的第一个结点的是根结点，最后一个结点一定是叶子结点。

中序遍历(中根遍历)

1.若二叉树空，返回；

若不空：

2.中序遍历左子树；

3.访问根结点；

4.中序遍历右子树。

先左，再根，后右

遍历结果：

8 4 9 2 10 5 11 1 12 6 3 7

第一个结点是最左边的结点，最后一个结点是最右边的结点，根结点位于左子树结点和右子树结点之间。

后序遍历(后根遍历)

1.若二叉树空，返回；

若不空：

2.中序遍历左子树；

3.后序遍历右子树；

4.访问根结点。

先左，再右，后根

遍历结果：

8 9 4 10 11 5 2 12 6 7 3 1

后序遍历中最后一个结点是根结点

树的遍历

递归遍历

先序遍历：

void PreOrder(BiTree T){
    if(T){
    visit(T->data);//遍历操作，可以是打印该结点的值
    PreOrder(T->lch);
    PreOrder(T->rch);
  }
}

中序遍历：

void InOrder(BiTree T){
  if(T){
    InOrder(T->lch);
    visit(T->data);
    InOrder(T->rch);
  }
}

后序遍历：

void PostOrder(BiTree T){
  if(T){
    PostOrder(T->lch);
    PostOrder(T->rch);
    visit(T->data);
  }
}

非递归遍历

先序遍历：

#define MAX 100
void PreOrder(BiTNode *root){
  BiTNode *p,*BiNode[MAX];
  int top=0;p=root;
  do{
    while(p!=NULL){
      visit(p->data);
      BiNode[top]=p;
      top++;
      p=p->lch;
    }
    if(top>0){
      top--;
      p=BiNode[top];
      p=p->rch;
    }
  }while(top>0||p!=NULL);
}

中序遍历：

void InOrder_N(BiTree root){
    BiTNode *p,*BiNode[MAX];
    int top=0;p=root;
    if(isEmpty(root)){
        printf("BiTree Empty!\r\n");
    }
    do{
        while(p!=NULL){
            BiNode[top]=p;
            top++;
            p=p->lch;
        }
        if(top>0){
            top--;
            p=BiNode[top];
            visit(p->data);
            p=p->rch;
        }
    }while(top>0||p!=NULL);
}

后序遍历：

void PostOrder_N(BiTree root)
{
    BiTNode *p, *lastVisited = NULL;
    BiTNode *stack[MAX];
    int top = 0; // 栈顶位置下标

    if (root == NULL)
    {
        return;
    }

    p = root;

    while (p != NULL || top > 0)
    {
        while (p != NULL)
        {
            stack[++top] = p;
            p = p->lch;
        }
        p = stack[top];
        // 判断右子树是否已经访问过
        if (p->rch == NULL || p->rch == lastVisited)
        {
            visit(p->data);
            lastVisited = p;
            top--;
            p = NULL; // 置空，防止重复访问
        }
        else
        {
            p = p->rch;
        }
    }
}

二叉树的其他操作

判断树是否空：

int isEmpty(BiTree root){
    if(root==NULL) return 1;
    else return 0;
}

访问结点操作：

void visit(TElemType data){
    printf("%d ",data.key);
}

求结点数：

int NodesNum(BiTNode *b){
    int num1,num2;
    if(b==NULL)
        return 0;
    else return NodesNum(b->lch)+NodesNum(b->rch)+1;
}

求叶子结点数：

int LeafNodesNum(BiTNode *b){
    int num1,num2;
    if(b==NULL)
        return 0;
    else if (b->lch==NULL&&b->rch==NULL){
        return 1;
    }
    else {
        num1=LeafNodesNum(b->lch);
        num2=LeafNodesNum(b->rch);
        return (num1+num2);
    }
}

复制树的操作：

void Copy(BiTNode *b,BiTNode *&t){
    if(b==NULL) t=NULL;
    else{
        t=(BiTNode*)malloc(sizeof(BiTNode));
        t->data=b->data;
        Copy(b->lch, t->lch);
        Copy(b->rch,t->rch);
    }
}

交换左右子树：

void Swap(BiTNode *b,BiTNode *&t){
    if(b==NULL) t=NULL;
    else{
        t=(BiTNode*)malloc(sizeof(BiTNode));
        t->data=b->data;
        Swap(b->lch, t->lch);
        Swap(b->rch,t->rch);    
    }
}

求树的高度：

int height(BiTree t){
    int tl,tr;
    if(t==NULL) return 0;
    tl=height(t->lch);
    tr=height(t->rch);
    if(tl>=tr) return tl+1;
    else return tr+1;
}

性质

给定遍历序列是否可以确定树的唯一结构？

只给出一个序列，无法确定树的唯一结构

给出前序和后序序列，无法确定唯一的二叉树

给出中序和后序序列，可以确定唯一的二叉树

给出中序和前序序列，可以确定唯一的二叉树

问题：给出前序和中序序列，如何构建二叉树？

代码实现：

void CreateTree(BiTree &T,int root,int start,int end,char *m,char *n)   //创建二叉树
{
    T=(BiNode*)malloc(sizeof(BiNode));
    if(start>end)
    {
        T=NULL;
        return;
    }
    int i=start;
    while(i<end&&n[i]!=m[root])
        i++;
    T->data=n[i];
    CreateTree(T->lch,root+1,start,i-1,m,n);
    CreateTree(T->rch,root+1+i-start,i+1 ,end,m,n);
}

线索二叉树

既可以指示前驱又可以指示后继的双链结构的二叉树称为线索二叉树

若结点有左子树，则lch指示左孩子，否则指示其前驱

若结点有右子树，则rch指示其右孩子，否则指示其后继

结点结构

typedef struct node{
    datatype data;
    struct node *lch,*rch;
    int ltag,rtag;
}threadbithptr,*BiThrTree;

ltag=0 lch指向左孩子 ltag=1 lch指向前驱

ltag=0 rch指向右孩子 ltag=1 rch指向后继

二叉树的线索化

存储结构：

typedef struct node{
    TElemType data;
    struct node *lch,*rch;
    int ltag,rtag;
}threadbithptr,*BiThrTree;
BiThrTree pre=NULL;

中序线索化：

void InThreading(BiThrTree p){
    if(p){
        InThreading(p->lch);
        if(!p->lch){
            p->ltag=1;
            p->lch=pre;
        }
        if(!p->rch){
            pre->rtag=1;
            pre->rch=p;
        }
        pre=p;
        InThreading(p->rch);
    }
}
void InOrderThreading(BiThrTree &Thrt,BiThrTree T){
    if(!(Thrt=(threadbithptr*)malloc(sizeof(threadbithptr)))){
        exit(-1);
    }
    Thrt->ltag=0;
    Thrt->rtag=1;
    Thrt->rch=Thrt;
    if(!T){
        Thrt->lch=Thrt;
    }
    else{
        Thrt->lch=T;
        pre=Thrt;
        InThreading(T);
        pre->rch=Thrt;
        pre->rtag=1;
        Thrt->rch=pre;
    }
}

在中序线索树中查找结点*p的后继：

threadbithptr* InOrderNext(threadbithptr *p){
    threadbithptr *q;
    if(p->rtag==1){
        return p->rch;
    }
    else {
        q=p->rch;
        while(q->ltag==0)
            q=q->lch;
        return q;
    }
}
void TraverseInthread(threadbithptr *p){
    if(p!=NULL){
        while(p->ltag==0)
            p=p->lch;
        do{
            visit(p->data);
            p=InOrderNext(p);
        }while(p!=NULL);
    }
}

在中序线索树中查找结点*p的前驱：

threadbithptr* InOrderPre(threadbithptr *p){
    threadbithptr *q;
    if(p->ltag==1){
        return p->lch;
    }
    else{
        q=p->lch;
        while(q->rtag==0)
            q=q->rch;
        return q;
    }
}

遍历中序线索二叉树的非递归算法：

void TraverseInthread(threadbithptr *p){
    if(p!=NULL){
        while(p->ltag==0)
            p=p->lch;
        do{
            visit(p->data);
            p=InOrderNext(p);
        }while(p!=NULL);
    }
}

树和森林

树的存储结构

双亲表示法

采用一组连续空间存储树的结点，通过保存每个结点的双亲结点的位置，表示树中结点关系的位置结构。

typedef struct PTNode{
    TElemType data;
    int parent;
}PTNode;

孩子链表表示法

对树的每个结点用线性链表存储它的孩子结点。

typedef struct CTNode{
  int child;
  struct CTNode *next;
}*ChildPtr;
typedef struct{
    TElemType data;
  int parent;
    ChildPtr firstchild;
}CTBox;
typedef struct{
  CTBox nodes[MAX];
  int n,r;
}CTree;

带双亲的孩子链表表示法

typedef struct CTNode{
  int child;
  struct CTNode *next;
}*ChildPtr;
typedef struct{
    TElemType data;
  int parent;
    ChildPtr firstchild;
}CTBox;
typedef struct{
  CTBox nodes[MAX];
  int n,r;
}CTree;

孩子兄弟表示法

typedef struct CSNode{
    TElemType data;
    struct CSNode *firstchild,*firstbrother;
}CSNode,*CSTree;

树、森林与二叉树的转化

树到二叉树

1)在所有兄弟结点之间加一条连线。

2)对每个结点，除了保留与其长子的连线外，去掉该结点与其他孩子的连线。

森林到二叉树

1)将森林中的每一棵树转化为二叉树

2)将各二叉树的根结点视为兄弟连在一起

树的遍历

一般不中序遍历

两条路径：从左到右、从上到下

树的前序遍历与转换成二叉树的前序遍历相同

树的后序遍历与转换成二叉树的中序遍历相同

赫夫曼树及其应用

基本概念

路径长度：路径上边的个数

树的路径长度：从根结点出发，到所有结点的路径长度之和

结点的带权路径长度：结点到根结点的长度与权重的乘积

树的带权路径长度：所有叶子结点的带权路径长度之和

赫夫曼树的定义

最优二叉树，给定叶结点权重，具有最小带权路径长度的二叉树。

构造赫夫曼树(赫夫曼算法)

基本思想：使权值大的叶子结点尽量靠近根节点，而使权值小的叶子结点尽量远离根结点

将给定的一些叶子结点中取出两个最小的叶子作为一个结点的左孩子和右孩子，然后将它们的权值相加，从剩下的叶子中寻找最小的结点作为上面结点的兄弟，重复此操作。

n个叶结点，按上述操作，构造的树中含有2n-1个结点。

huffman算法实现：

主函数先给n，m赋值。

typedef struct {
    float weight;
    int lch,rch,parent;
}hufmtree;
int n,m;
void CreateHuffmanTree(hufmtree tree[]){//初始化
    int i;
    for(i=0;i<m;i++){
        tree[i].weight=0.0;
        tree[i].lch=-1;
        tree[i].rch=-1;
        tree[i].parent=-1;
    }
}
void InputWeight(hufmtree tree[]){
    float w;
    float small1,small2,f;
    int i,j,p1,p2;
    for(i=0;i<n;i++){
        printf("\n输入第%d个权值:",i+1);
        scanf("%f",&w);
        tree[i].weight=w;
    }
    for(i=n;i<m;i++){//把合并后的结点放入n～m向量
        p1=0;p2=0;    //两个根结点在tree中的下标
        small1=MAXFLOAT;//MAXFLOAT为最大浮点数
        small2=MAXFLOAT;
        for(j=0;j<i-1;j++){//选择两个最小的权
            if(tree[j].parent==-1){
                if(tree[j].weight<small1){
                    small2=small1;//更新最小权，次小权，及其位置
                    small1=tree[j].weight;//找出最小权
                    p2=p1;
                    p1=j;
                }
                else if(tree[j].weight<small2){
                    small2=tree[j].weight;//改变次小权及位置
                    p2=j;
                }
            }
        }
        tree[p1].parent=i+1;
        tree[p2].parent=i+1;
      //将新生成的结点放在tree[i+1]
        tree[i+1].lch=p1;
        tree[i+1].rch=p2;
        tree[i+1].weight=tree[p1].weight+tree[p1].weight;
    }
}

赫夫曼编码

1)首先构造出赫夫曼树

2)每个结点的左分支计0 右分支计1，从根结点到叶子结点的沿途路径分支组成的01代码串即赫夫曼编码