（数据结构）二叉树的基本操作
实验内容：
1、 按先序次序输入二叉树中结点的值（一个字符），利用某个特殊字符（例如`@`）表示空树，生成二叉树的二叉链表存储结构。
2、 按先、中、后序递归遍历二叉树，之后结合栈的应用，将中序遍历算法改为非递归算法。
3、利用二叉树的递归算法求二叉树的高度 。
4、利用二叉树的递归算法求二叉树的叶子个数。
5、利用队列实现二叉树的层次遍历。
*6、设有字符集{A,B,C,D}，各字符在电文中出现的次数集为{1,3,4,7}，编程实现哈夫曼树的构造，并在此基础上编程实现哈夫曼编码。
7、编写一个主函数，调试上述算法。
代码：
#include <iostream>
#include <cstdio>
#include <time.h>
#include <cstdlib>
#include <stack>
#include <queue>
using namespace std;
int LeafCount=0;
typedef struct Node{
char data;
struct Node *Lchild;
struct Node *Rchild;
}BitNode,*BiTree;
void CreateBiTree(BiTree *bt){
char ch;
ch=getchar();
// cin>>ch;
if(ch!='@'){
*bt=(BiTree)malloc(sizeof(BitNode));
(*bt)->data=ch;
CreateBiTree(&((*bt)->Lchild));
CreateBiTree(&((*bt)->Rchild));
}
else *bt=NULL;
}
void PreOrder(BiTree bt){//先序
if(bt==NULL) return;
cout<<bt->data<<" ";
PreOrder(bt->Lchild);
PreOrder(bt->Rchild);
}
void InOrder(BiTree bt){//中序
if(bt==NULL) return;
InOrder(bt->Lchild);
cout<<bt->data<<" ";
InOrder(bt->Rchild);
}
void PostOrder(BiTree bt){//后序
if(bt==NULL) return;
PostOrder(bt->Lchild);
PostOrder(bt->Rchild);
cout<<bt->data<<" ";
}
void inOrder2(BiTree root){//非递归中序遍历
stack<BiTree> s;
BiTree p=root;
while(p!=NULL||!s.empty())
{
while(p!=NULL)
{
s.push(p);
p=p->Lchild;
}
if(!s.empty())
{
p=s.top();
cout<<p->data<<" ";
s.pop();
p=p->Rchild;
}
}
}
int depth(BiTree root){
int ldepth,rdepth;
if(!root)
return 0;
else{
ldepth =depth(root->Lchild)+1;
rdepth =depth(root->Rchild)+1;
return max(ldepth,rdepth);
}
cout<<ldepth<<" "<<rdepth<<endl;
}
void Countleaf(BiTree root){
if(root!=NULL){
Countleaf(root->Lchild);
Countleaf(root->Rchild);
if(root->Lchild==NULL&&root->Rchild==NULL)
LeafCount++;
}
}
void PrintFromTopToBottom(BiTree T)
{
if(T == NULL)
return;
queue<BiTree> queueTreeNode;
queueTreeNode.push(T);
while(!queueTreeNode.empty())
{
BiTree pNode = queueTreeNode.front();
cout << pNode->data << " ";
queueTreeNode.pop();
if(pNode->Lchild != NULL)
queueTreeNode.push(pNode->Lchild);
if(pNode->Rchild != NULL)
queueTreeNode.push(pNode->Rchild);
}
}
void display(BiTree root) //显示树形结构
{
if(root!=NULL)
{
cout<<root->data;
if(root->Lchild!=NULL)
{
cout<<'(';
display(root->Lchild);
}
if(root->Rchild!=NULL)
{
cout<<',';
display(root->Rchild);
cout<<')';
}
}
}
int main()
{
BiTree bt;
int n;
cout<<"请按先序次序输入二叉树中结点的值,@表示空树："<<endl;
CreateBiTree(&bt);
// cout<<"二叉树的树形显示："<<endl;
// display(bt);
cout<<"先序递归遍历二叉树："<<endl;
PreOrder(bt);cout<<endl;
cout<<"中序递归遍历二叉树："<<endl;
InOrder(bt);cout<<endl;
cout<<"后序递归遍历二叉树："<<endl;
PostOrder(bt);cout<<endl;
cout<<"中序非递归遍历二叉树："<<endl;
inOrder2(bt);cout<<endl;
cout<<"二叉树的高度：";
n=depth(bt);
cout<<n<<endl;
cout<<"二叉树叶节点个数：";
LeafCount=0;
Countleaf(bt);
cout<<LeafCount<<endl;
cout<<"队列实现二叉树的层次遍历："<<endl;
PrintFromTopToBottom(bt);
return 0;
}
测试截图：