（期末考试prepare）数据结构（C语言版）第五章——树和二叉树·附习题

秒速五厘米 2023-02-17 05:28 12阅读 0赞

**数据结构期末复习系列【陆续更新】**  
→**数据结构期末考试提纲：**  
https://blog.csdn.net/qq\_45832958/article/details/106645158  
→**查找（顺序表、树表、哈希表）·题型实练：**  
https://blog.csdn.net/qq\_45832958/article/details/106594323  
→**内部排序·题型实练：**  
https://blog.csdn.net/qq\_45832958/article/details/106542994

### 树和二叉树 ###

*  1.二叉树的存储结构
 *   *  ①顺序存储
     *  ②链式存储
 *  2.遍历
 *   *  遍历的递归实现
     *   *  ①先序
         *  ②中序
         *  ③后序
     *  遍历的非递归实现
     *   *  ①先序
         *  ②中序
         *  ③后序
         *  例：统计二叉树中叶子结点的个数
         *  例：求二叉树深度
 *  4.二叉树的二叉线索链表
 *  5.树的双亲表示法
 *  6.树和二叉树互相转换
 *  7.森林和二叉树相互转换
 *  8.先根遍历和后根遍历
 *  9.哈夫曼树
 *   *  后记

# 1.二叉树的存储结构 #

## ①顺序存储 ##

#define MAX_TREE_SIZE 100
    typedef TElemType SqBiTree[MAX_TREE SIZE];
    SqBiTree BT;

## ②链式存储 ##

typedef struct BiTNode{
    TElemType data;
    struct BiTNode *rchild,*lchild;
    }BiTNode,*BiTree;

# 2.遍历 #

若以D/L/R分别表示访问根结点、左子树和右子树，  
则DLR为先序遍历，LDR为中序遍历，LRD为后序遍历

## 遍历的递归实现 ##

### ①先序 ###

void PreOrder(BiTree BT)
    {
         if(BT)
         {
             printf(BT->data);
             PreOrder(BT->lchild);
             PreOrder(BT->rchild);
         }
    }

### ②中序 ###

void InOrder(BiTree BT)
    {
    	if(BT)
    	{
    		InOrder(BT->lchild);
    		printf(BT->data);
    		InOrder(BT->rchild);
    	}
    }

### ③后序 ###

void PostOrder(BiTree BT)
    {
    	if(BT)
    	{
    			PostOrder(BT->lchild);
    			printf(BT->data);
    			PostOrder(BT->rchild);
    	}
    }

## 遍历的非递归实现 ##

### ①先序 ###

void NRPreOrder(BiTree BT)
    {
    	BiTree stack[MAX_TREE_SIZE],p;
    	int top;
    	if(BT){
    	{
    		top=1;
    		stack[top]=BT;//根结点入栈
    		while(top)
    		{
    			p=stack[top];//（逻辑上）退栈并访问该结点
    			top--;
    			printf(p->data);
    			if(p->rchild)
    			{
    				top++;
    				stack[top]=p->rchld;
    			  }
    			if(p->lchild)
    		    {
    				top++;
    				stack[top]=p->lchild;
    	    	}
    		}	
    	}
    }

### ②中序 ###

void NRInOrder(BiTree BT)
    {
    	BiTree stack[MAZ_TREE_SIZE],p;
        int top=0;
        p=BT;
        do{
    			while(p)//扫描p的所有左结点并入栈
    			{
    					top++;
    					stack[top]=p;
    				    p=p->lchild;
    			}
    			if(top>0)
    			{
    				p=stack[top];
    				top--;
    				printf(p->data);
    				p=p->rchild;
    			}
    		}while(p||top>0)
    }

### ③后序 ###

void NRPostOrder(BiTree BT)
    {
    	BiTree stack[MAX_TREE_SIZE],p;
    	int tag[MAX_TREE_SIZE];
    	int top=0;
    	p=BT;
        do{
    			while(p!=NULL)
    			{
    				top++;
    				stack[top]=p;
    				p->lchild;
    				tag[top]=0;
    			}
    			if(top>0)
    			{
    				if(tag[top]==1)
    				{
    					printf(stack[top]->data);
    					top--;
    				}
    				else
    				{
    						p=stack[top];
    						if(tag>0)
    						{
    							p=p->rchild;
    							tag[top]=1;
    						}
    				}
    			}
    	   }while(p||top>0);
    }

### 例：统计二叉树中叶子结点的个数 ###

其实就是将遍历改成统计

void CountLeaves(BiTree BT,int &count)
    {
    	if(BT)
    	{
    		if(!BT->lchild&&!BT->rchild) count++;
    		CountLeaves(BT->lchild,count);
    		CountLeaves(BT->rchild,count)
    	}
    }

### 例：求二叉树深度 ###

int BiTreeDepth(BiTree BT)
    {
    int lchilddep,rchilddep;
    if(!BT) return 0;
    else
    {
    lchilddep=BiTreeDepth(BT->lchild);
    rchilddep=BiTreeDepth(BT->rchild);
    return (lchilddep>rchilddep)?(1+lchilddep):(1+rchilddep);
    }
    }

# 4.二叉树的二叉线索链表 #

typedef struct BiThrNode{
    TElemType data;
    struct BiThrNode *lchild,*rchild;
    int LTag,RTag;
    }BiThrNode,*BiThrTree;

# 5.树的双亲表示法 #

#defint MAX_TREE_SIZE 100
    typedef struct PTNode{
    	TElemType data;
    	int parent;
    }PTNode;
    typedef struct{
    	PTNode nodes[MAX_TREE_SIZE];
    	int r,n;//根的位置和结点数
    }PTree;

# 6.树和二叉树互相转换 #

二叉树简单，遂可转换树/森林转换为二叉树处理  
加线（兄弟连虚线）→抹线（每结点仅保留与左孩子连线）  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1ODMyOTU4_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1ODMyOTU4_size_16_color_FFFFFF_t_70 1]

# 7.森林和二叉树相互转换 #

将每棵树转换成二叉树→将后棵树的根结点作为前棵树的根结点的右孩子，  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1ODMyOTU4_size_16_color_FFFFFF_t_70 2]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1ODMyOTU4_size_16_color_FFFFFF_t_70 3]

# 8.先根遍历和后根遍历 #

（感觉好像就是先序遍历和后序遍历）  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1ODMyOTU4_size_16_color_FFFFFF_t_70 4]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1ODMyOTU4_size_16_color_FFFFFF_t_70 5]

# 9.哈夫曼树 #

（除了叶子结点外）度均为2

构建**哈夫曼树**：

#define INFINITY INT_MAX
    #define MAXLEAF 30
    #define MAXNODE MAXLEAF*2-1
    typedef struct{
    int weight;
    int parent,lchild,rchild;
    }HTNode;
    
    void HuffmanTree(HTNode HuffNode[],int n) //n是叶子结点的数量
    {
    	int i,j,m1,m2,x1,x2;
    	for(i=0;i<2*n-1;i++)//HuffNode[]初始化
    	{
    	HuffNode[i].weight=0;
    	HuffNode[i].parent=-1;
    	HuffNode[i].lchild=-1;
    	HuffNode[i].rchild=-1;
        }
    	for(i=0;i<n;i++)
    		scanf("%d",&HuffNode[i].weight);
    	for(i=0;i<n-1;i++)//构造HuffmanTree
    	{
    		m1=m2=INTINITY;
    		X1=X2=-1;
    		for(j=0;j<n+1;j++)
    		{
    			if(HuffNode[j].weight<m1&&HuffNode[j].parent==-1)
    			{
    				m1=m2;
    				x2=x1;
    				m1=HuffNode[j].weight;
    				x1=j;
    			}
    			else if(HuffNode[j].weight<m2&&HuffNode[j].parent==-1)
    			{
    				m2=HuffNode[j].weight;
    				x2=j;
    			}
    		}
    		//将两棵子树合并为一棵
    		HuffNode[x1].parent=n+1;
    		HuffNode[x2].parent=n+1;
    		HuffNode[n+1].weight=HuffNode[x1].weight+HuffNode[x2].weight;
    		HuffNode[m+i].lchild=x1;
    		HuffNode[n+i].rchild=x2;
       }
    }

## 后记 ##

1.Textbook  
所用课本为朱昌杰所著《数据结构（C语言版）（第二版）》  
私认为这本书非常适合新手使用，代码知识简单，作者逻辑清晰。  
之前还看过严蔚敏老师的数据结构著作，写得非常好，代码的健壮性也非常强，但是很多东西讲得很深较难，新手很多地方会看不懂。  
但是严老师的书明显比朱老师的书挖掘的知识更深更详细，适合有数据结构基础后深造使用。

2.杂谈总结  
唉，讲真太忙了这几个月，学的知识广多杂但是肤浅，很多基础代码都是云里雾里。自认为学了那么东西，但是到头来却一点都想不起来。  
这就是因为缺乏实践、缺乏每日持续性学习，而只是总心血来潮地隔一段时间去花几天的全部时间去学习某一方向。  
所以**每天少量、及时复盘、大量实践**非常重要。  
学习知识贵在不要心急，一口吃不了个胖子。暑假还要把数据结构从头到尾过一遍，刷刷题。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1ODMyOTU4_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200612214445982.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1ODMyOTU4,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1ODMyOTU4_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200612214459548.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1ODMyOTU4,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1ODMyOTU4_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200612214516662.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1ODMyOTU4,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1ODMyOTU4_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20200612214532526.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1ODMyOTU4,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1ODMyOTU4_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20200612221204217.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1ODMyOTU4,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1ODMyOTU4_size_16_color_FFFFFF_t_70 5]: https://img-blog.csdnimg.cn/20200612221238337.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1ODMyOTU4,size_16,color_FFFFFF,t_70