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

数据结构期末复习系列 · 持续更新：

图的深度遍历和广度遍历 图的邻接矩阵和邻接表表示 串的基本知识及操作 数据结构期末考试提纲（重点复习知识汇总） 期末考试 | 数据结构第五章 | 树和二叉树·附习题 期末考试 | 数据结构第七章 | 查找（顺序表、树表、哈希表）·附习题 期末考试 | 数据结构第八章 | 内部排序（插入/选择/冒泡/快排/堆排序/基数排序） 稀疏矩阵的三种表示方法·转置矩阵·矩阵相乘·十字链表表示法·数组的基本操作 栈的简单应用：数制转换·括号的匹配检验·行编辑·迷宫求解·表达式求值·递归调用 队列的基本概念·循环队列·银行排队场景驱动管理 线性表和链表的基本操作：初始化·定位查询·插入元素·删除·查找·双向链表

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.树和二叉树互相转换

二叉树简单，遂可转换树/森林转换为二叉树处理 加线（兄弟连虚线）→抹线（每结点仅保留与左孩子连线）

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

将每棵树转换成二叉树→将后棵树的根结点作为前棵树的根结点的右孩子，

8.先根遍历和后根遍历

（感觉好像就是先序遍历和后序遍历）

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