🎯目的：
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 <iostream> 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<<T->data; PreOrderTraverse(T->lchild); PreOrderTraverse(T->rchild); } } void InOrderTraverse(BiTree T){//中序遍历输出 if(T){ InOrderTraverse(T->lchild); cout<<T->data; InOrderTraverse(T->rchild); } } void PostOrderTraverse(BiTree T){//后序遍历输出 if(T){ PostOrderTraverse(T->lchild); PostOrderTraverse(T->rchild); cout<<T->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<<"请输入所要建立的二叉树的序列:"<<endl; cout<<"提示：先序为:(ABC##DE#G##F###)"<<endl; CreateBiTree(t); cout<<endl; cout<<"先序遍历输出为："<<endl; PreOrderTraverse(t); cout<<endl; cout<<"中序遍历输出为："<<endl; InOrderTraverse(t); cout<<endl; cout<<"后序遍历输出为："<<endl; PostOrderTraverse(t); cout<<endl; cout<<"二叉树的深度为："<<endl; cout<<Depth(t)<<endl; cout<<"二叉树的总结点为:"<<endl; cout<<NodeCount(t)<<endl; cout<<"二叉树的叶子节点为："<<endl; cout<<LeafCount(t)<<endl; return 0; }
[附加题]
哈夫曼树的构造：
根据给定的N个权值{7,6,3,5}建立哈夫曼树，并输出终态表查看构造结果。
终态表：
序号 |
权值 |
parent |
lchild |
rchild |
1 |
7 |
6 |
0 |
0 |
2 |
6 |
6 |
0 |
0 |
3 |
3 |
5 |
0 |
0 |
4 |
5 |
5 |
0 |
0 |
5 |
8 |
7 |
3 |
4 |
6 |
13 |
7 |
2 |
1 |
7 |
21 |
0 |
5 |
6 |
🎯 结果：
#include <iostream> 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<<"输入哈夫曼树的权值（用空格隔开）:"<<endl; 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){ 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){ 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); } }
