C說話 二叉樹的鏈式存儲實例。本站提示廣大學習愛好者：（C說話 二叉樹的鏈式存儲實例）文章只能為提供參考，不一定能成為您想要的結果。以下是C說話 二叉樹的鏈式存儲實例正文
二叉樹的鏈式存儲
完成二叉樹的根本操作：樹立、遍歷、盤算深度、結點數、葉子數等。
輸出C，先序創立二叉樹，#表現空節點；
輸出H：盤算二叉樹的高度；
輸出L：盤算二叉樹的葉子個數；
輸出N：盤算二叉樹節點總個數；
輸出1：先序遍歷二叉樹；
輸出2：中序遍歷二叉樹；
輸出3：後續遍歷二叉樹；
輸出F：查找值=x的節點的個數；
輸出P：以縮格文本情勢輸入一切節點。
很簡略就不須要多說明了，代碼貼上
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
using namespace std;
/*二叉樹的鏈式存儲表現*/
typedef char DataType; /*應由用戶界說DataType的現實類型*/
typedef struct node
{
DataType data;
node *lchild, *rchild; /*閣下孩子指針*/
} BinTNode; /*結點類型*/
typedef BinTNode *BinTree;
int sum=0;
void DisplayBinTree(BinTree T); /*用格文本情勢表現二叉樹*/
void CreateBinTree(BinTree *T); /*結構二叉鏈表*/
void Preorder(BinTree T); /*前序遍歷二叉樹*/
void Inorder(BinTree T); /*中序遍歷二叉樹*/
void Postorder(BinTree T); /*後序遍歷二叉樹*/
int nodes(BinTree T); /*盤算總結點數*/
int leafs(BinTree T); /*盤算總葉子數*/
int hight(BinTree T); /*盤算二叉樹的高度*/
int find(BinTree T,char x); //查找值=x的節點的個數；
int main()
{
BinTree T;
char flg;
while(cin>>flg)
switch(flg)
{
case'C':
getchar();
CreateBinTree(&T);
cout<<"Created success!"<<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("Preorder is:");
Preorder(T);
cout<<"."<<endl;
break;
case'2':
printf("Inorder is:");
Inorder(T);
cout<<"."<<endl;
break;
case'3':
printf("Postorder is:");
Postorder(T);
cout<<"."<<endl;
break;
case'F':
char x;
int ko;
getchar();
cin>>x;
ko=find(T,x);
cout<<"The count of "<<x<<" is "<<ko<<"."<<endl;
break;
case'P':
cout<<"The tree is:"<<endl;
DisplayBinTree(T);
break;
default:
cout<<"輸出有誤，請從新輸出"<<endl;
}
}
/*結構二叉鏈表*/
void CreateBinTree(BinTree *T)
{
char ch;
if ((ch=getchar())=='#')
*T=NULL;
else
{
/*讀入非空格*/
*T=(BinTNode *)malloc(sizeof(BinTNode));/*生成結點*/
(*T)->data=ch;
CreateBinTree(&(*T)->lchild ); /*結構左子樹*/
CreateBinTree(&(*T)->rchild ); /*結構右子樹*/
}
}
/*用縮格文本情勢表現二叉樹*/
void DisplayBinTree(BinTree T)
{
BinTree stack[100],p;
int level[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;
}
}
}
}
/*盤算總結點數*/
int nodes(BinTree T)
{
if(T)
{
if( (T->lchild==NULL)&&(T->rchild==NULL))
return 1;
else
return nodes(T->lchild)+nodes(T->rchild)+1;
}
return 0;
}
/*盤算總葉子數*/
int leafs(BinTree T)
{
if(T)
{
if ((T->lchild==NULL)&&(T->rchild==NULL))
return 1;
else
return leafs(T->lchild)+leafs(T->rchild);
}
return 0;
}
/*盤算樹的高度*/
int hight(BinTree T)
{
if(T)
{
if ((T->lchild==NULL)&&(T->rchild==NULL))
return 1;
else if((T->lchild==NULL)&&(T->rchild))
return 1+hight(T->rchild);
else if((T->lchild)&&(T->rchild==NULL))
return 1+hight(T->lchild);
else
return hight(T->lchild)+hight(T->rchild);
}
return 0;
}
/*前序遍歷二叉樹*/
void Preorder(BinTree T)
{
if(T)
{
printf("%c ",T->data); /*拜訪結點*/
Preorder(T->lchild);
Preorder(T->rchild);
}
}
/*中序遍歷二叉樹*/
void Inorder(BinTree T)
{
if(T)
{
Inorder(T->lchild);
printf("%C ",T->data);
Inorder(T->rchild);
}
}
/*後序遍歷二叉樹*/
void Postorder(BinTree T)
{
if(T)
{
Postorder(T->lchild);
Postorder(T->rchild);
printf("%C ",T->data);
}
}
int find(BinTree T,char x)
{
if(T)
{
if((T->data)==x)
sum++;
find(T->lchild,x);
find(T->rchild,x);
}
return sum;
}
以上就是二叉樹鏈式存儲的一個小實例，需進修要的同窗請參考，感謝支撐
