二叉树的基本 操作

页眉内容

//二叉树的基本操作 #include

typedef struct node //定义结点 { char data;

struct node *lchild, *rchild; } BinTNode;

typedef BinTNode *BinTree; //定义二叉树

void CreateBinTree(BinTree &T); //先序创建二叉树 void PreOrder(BinTree T); //先序遍历二叉树 void InOrder(BinTree T); //中序遍历二叉树 void PostOrder(BinTree T); //后序遍历二叉树 int onechild(BinTree T); //求度为1的结点的个数 int leafs(BinTree T); //求叶子结点的个数 int twochild(BinTree T); //度为2的结点的个数 void translevel(BinTree b); //层序遍历二叉树 void main() { int n; BinTree T; char ch1,ch2;

cout<<\欢迎进入二叉树测试程序的基本操作\ cout<<\请选择------------\ ch1='y';

while(ch1=='y'||ch1=='Y') {

cout<<\建立二叉树 \\n\

cout<<\先序遍历\\n\ cout<<\中序遍历\\n\ cout<<\后序遍历\\n\

页眉内容

cout<<\单孩子结点数\\n\

cout<<\双孩子结点数\\n\ cout<<\叶子结点数\\n\

cout<<\层序遍历\\n\

cout<<\退出\\n\ cin>>ch2; switch(ch2) {

case '1':

cout<<\请输入按先序建立二叉树的结点序列：\\n\

CreateBinTree(T); cout<

case '2':

cout<<\二叉树的先序遍历序列：\\n\

PreOrder(T); cout<

case '3':

cout<<\二叉树的中序遍历序列：\\n\

InOrder(T); cout<

case '4':

cout<<\二叉树的后序遍历序列：\\n\

PostOrder(T); cout<

页眉内容

cout<<\二叉树的单孩子结点数：\\n\

n=onechild(T); cout<

cout<<\二叉树的双孩子结点数：\\n\

n=twochild(T); cout<

cout<<\二叉树的叶子结点数：\\n\

n=leafs(T); cout<

case '8':

cout<<\二叉树的层序遍历序列：\\n\

translevel(T); cout<

} } }

void CreateBinTree(BinTree &T)

页眉内容

{

char ch; cin>>ch;

if(ch=='0') T=NULL; else { }

void InOrder(BinTree T) { }

void PostOrder(BinTree T) { }

if(T) { }

PostOrder(T->lchild ); PostOrder(T->rchild ); cout<data; if(T) { }

InOrder(T->lchild ); cout<data; InOrder(T->rchild );

T=(BinTNode *)new BinTNode; T->data=ch;

CreateBinTree(T->lchild ); CreateBinTree(T->rchild ); }