首页 > 代码库 > 数据结构之二叉树(一)

数据结构之二叉树(一)

 

 

设计和编写程序,按照输入的遍历要求(即先序、中序和后序)完成对二叉树的遍历,并输出相应遍历条件下的树结点序列。

 

 

 

//递归实现
#include<iostream> #include<string> using namespace std; typedef struct BiTNode{ char data; struct BiTNode *lchild,*rchild; }BiTNode,*BiTree; void InitBiTree(BiTree &T)//构造空二叉树 { T=NULL; } void CreateBiTree(BiTree &T)//生成二叉树 { char ch; cin>>ch; if(ch==0)//0代表空 T=NULL; else { T=(BiTree)malloc(sizeof(BiTNode));//生成根结点 if(!T) { cout<<"生成结点错误!"<<endl; return; } T->data=http://www.mamicode.com/ch; CreateBiTree(T->lchild); CreateBiTree(T->rchild); } } void PreOrder(BiTree T)//先序递归遍历 { if(T!=NULL) { cout<<T->data<<" "; PreOrder(T->lchild); PreOrder(T->rchild); } } void InOrder(BiTree T)//中序递归遍历 { if(T!=NULL) { InOrder(T->lchild); cout<<T->data<<" "; InOrder(T->rchild); } } void PostOrder(BiTree T)//后序递归遍历 { if(T!=NULL) { PostOrder(T->lchild); PostOrder(T->rchild); cout<<T->data<<" "; } } int main() { BiTree T; InitBiTree(T); cout<<"请输入二叉树结点"<<endl; CreateBiTree(T); string str=""; cout<<"请输入遍历要求(先序,中序,后序)"; cin>>str; if(str=="先序") { cout<<endl<<"先序递归遍历树"<<endl; PreOrder(T); } else if(str=="中序") { cout<<endl<<"中序递归遍历树"<<endl; InOrder(T); } else if(str=="后序") { cout<<endl<<"后序递归遍历树"<<endl; PostOrder(T); } cout<<endl; system("pause"); return 0; }

 

数据结构之二叉树(一)