数据结构第六章——树和二叉树_定长编码集的二叉树

一、树的定义和基本术语

1.树是n个节点的有限集。在一棵非空树种：

1）有且仅有一个特定的称为根（root）的节点；

2）当n>1时，其余结点可分为m个互不相交的有限集T1,T2...Tm，其中每个集合本身又是一棵树，称为根的子树（subtree）

2.四种表示方法：

 

 3.基本术语

（1）结点的度（degree）：节点具有的子树数

（2）叶子节点：度为0的结点（没有子树的结点）

（3）分支结点：度大于零的结点

（4）内部节点：除根节点外的分支节点

（5）树的度：一棵树中各个节点度数的最大值

（6）儿子结点和父亲结点：一个结点的子树的根称为该结点的儿子结点；该结点称为其孩子结点的父亲结点。

（7）兄弟结点：同一个结点的儿子结点之间互称兄弟结点

（8）路径：从树中一个结点到另一个结点之间的分支构成这两个结点之间的路径

（9）子孙结点：一个结点的子树中所有结点

（10）祖先结点：从根结点到达一个结点的路径上所有的结点都叫该结点的祖先结点

（11）树的深度：根结点为第一层，其儿子结点为第二层。一棵树中结点的最大层数为树的深度或高度。

（12）有序树和无序树：若将树中每个结点的各子树看成是从左到右有次序的即为有序树，否则为无序树。

（13）森林（forest）：m（>=0）颗互不相交的树的集合。

 4.逻辑特征

---

二、二叉树

1.二叉树或为空树，或是由一个根结点加上两颗分别称为左子树和右子树的、互不相交的二叉树组成。二叉树中不存在度大于2的结点且二叉树的子树有左子树和右子树之分。

 2.性质

（1）在二叉树的第 i 层上至多有2^i-1 个结点 (i≥1) 。

（2）深度为 k 的二叉树至多含 2^k-1 个结点（k≥1）。

（3）对任何一棵二叉树，若它含有n0 个叶子结点、n2 个度为 2 的结点，则必存在关系式：n0 = n2+1。

（4）具有 n 个结点的完全二叉树的深度为 ( log2n) +1 。

（5）

 

3.满二叉树：深度为k且有2^k-1个结点的二叉树。（从上到下从左到右按自然数编号）

 4.完全二叉树：深度为k的二叉树中所含n个结点和深度k的满二叉树中编号为1~n的结点一一对应。（没有中途空缺，有右就有左，有左可以没右）

5.完全二叉树特点

（1）除最后一层外，每一层都取最大结点数，最后一层结点都集中且连续分布在该层最左边的若干位置。

（2）叶子结点只可能在层次最大的两层出现。

（3）对任一结点，若其右分支下的子孙的最大层次为L，则其左分支下的子孙的最大层次为L 或L+1。

6.二叉树的存储结构

（1）二叉树的顺序存储

#define  MAX_TREE_SIZE  100      
             // 二叉树的最大结点数
typedef TElemType  
                 SqBiTree[MAX_TREE_SIZE];   
             // 0号单元存储根结点
SqBiTree  bt;
//即将 bt 定义为含有MAX_TREE_SIZE个 TElemType 类型元素的一维数组。 
 

一般二叉树编号规则：根结点的编号为1；对于编号为i的结点，左孩子如果存在，则编号为2i，右孩子如果存在则编号为2i+1。

（2）二叉树的链式存储

 

typedef struct BiTNode { // 结点结构
    TElemType      data;
    struct BiTNode  *lchild, *rchild; 
                                     // 左右孩子指针
} BiTNode, *BiTree;

三、遍历二叉树和线索二叉树

L/D/R 左 根 右

1.先左后右

（1）DLR 前序遍历算法

void preorder (NODE  *p)
{    // 前序遍历二叉树 
      if (p!=NULL)
      {	 
         printf("%c", p->data);   
         preorder(p->lchild);
 	     preorder(p->rchild); 
       }
}

（2）LDR 中序

void  inorder (NODE  *p)
{    // 中序遍历二叉树 
      if (p!=NULL)
      {	     inorder(p->lchild);
             print("%c", p->data);   
	     inorder(p->rchild); 
       }
}

（3）LRD 后序

void postorder (NODE  *p)
{    // 后序遍历二叉树 
      if (p!=NULL)
      {	     postorder(p->lchild);
 	     postorder(p->rchild);                        
             printf("%c", p->data); 
       }
}

2.表达式的二叉树表示

3.遍历算法的应用举例

（1）输出二叉树中的结点（先序遍历）

void Preorder (BiTree root)
{      if (root!=NULL)
       {
               printf(root->data); 
               Preorder(root->lchild); 
               Preorder(root->rchild);   
       }
}

（2）统计二叉树中叶子节点的个数（先序遍历）

若是叶子，计数器+1

int  LeafCount=0;
void  LeafNum(BiTree bt)   //先序遍历
{    if (bt!=NULL)
     {
  	   if(bt->LChild == NULL && bt->RChild == NULL)
         LeafCount++;	
       LeafNum(bt->LChild);
	   LeafNum(bt->RChild);
     }
}

（3）求二叉树的深度（后序遍历） 

左右子树深度的最大值+1

int PostTreeDepth(BiTree bt) 
{    
  int hl,hr,max;
  if (bt!=NULL)
  {	
    hl=PostTreeDepth(bt->LChild); 		
    hr=PostTreeDepth(bt->RChild); 		
    max=hl>hr?hl:hr; 
    return(max+1); 
  }
  else return(0);    /* 如果是空树，则返回0 */
}

4.二叉树遍历的非递归实现——中序遍历（栈）

（1）指向根结点的指针进栈；

（2）栈顶指针非空则其左孩子指针进栈；直到栈顶指针为空；

（3）弹出栈顶空指针，若栈非空，再弹出栈顶指针并访问该指针指向的结点；该指针指向结点的右孩子指针入栈；

（4）继续第（2）步的操作，直到栈为空。

Status InOrderTraverse(BiTree T, Status (*Visit)(ElemType)) 
{
	InitStack(S);  Push(S, T);  // 根指针进栈
	while (!StackEmpty(S)) 
	{	 // 向左走到尽头
		while (GetTop(S, p) && p)   Push(S, p->lchild); 			
        Pop(S, p);                // 空指针退栈
		if (!StackEmpty(S)) 
		{     // 访问结点，向右一步
			Pop(S, p);  
			if (!Visit(p->data)) return ERROR;
			Push(S, p->rchild);
		}
	}
	return OK;
} // InOrderTraverse

5.二叉树的层次遍历（队列）

（1）访问该元素所指结点；

（2）若该元素所指结点的左、右孩子结点非空，则将该元素所指结点的左孩子指针和右孩子指针顺序入队。 此过程不断进行，当队列为空时，二叉树的层次遍历结束。

void LevelOrder（BiTree    bt）
 { BiTree  Queue[MAXNODE];   //一维数组用以实现队列 
      int front,rear;       //队首元素和队尾元素
      if (bt = = NULL) return;
      front= -1;   rear=0;
      queue[rear]= bt;
      while(front!=rear)
         {front++;
          Visit ( queue[front]->data );      /*访问队首结点的数据域*/
          if (queue[front]->lchild!=NULL)     /*左孩子结点入队*/
           { rear++;
             queue[rear]= queue[front]->lchild;            }
          if (queue[front]->rchild!=NULL)   /*右孩子结点入队列*/
           { rear++;
             queue[rear]=queue[front]->rchild;            }
         }
}

（过程看PPT演示） 

6.建立二叉树

首先读入当前根结点数据，如果是“＃”，则表示当前树根置为空，否则申请一个新结点，存入当前根结点的数据，分别用当前根结点的左子域和右子域进行递归调用，创建左、右子树。

BiTree  CreateBiTree()
 {    char ch;  BiTreeNode *p;
      ch=getchar();
      if (ch==‘#’)    return NULL;
      else	
      {    p=(BiTreeNode *) malloc(sizeof(BiTreeNode));
	   p->data=ch;
	   p->LChild=CreateBiTree();
	   p->RChild=CreateBiTree();
	   return (p);
    }
}

7.线索二叉树

 

 指向前驱和后继的指针叫线索，具有线索的二叉树为线索二叉树。

typedef  enum  PointerTag {Link,Thread};
 
typedef  struct  BiThrNode
 
        {   TElemType   data;
             PointerTag   LTag,RTag;
             struct BiThrNode *lchild,*rchild;
         }BiThrNode , *BiThrTree ;  

 PPT105 将二叉树中序线索化

四、树和森林

1.树的存储结构

（1）双亲表示法

 （2）孩子表示法

 （3）孩子兄弟表示法

2.树、森林与二叉树的相互转换

树-->二叉树

（1）加线：在各亲兄弟之间加一虚线。

（2）抹线：抹掉（除第一个孩子外）该结点到其余孩子之间的连线。

（3）旋转：新加上去的虚线改实线且均向右斜（rchild），原有的连线均向左斜（lchild)，使之结构层次分明。

 森林——>二叉树

（1）将各棵树分别转换为二叉树。

（2）按给出森林中树的次序，依次将后一 棵二叉树作为前一棵二叉树根结点的右子树，则第一棵树的根结点是转换后二叉树的根。

 二叉树-->树

前提：二叉树的根结点无右孩子 

 二叉树-->森林

3.树、森林的遍历

（1）先根遍历

若森林F为空, 返回；否则

访问F的第一棵树的根结点；

先根次序遍历第一棵树的子树森林；

先根次序遍历其它树组成的森林。

（2）后根遍历

若森林F为空，返回；否则：

中根次序遍历第一棵树的子树森林；

访问F的第一棵树的根结点；

中根次序序遍历其它树组成的森林。

五、树与等价问题

六、Huffman树及其应用

1.基本概念

（1）路径与路径长度：从树中一个结点到另外一个结点之间的分支称为这两个结点之间的路径，路径上分支的数目称做路径长度。

（2）结点的带权路径长度：从根结点到结点之间的路径长度与该结点上权值的乘积。

（3）树的带权路径长度：树中所有叶子结点的带权路径长度之和。

 2.哈夫曼树基本概念

（1）n 个带权叶子结点构成的所有二叉树中，必存在一棵其带权路径长度WPL最小值的树，我们称之为最优二叉树或哈夫曼树。

（2）特点：权值越大的叶子结点离根结点越近。

3.哈夫曼编码

（1）等长编码

（2）不等长编码

（3）前缀编码：任何一个字符的编码都不是同一字符集中另一个字符的编码的前缀。

 

4.哈夫曼算法

 

哈夫曼算法的实现——类型定义
#define N  20		   /*叶子结点个数的最大值*/
#define M   2*N-1         /*所有结点个数的最大值*/
typedef struct
{	int weight; 
     int parent;		   /*双亲的下标*/
	int LChild;            /*左孩子的下标*/
     int RChild;           /*右孩子的下标*/
}HTNode,HuffmanTree[M+1];  /*Huffman 树，0号
                                                                        单元未用* /

（1）创建哈夫曼树

void CrtHuffmanTree(HuffmanTree ht,int w[ ],int n)
{   int i, j ,k , s1 , s2;	
    for(i=1;i<=n;i++)         /*初始化*/
	{	 ht[i].weight=w[i];      ht[i].Parent=0;	  
          ht[i].LChild=0;	 ht[i].RChild=0;
	} 
    m=2*n-1;
    for(i=n+1;i<=m;i++)   /*初始化*/
	{	 ht[i].weight=0;      ht[i].Parent=0;	  
          ht[i].LChild=0;	 ht[i].RChild=0;
	}
     /*选择   合并*/
}
 
      /*选择、合并n-1次*/	
	for(i=n+1;i<=m;i++) 
    {	select (ht,i-1,&s1,&s2);
		ht[i].weight=ht[s1].weight+ht[s2].weight;
		ht[s1].parent=i;      
         ht[s2].parent=i;
		ht[i].LChild=s1;   
         ht[i].RChild=s2;
	} 

 （2）Huffman算法实现——选择函数

#define  MAXINT  32767
select(HuffmanTree ht, int pos, int *s1, int *s2 )
{  int  j , m1, m2;    /*m1存放最小权值,s1是m1在数组的下标*/         
   m1=m2=MAXINT;  /*m2存放次小权值,s2是m2在数组的下标*/
   for(j=1;j<＝pos;j++)    
   {   if (ht[j].weight<m1 && ht[j].parent==0)  
       { 	   m2 = m1;     *s2=*s1;	 *s1=j;
   m1 = ht[j].weight;
  }
  else  if(ht[j].weight<m2 && ht[j].parent==0)
  {	   m2 = ht[j].weight; 	 
             *s2 = j;
  }
   }
}
 
typedef char *HuffmanCode[n+1];          /*Huffman 编码*/
void CrtHuffmanCode(HuffmanTree ht,HuffmanCode hc,int n)
{	char *cd;   cd=(char *)malloc(n*sizeof(char));
	cd[n-1]=‘\0’;
	for(i=1;i<=n;i++)
    {	start=n-1; c=i; 
          p=ht[i].parent;
		while(p!=0)
         {    --start;
		    if(ht[p].LChild==c)  
                    cd[start]=‘0’;
		    else  
                    cd[start]=‘1’;
		    c=p;  p=ht[p].parent; 
         }
	   hc[i]=(char *)malloc((n-start)*sizeof(char));
	   strcpy(hc[i],&cd[start]);  
     }
	free(cd);