数据结构— — 二叉树的遍历

  🎃Hello，大家好，今天我们要做的是 二叉树的遍历。

---

🎯目的：

1、掌握二叉树的特点及其存储方式。

2、掌握二叉树的创建。

3、掌握二叉树前序、中序、后序遍历的基本方法及应用。

---

🎯内容：

1、用前序方法建立一棵二叉树。

2、编写前序遍历二叉树的程序。

3、编写中序遍历二叉树的程序。

4、编写后序遍历二叉树的程序。

5、编写程序实现二叉树中的一些基本操作。

---

🎯环境：

TC或VC++。

---

🎯步骤：

1、二叉树的二叉链表存储类型定义：

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

2、使用先序遍历建立下图所示的二叉树：      

3、编程实现以上二叉树的前序、中序和后序遍历操作，并输出遍历序列：

（1）先序遍历二叉树并输出遍历序列（ABCDEGF）；

（2）中序遍历二叉树并输出遍历序列（CBEGDFA）；

（3）后序遍历二叉树并输出遍历序列（CGEFDBA）。

4、计算二叉树的深度：

算法基本思想：

递归计算左子树的深度记为m；递归计算右子树的深度记为n；如果m大于n，二叉树的深度为m+1，否则为n+1。

5、统计二叉树中结点的总数：

算法基本思想：

如果是空树，则结点个数为0；结点个数为左子树的结点个数+右子树的结点个数再+1。

6、统计二叉树中叶子结点的个数：

算法基本思想：

先序（或中序或后序）遍历二叉树，在遍历过程中查找叶子结点，并计数。由此，需在遍历算法中增添一个“计数”的参数，并将算法中“访问结点” 的操作改为：若是叶子，则计数器增1。

7、在主函数中实现相关函数的调用。

#include 
 
using namespace std;
 
typedef struct BiTNode{//定义二叉树
 
       char data;
 
       struct BiTNode *lchild,*rchild;
 
}BiTNode,*BiTree;
 
void CreateBiTree(BiTree &T){//先序遍历二叉树
 
       char ch;
 
       cin>>ch;
 
       if(ch=='#')
 
              T=NULL;//结束，空树；
 
       else{
 
              T=new BiTNode;
 
              T->data=ch;
 
              CreateBiTree(T->lchild);
 
              CreateBiTree(T->rchild);
 
       }
 
}
 
void PreOrderTraverse(BiTree T){//先序遍历输出
 
       if(T){
 
              cout<data;
 
              PreOrderTraverse(T->lchild);
 
              PreOrderTraverse(T->rchild);
 
       }
 
}
 
void InOrderTraverse(BiTree T){//中序遍历输出
 
       if(T){
 
              InOrderTraverse(T->lchild);
 
              cout<data;
 
              InOrderTraverse(T->rchild);
 
       }
 
}
 
void PostOrderTraverse(BiTree T){//后序遍历输出
 
       if(T){
 
              PostOrderTraverse(T->lchild);
 
              PostOrderTraverse(T->rchild);
 
              cout<data;
 
       }
 
}
 
int Depth(BiTree T){//计算深度
 
       int m,n;
 
       if(T==NULL)
 
              return 0;//空树，深度为0
 
       else
 
       {
 
              m=Depth(T->lchild);
 
              n=Depth(T->rchild);
 
              if(m>n)
 
                     return m+1;
 
              else{
 
                     return n+1;
 
              }
 
       }
 
}
 
int NodeCount(BiTree T){//总结点
 
       if(T==NULL){
 
              return 0;
 
       }
 
       else
 
              return  NodeCount(T->lchild)+ NodeCount(T->rchild)+1;
 
             
 
}
 
int LeafCount(BiTree T){//叶子节点
 
       if(T==NULL)
 
              return 0;
 
       if(T->rchild==NULL&&T->lchild==NULL){
 
              return 1;
 
       }
 
       else{
 
              return LeafCount(T->lchild)+LeafCount(T->rchild);
 
       }
 
}
 
int main(){
 
       BiTree t;
 
       cout<<"请输入所要建立的二叉树的序列:"<
 
       cout<<"提示：先序为:(ABC##DE#G##F###)"<
 
       CreateBiTree(t);
 
       cout<
 
       cout<<"先序遍历输出为："<
 
       PreOrderTraverse(t);
 
       cout<
 
       cout<<"中序遍历输出为："<
 
       InOrderTraverse(t);
 
       cout<
 
       cout<<"后序遍历输出为："<
 
       PostOrderTraverse(t);
 
       cout<
 
       cout<<"二叉树的深度为："<
 
       cout<<Depth(t)<
 
       cout<<"二叉树的总结点为:"<
 
       cout<<NodeCount(t)<
 
       cout<<"二叉树的叶子节点为："<
 
       cout<<LeafCount(t)<
 
       return 0;
 
}

[附加题]

哈夫曼树的构造：

根据给定的N个权值{7,6,3,5}建立哈夫曼树，并输出终态表查看构造结果。

终态表：

🎯 结果：

#include 
using namespace std;
typedef struct{
	int weight;
	int parent,lchild,rchild;
}HTNode,*HuffmanTree;
void Select(HuffmanTree HT,int x,int &s1,int &s2); 
void CreateHuffmanTree(HuffmanTree &HT,int n){
	if(n<=1)
		return;
	int m=2*n-1;
	HT=new HTNode[m+1];//0号不用 
	for(int i=1;i<=m;i++){//初始化 
		HT[i].parent=0;
		HT[i].lchild=0;
		HT[i].rchild=0;
	}
	cout<<"输入哈夫曼树的权值（用空格隔开）:"<
	for(int i=1;i<=n;i++){//输入叶子结点的权值 
		cin>>HT[i].weight;	
	}
	int s1,s2,i;	
	for(i=n+1;i<=m;i++){
		Select(HT,i-1,s1,s2);
		HT[s1].parent=i;
		HT[s2].parent=i; 
		HT[i].lchild=s1;
		HT[i].rchild=s2;
		HT[i].weight=HT[s1].weight+HT[s2].weight;
	}
}
void Select(HuffmanTree HT,int x,int &s1,int &s2){
	int min1=100000;
	for(int k=1;k<=x;k++){
		if(HT[k].parent==0&&HT[k].weight
			min1=HT[k].weight;
			s1=k;
		}
	}
//	HT[s1].weight=100000000;
	HT[s1].parent=1;
	int min2=1000000;
	for(int k=1;k<=x;k++){
		if(HT[k].parent==0&&HT[k].weight
			min2=HT[k].weight;
			s2=k;
		}
	}
//	HT[s1].weight=min1;
	HT[s1].parent=0;
}
int main(){
	HuffmanTree ht;
	int n=4;
	CreateHuffmanTree(ht,n);
	printf("终态表如下:\n序号 权值 parent lchild rchild \n");
	for(int i=1;i<=2*n-1;i++){
	printf(" %2d   %2d    %2d    %2d    %2d \n",i,ht[i].weight,ht[i].parent,ht[i].lchild,ht[i].rchild);
	}
}

 🎃以上是本期的所有内容了，请大佬多多在评论区指正！

 🌞我是IT闫，期待你的关注！！！❤️