C语言 二叉树的链式存储实例
二叉树的链式存储
实现二叉树的基本操作：建立、遍历、计算深度、结点数、叶子数等。
输入C，先序创建二叉树，#表示空节点；
输入H：计算二叉树的高度；
输入L：计算二叉树的叶子个数；
输入N：计算二叉树节点总个数；
输入1：先序遍历二叉树；
输入2：中序遍历二叉树；
输入3：后续遍历二叉树；
输入F：查找值=x的节点的个数；
输入P：以缩格文本形式输出所有节点。
很简单就不需要多解释了，代码贴上
#include<stdio.h>
#include<stdlib.h>
#include<iostream>
usingnamespacestd;
/*二叉树的链式存储表示*/
typedefcharDataType;/*应由用户定义DataType的实际类型*/
typedefstructnode
{
DataTypedata;
node*lchild,*rchild;/*左右孩子指针*/
}BinTNode;/*结点类型*/
typedefBinTNode*BinTree;
intsum=0;
voidDisplayBinTree(BinTreeT);/*用格文本形式表示二叉树*/
voidCreateBinTree(BinTree*T);/*构造二叉链表*/
voidPreorder(BinTreeT);/*前序遍历二叉树*/
voidInorder(BinTreeT);/*中序遍历二叉树*/
voidPostorder(BinTreeT);/*后序遍历二叉树*/
intnodes(BinTreeT);/*计算总结点数*/
intleafs(BinTreeT);/*计算总叶子数*/
inthight(BinTreeT);/*计算二叉树的高度*/
intfind(BinTreeT,charx);//查找值=x的节点的个数；
intmain()
{
BinTreeT;
charflg;
while(cin>>flg)
switch(flg)
{
case'C':
getchar();
CreateBinTree(&T);
cout<<"Createdsuccess!"<<endl;
break;
case'H':
cout<<"Height="<<hight(T)<<"."<<endl;
break;
case'L':
cout<<"Leaf="<<leafs(T)<<"."<<endl;
break;
case'N':
cout<<"Nodes="<<nodes(T)<<"."<<endl;
break;
case'1':
printf("Preorderis:");
Preorder(T);
cout<<"."<<endl;
break;
case'2':
printf("Inorderis:");
Inorder(T);
cout<<"."<<endl;
break;
case'3':
printf("Postorderis:");
Postorder(T);
cout<<"."<<endl;
break;
case'F':
charx;
intko;
getchar();
cin>>x;
ko=find(T,x);
cout<<"Thecountof"<<x<<"is"<<ko<<"."<<endl;
break;
case'P':
cout<<"Thetreeis:"<<endl;
DisplayBinTree(T);
break;
default:
cout<<"输入有误，请重新输入"<<endl;
}
}
/*构造二叉链表*/
voidCreateBinTree(BinTree*T)
{
charch;
if((ch=getchar())=='#')
*T=NULL;
else
{
/*读入非空格*/
*T=(BinTNode*)malloc(sizeof(BinTNode));/*生成结点*/
(*T)->data=ch;
CreateBinTree(&(*T)->lchild);/*构造左子树*/
CreateBinTree(&(*T)->rchild);/*构造右子树*/
}
}
/*用缩格文本形式表示二叉树*/
voidDisplayBinTree(BinTreeT)
{
BinTreestack[100],p;
intlevel[100],top,n,i;
if(T)
{
top=1;
stack[top]=T;
level[top]=0;
while(top>0)
{
p=stack[top];
n=level[top];
for(i=1;i<=n;i++)
cout<<"";
printf("%c\n",p->data);
top--;
if(p->rchild!=NULL)
{
top++;
stack[top]=p->rchild;
level[top]=n+2;
}
if(p->lchild!=NULL)
{
top++;
stack[top]=p->lchild;
level[top]=n+2;
}
}
}
}
/*计算总结点数*/
intnodes(BinTreeT)
{
if(T)
{
if((T->lchild==NULL)&&(T->rchild==NULL))
return1;
else
returnnodes(T->lchild)+nodes(T->rchild)+1;
}
return0;
}
/*计算总叶子数*/
intleafs(BinTreeT)
{
if(T)
{
if((T->lchild==NULL)&&(T->rchild==NULL))
return1;
else
returnleafs(T->lchild)+leafs(T->rchild);
}
return0;
}
/*计算树的高度*/
inthight(BinTreeT)
{
if(T)
{
if((T->lchild==NULL)&&(T->rchild==NULL))
return1;
elseif((T->lchild==NULL)&&(T->rchild))
return1+hight(T->rchild);
elseif((T->lchild)&&(T->rchild==NULL))
return1+hight(T->lchild);
else
returnhight(T->lchild)+hight(T->rchild);
}
return0;
}
/*前序遍历二叉树*/
voidPreorder(BinTreeT)
{
if(T)
{
printf("%c",T->data);/*访问结点*/
Preorder(T->lchild);
Preorder(T->rchild);
}
}
/*中序遍历二叉树*/
voidInorder(BinTreeT)
{
if(T)
{
Inorder(T->lchild);
printf("%C",T->data);
Inorder(T->rchild);
}
}
/*后序遍历二叉树*/
voidPostorder(BinTreeT)
{
if(T)
{
Postorder(T->lchild);
Postorder(T->rchild);
printf("%C",T->data);
}
}
intfind(BinTreeT,charx)
{
if(T)
{
if((T->data)==x)
sum++;
find(T->lchild,x);
find(T->rchild,x);
}
returnsum;
}
以上就是二叉树链式存储的一个小实例，需学习要的同学请参考，谢谢支持