数据结构第6章 树和二叉树树的定义和基本术语二叉树赫夫曼树及其应用

树的定义和基本术语

概念

树（Tree）是n（n≥0）个结点的有限集合，它或为空树（n = 0）；或为非空树，对于非空树T：

1. 有且仅有一个称之为根的结点；
2. 除根结点以外的其余结点可分为m（m＞0）个互不相交的有限集T1, T2, …, Tm, 其中每一个集合本身又是一棵树，并且称为根的子树（SubTree）。

结点的度与树的度：树中一个结点的子树的个数称为该结点的度。树中各结点的度的最大值称为树的度，通常将度为m 的树称为m次树或者m叉树。

分支结点与叶结点：度不为零的结点称为非终端结点，又叫分支结点。度为零的结点称为终端结点或叶结点（或叶子结点）。
度为1的结点称为单分支结点；度为2的结点称为双分支结点，依此类推。

两个结点间的路径长度等于路径所通过的结点数目减1（即路径上分支数目）。

孩子结点、双亲结点和兄弟结点：在一棵树中，每个结点的后继，被称作该结点的孩子结点。相应地，该结点被称作孩子结点的双亲结点。具有同一双亲的孩子结点互为兄弟结点。

以某结点为根的子树中的任一结点都成为该结点的子孙。结点的祖先是从根到该结点所经分支上的所有结点。

有序树和无序树：若树中各结点的子树是按照一定的次序从左向右安排的，且相对次序是不能随意变换的，则称为有序树，否则称为无序树。

树的性质

1. 树中的结点数等于所有结点的度数加1。
2. 度为m的树中第i 层上至多有m i-1个结点，这里应有i≥1。
3. 高度为h的m次树至多有$\frac{m^h-1}{m-1}$个结点。

树的存储结构

孩子链表

把每个结点的孩子结点排列起来，看成是一个线性表，且以单链表作存储结构，则 n个结点有 n 个孩子链表（叶子的孩子链表为空)。

typedef struct CTNode {   //孩子结点
    int child;
  　struct CTNode *next; 
} *ChildPtr;

typedef struct {　 //双亲结点结构
    ElemType data; 
    CTNode* firstchild; // 孩子链的头指针
} CTBox;

typedef struct {  //树结构:
    CTBox nodes[MAX_TREE_SIZE];
    int n, r; // 结点数和根结点的位置    
} CTree;

左孩子右兄弟链

typedef struct CSNode
{  ElemType          data;
   struct CSNode   *firstchild;
  struct CSNode  *nextsibling;
}CSNode,*CSTree;

树的遍历

1. 先根遍历：若树不空，则先访问根结点，然后依次先根遍历各棵子树。
2. 后根遍历：若树不空，则先依次后根遍历各棵子树，然后访问根结点。
3. 层次遍历：若树不空，则自上而下、自左至右访问树中每个结点。

二叉树

二叉树的定义

二叉树是有限的结点集合。
这个集合或者是空。
或者由一个根结点和两棵互不相交的称为左子树和右子树的二叉树组成。

满二叉树：如果所有分支结点都有双分结点；并且叶结点都集中在二叉树的最下一层的二叉树。

完全二叉树：除最后一层外，每一层都取最大结点数，并且最下一层结点都集中在该层最左边的若干位置。

二叉树的性质

1. 若在任意一棵二叉树中，有$n_0$个叶子结点，有$n_2$个度为2的结点，则：$n_0=n_2+1$

2. 二叉树的第i层上至多有$2^{i-1}（i>1）$个结点。至少有1个结点；

3. 深度为h的二叉树中至多含有$2^{h-1},(h\ge 1)$个结点。

4. 含n个结点完全二叉树性质：若n为奇数，$n_1=0$ ；若n为偶数，$n_1=1$。（$n_i$表示度为$i$的节点数）

5. 含n个结点完全二叉树性质：若编号为 i 的结点有左孩子结点，则左孩子结点的编号为 2i ；若编号为i的结点有右孩子结点，则右孩子结点的编号为 2i+1。除树根结点外，若一个结点的编号为 i，则它的双亲结点的编号为 $\lfloor i/2\rfloor$ 。若$i\le \lfloor n/2\rfloor$，则编号为i的结点为分支结点，否则为叶结点。
   

6. 具有n个（n＞0）结点的完全二叉树的高度为$\lceil {\log }_2(n+1)\rceil$。

7. 任何二又树，都可由它的中序序列和前序序列唯一地确定；或者中序序列和后序序列唯一地确定。

二叉树的存储结构

二叉树的顺序存储结构

一般的二叉树先用空结点补全成为完全二叉树，然后按完全二叉树的结点层次编号，依次存放二叉树中的数据元素。

二叉树的链式存储结构

typedef struct node
 { ElemType data;
   struct node *lchild;
   struct node  *rchild;
 } BTNode;      

三叉链表

typedef struct  TriBNode
{   ElemType data;
    TriBNode*lchild,*rchild，*parent;
 } TriBNode;

遍历二叉树

先序遍历的

void PreOrder(BTNode *b)
{  //递归算法
   if (b!=NULL)  
   {       
        printf("%c ",b->data);    //访问根结点
        PreOrder(b->lchild);
        PreOrder(b->rchild);
   }
}

void PreOrder2(BTNode *b)
{   //非递归算法，栈中保存的是当前结点p的所有祖先结点
    BTNode *p;  
    SqStack *st;//定义一个顺序栈指针st，
    InitStack(st);		//初始化栈st
    p=b;
    while (!StackEmpty(st) || p!=NULL)
    {	if(p!=NULL)	 //访问根结点，根指针进栈，遍历左子树
        {	printf("%c "，p->data);	//访问结点p
            Push(st，p);		//结点p进栈
            p=p->lchild;		//移动到左孩子
        }
        //以下考虑栈顶结点
        else//根指针退栈，遍历右子树
        {	Pop(st，p);	//出栈结点p
            p=p->rchild;	//转向处理其右子树
        }
    }
    DestroyStack(st);  //销毁栈
}

中序遍历

 void InOrder(BTNode *b)
 {   //递归算法
    if (b!=NULL)  
    {        
        InOrder(b->lchild);
        printf("%c ",b->data); //访问根结点
        InOrder(b->rchild);
    } 
}

void InOrder2(BTNode *b)
{   //非递归算法，栈中保存的是当前结点p的所有祖先结点
    BTNode *p;  SqStack *st;	//定义一个顺序栈指针st
    InitStack(st);		//初始化栈st
    p=b;
    while (!StackEmpty(st) || p!=NULL)
    {	 
        if(p!=NULL)	 //根指针进栈，遍历左子树
        {	
            Push(st，p);		//结点p进栈
            p=p->lchild;		//移动到左孩子
        }
        //以下考虑栈顶结点
        else //根指针退栈，访问根结点，遍历右子树
        {	Pop(st，p);	//出栈结点p
            printf("%c "，p->data);	//访问结点p
            p=p->rchild;	//转向处理其右子树
        }
    }
    DestroyStack(st);  //销毁栈
}

后序遍历

 void PostOrder(BTNode *b) 
 {   //递归算法
    if (b!=NULL)  
    {  
        PostOrder(b->lchild);
        PostOrder(b->rchild);
        printf("%c ",b->data); //访问根结点
    } 
}

void PostOrder1(BTNode *b)	//后序非递归遍历算法
{   //非递归算法，栈中保存的是当前结点p的所有祖先结点
    BTNode *p，*r;
    bool flag;
    SqStack *st;		//定义一个顺序栈指针st
    InitStack(st);		//初始化栈st
    p=b;
    do
    {	
        while (p!=NULL)	//扫描结点p的所有左下结点并进栈
        {       
            Push(st，p);		//结点p进栈
            p=p->lchild;	//移动到左孩子
        }
        r=NULL;		//r指向刚刚访问的结点，初始时为空
        flag=true;		//flag为真表示正在处理栈顶结点
        while (!StackEmpty(st) && flag)
        {      
            GetTop(st，p);//取出当前的栈顶结点p
            if (p->rchild==r)//若结点p的右孩子为空或者为刚访问结点	
            {   printf("%c "，p->data);//访问结点p
                Pop(st，p);
                r=p;		 //r指向刚访问过的结点
            }
            else
            {      
                p=p->rchild;	//转向处理其右子树
                flag=false;		//表示当前不是处理栈顶结点
            }
        }
    } while (!StackEmpty(st));	//栈不空循环
    printf("n");
    DestroyStack(st);		//销毁栈
}

层次遍历

void LevelOrder(BTNode *b)
{      
    BTNode *p;
    SqQueue *qu;			//定义环形队列指针
    InitQueue(qu);			//初始化队列
    enQueue(qu，b);			//根结点指针进入队列
    while (!QueueEmpty(qu))		//队不为空循环
    {	deQueue(qu，p);		//出队结点p
        printf("%c "，p->data);		//访问结点p
        if (p->lchild!=NULL)		//有左孩子时将其进队
            enQueue(qu，p->lchild);
        if (p->rchild!=NULL)		//有右孩子时将其进队
            enQueue(qu，p->rchild);
    } 
}

线索二叉树

对于具有n个结点的二叉树，采用二叉链存储结构时，每个结点有两个指针域，总共有2n个指针域。其中只有n-1个结点被有效指针所指向，即有n-1个非空指针域。所以共有2n-(n-1) = n+1个空链域。可以用它来存放当前结点的直接前驱和后继等线索，以加快查找速度。

赫夫曼树及其应用

赫夫曼树的定义

带权路径长度：结点到根的路径长度与结点上权的乘积
树的带权路径长度：树中所有叶子结点的带权路径长度之和
$WPL={\sum }_{i=1}^n{w}_i{l}_i$
带权路径长度最小的树称为赫夫曼树（Huffman）

构造赫夫曼树的过程

1. 给定的n个权值{W1，W2，…，Wn}构造n棵只有一个叶结点的二叉树，从而得到一个二叉树的集合F={T1，T2，…，Tn}。
2. 在F中选取根结点的权值最小和次小的两棵二叉树作为左、右子树构造一棵新的二叉树，这棵新的二叉树根结点的权值为其左、右子树根结点权值之和。
3. 在集合F中删除作为左、右子树的两棵二叉树，并将新建立的二叉树加入到集合F中。
4. 重复2、3两步，当F中只剩下一棵二叉树时，这棵二叉树便是所要建立的赫夫曼树。
   

void CreatHuffmanTree ( )
{    int i,m;
     if(n<=1)       return;
     m=2*n-1;
     for( i=1;i<=m;++i)
     {       HT[i].lchild=0;      HT[i].rchild=0;           HT[i].parent=0;            }
     for( i=1;i<=n;++i)       cin>>HT[i].weight;   
     for( i=n+1;i<=m;++i)       //构造  Huffman树
     {       Select(i-1, s1, s2);   //在HT[1..i-1]中选择两个其双亲域为0,且权值最小的结点,并返回它们在HT中的序号s1和s2
            HT[s1].parent=i;   HT[s2] .parent=i;      //表示从F中删除s1,s2
            HT[i].lchild=s1;    HT[i].rchild=s2 ;     //s1,s2分别作为i的左右孩子
            HT[i].weight=HT[s1].weight + HT[s2].weight; //权值为左右孩子权值之和
     }
} 

void Select(int i,int &s1,int &s2)
{ //在HT[1..i]中选择两个其双亲域为0，且权值最小的结点，并返回它们在HT中的序号s1和s2
	int k,v1,v2;	v1 = infinity;	v2 = infinity;	s1 = 0;	s2 = 0;
	for(k=1;k<=s;k++)
	{   if(HT[k].parent == 0)
		if(HT[k].weight < v1)
		{v2 = v1;   s2 = s1;   v1 = HT[k].weight;   s1 = k;	}
		else if( HT[k].weight < v2 )
		{v2 = HT[k].weight;	s2 = k;}
	}
}

构造huffman编码

void Huffman_Code()
{//从叶子到根逆向求每个字符的赫夫曼编码，存储在编码表HC中
    int i, j,k,c,f;
    for( i=1; i <= n; i++) //逐个字符求赫夫曼编码
    {   k= 0;     //字符编码计数
        c=i;        f=HT[i].parent;
        while(f!=0)       //从叶子结点开始向上回溯，直到根结点
        {     k++;          //回溯一次k向后移动一个位置
             if(HT[f].lchild==c)   HC[i][k]=0; //结点c是f的左孩子，则生成编码0
             else        HC[i][k]=1;         //结点c是f的右孩子，则生成编码1
             c=f; f=HT[f].parent;        //继续向上回溯
        }      //求出第i个字符的编码 
        HC[i][0]=k;      //记录第i个字符的码长
     } 
     for (i=1;i<=n;i++)    //逆向输出 huffman编码表
     {      printf("%d:",ht[i].weight);
     for(j=HC[i][0];j>=1;j--)          printf("%d",HC[i][j]);
     printf("n");
     }
}

最后

以上就是平淡高跟鞋为你收集整理的数据结构第6章 树和二叉树树的定义和基本术语二叉树赫夫曼树及其应用的全部内容，希望文章能够帮你解决数据结构第6章 树和二叉树树的定义和基本术语二叉树赫夫曼树及其应用所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。