前、中、后序.txt

数据结构书上源代码（严蔚敏C语言版）以及二叉树的各种基本算法

#include <string> 
#include<iostream> 
#include<stack> 
using namespace std; 
class BinaryNode 
{ 
BinaryNode* leftChild; 
BinaryNode* rightChild; 
char name; 
public: 
BinaryNode(char a) 
{ 
name=a; 
leftChild=NULL; 
rightChild=NULL; 
} 
BinaryNode() 
{ 
name='0'; 
leftChild=NULL; 
rightChild=NULL; 
} 
BinaryNode(BinaryNode *l,char item,BinaryNode *r) 
{ 
name=item; 
leftChild=l; 
rightChild=r; 
} 
BinaryNode(char item,BinaryNode *r){ 
name=item; 
rightChild=r; 
leftChild=NULL; 
} 
BinaryNode(BinaryNode *l,char item){ 
leftChild =l; 
name=item; 
rightChild=NULL; 
} 
BinaryNode* getLeft() 
{ 
return leftChild; 
} 
BinaryNode* getRight() 
{ 
return rightChild; 
} 
void setName(char a){ 
name=a; 
} 
char getName(){ 
return name; 
} 
void setLeft(BinaryNode * l){ 
leftChild=l; 
} 
void setRight(BinaryNode * r){ 
rightChild=r; 
} 


}; 
class Tree{ 

public: 
BinaryNode* root; 
Tree(){ 
root=NULL; 
} 
void postOrder(BinaryNode* r){ 
if(r==NULL)return ; 
cout<<r->getName()<<" "; 
postOrder(r->getLeft()); 
postOrder(r->getRight()); 
} 
void inOrder(BinaryNode* r){ 
if(r==NULL)return ; 
inOrder(r->getLeft()); 
cout<<r->getName()<<" "; 
inOrder(r->getRight()); 
} 
void afterOrder(BinaryNode* r){ 
if(r==NULL)return ; 
afterOrder(r->getLeft()); 
afterOrder(r->getRight()); 
cout<<r->getName()<<" "; 
} 
void setRoot(BinaryNode *r){ 
root =r; 

} 
void preOrderUNre(BinaryNode *t) 
{ 
stack<BinaryNode*> pre; 
if(t==NULL)return; 
BinaryNode *curr; 
pre.push(t); 
while(!pre.empty()) 
{ 
curr=pre.top(); 
pre.pop(); 
if(curr!=NULL) 
cout<<curr->getName()<<" "; 
if(curr->getRight()!=NULL) 
pre.push(curr->getRight()); 
if(curr->getLeft()!=NULL) 
pre.push(curr->getLeft()); 
} 

} 


}; 
BinaryNode * CreateBT (string pres, string ins )//利用前序中序建立树 
{ 
int inpos; 
BinaryNode * temp; 
string prestemp, instemp ; 
if (pres.length()==0) return NULL; 
else { temp=new BinaryNode(); 
temp->setName(pres.at(0)); 
inpos=0; 
while (ins.at(inpos)!=temp->getName()) inpos++; 
prestemp=pres.substr(1,inpos); 
instemp=ins.substr(0,inpos); 
temp->setLeft( CreateBT(prestemp, instemp)); 
prestemp=pres.substr(inpos+1, pres.length( )); 
instemp=ins.substr(inpos+1, ins.length( )); 
temp->setRight (CreateBT(prestemp, instemp)); 
return temp; 
} 
} 
#include <deque> 
string levelOrder(BinaryNode* t) 
{ 
string result=""; 
deque<BinaryNode *> q1; 
if(t==NULL)return NULL; 
BinaryNode* p; 
q1.push_back(t); 
while(!q1.empty()) 
{ 
p=q1.front(); 
q1.pop_front(); 
if(p!=NULL) 
result=result + p->getName()+" "; 
cout<<result<<endl; 
if(p->getLeft()!=NULL) 
q1.push_back(p->getLeft()); 
if(p->getRight()!=NULL) 
q1.push_back(p->getRight()); 
} 
return result; 
} 


void main(){ 
string pres,ins; 
cout<<"输入前序"<<endl; 
cin>>pres; 
cout<<"输入中序"<<endl; 
cin>>ins; 
Tree myTree; 
myTree.setRoot(CreateBT(pres,ins)); 
cout<<"不使用递归的前序结果是"; 
myTree.preOrderUNre(myTree.root); 
cout<<endl; 
cout<<"使用递归的结果是："; 
myTree.postOrder(myTree.root); 
cout<<endl; 
string r=levelOrder(myTree.root); 
cout<<"层次遍历"<<r<<endl; 



} 
前序提供两种思路解决，层次遍历给出方法， 
创建树是利用前序和 中序，也可以自己在main函数里从树叶到根一个节点一个节点创建树。 
给出节点类，树类。 
也可以实现中序后续的遍历 
回答者： winelover72 - 经理 五级   12-4 11:02







#include "iostream.h" 
#include "stdlib.h" 
#include "stdio.h" 

typedef char ElemType;//定义二叉树结点值的类型为字符型 
const int MaxLength=10;//结点个数不超过10个 

typedef struct BTNode{ 
ElemType data; 
struct BTNode *lchild,*rchild; 
}BTNode,* BiTree; 


void CreateBiTree(BiTree &T){//按先序次序输入，构造二叉链表表示的二叉树T，空格表示空树 
// if(T) return; 
char ch; 
ch=getchar(); //不能用cin来输入，在cin中不能识别空格。 
if(ch==' ') T=NULL; 
else{ 
if(!(T=(BTNode *)malloc(sizeof(BTNode)))) cout<<"malloc fail!"; 
T->data=ch; 
CreateBiTree(T->lchild); 
CreateBiTree(T->rchild); 
} 
} 

void PreOrderTraverse(BiTree T){//先序遍历 
if(T){ 
cout<<T->data<<' '; 
PreOrderTraverse(T->lchild); 
PreOrderTraverse(T->rchild); 
} 
} 
void InOrderTraverse(BiTree T){//中序遍历 
if(T){ 
InOrderTraverse(T->lchild); 
cout<<T->data<<' '; 
InOrderTraverse(T->rchild); 
} 
} 
void PostOrderTraverse(BiTree T){//后序遍历 
if(T){ 
PostOrderTraverse(T->lchild); 
PostOrderTraverse(T->rchild); 
cout<<T->data<<' '; 
} 
} 
void LevelOrderTraverse(BiTree T){//层序遍历 

BiTree Q[MaxLength]; 
int front=0,rear=0; 
BiTree p; 
if(T){ //根结点入队 
Q[rear]=T; 
rear=(rear+1)%MaxLength; 
} 
while(front!=rear){ 
p=Q[front]; //队头元素出队 
front=(front+1)%MaxLength; 
cout<<p->data<<' '; 
if(p->lchild){ //左孩子不为空，入队 
Q[rear]=p->lchild; 
rear=(rear+1)%MaxLength; 
} 
if(p->rchild){ //右孩子不为空，入队 
Q[rear]=p->rchild; 
rear=(rear+1)%MaxLength; 
} 
} 

} 
//非递归的先序遍历算法 
void NRPreOrder(BiTree bt) 
{ BiTree stack[MaxLength],p; 
int top; 
if (bt!=NULL){ 
top=0;p=bt; 
while(p!=NULL||top>0) 
{ while(p!=NULL) 
{ 
cout<<p->data; 
stack[top]=p; 
top++; 
p=p->lchild; 
} 
if (top>0) 
{ top--; p=stack[top]; p=p->rchild; } 
} 
} 
} 
//非递归的中序遍历算法 
void NRInOrder(BiTree bt) 
{ BiTree stack[MaxLength],p; 
int top; 
if (bt!=NULL){ 
top=0;p=bt; 
while(p!=NULL||top>0) 
{ while(p!=NULL) 
{ 

stack[top]=p; 
top++; 
p=p->lchild; 
} 
if (top>0) 
{ top--; p=stack[top];cout<<p->data; p=p->rchild; } 
} 
} 
} 
//非递归的后序遍历算法 
/*bt是要遍历树的根指针，后序遍历要求在遍历完左右子树后，再访问根。 
需要判断根结点的左右子树是否均遍历过。 
可采用标记法，结点入栈时，配一个标志tag一同入栈 
(1：遍历左子树前的现场保护，2：遍历右子树前的现场保护)。 
首先将bt和tag(为1)入栈，遍历左子树； 
返回后，修改栈顶tag为2，遍历右子树；最后访问根结点。*/ 

typedef struct 
{ 
BiTree ptr; 
int tag; 
}stacknode; 

void NRPostOrder(BiTree bt) 
{ 
stacknode s[MaxLength],x; 
BiTree p=bt; 
int top; 
if(bt!=NULL){ 
top=0;p=bt; 
do 
{ 
while (p!=NULL) //遍历左子树 
{ 
s[top].ptr = p; 
s[top].tag = 1; //标记为左子树 
top++; 
p=p->lchild; 
} 

while (top>0 && s[top-1].tag==2) 
{ 
x = s[--top]; 
p = x.ptr; 
cout<<p->data; //tag为R，表示右子树访问完毕，故访问根结点 
} 

if (top>0) 
{ 
s[top-1].tag =2; //遍历右子树 
p=s[top-1].ptr->rchild; 
} 
}while (top>0);} 
}//PostOrderUnrec 

int BTDepth(BiTree T){//求二叉树的深度 
if(!T) return 0; 
else{ 
int h1=BTDepth(T->lchild); 
int h2=BTDepth(T->rchild); 
if(h1>h2) return h1+1; 
else return h2+1; 
} 
} 

int Leaf(BiTree T){//求二叉树的叶子数 
if(!T) return 0; 
else if(!T->lchild&&!T->rchild) return 1; 
else return(Leaf(T->lchild)+Leaf(T->rchild)); 
} 

int NodeCount(BiTree T){//求二叉树的结点总数 
if(!T) return 0; 
else return NodeCount(T->lchild)+NodeCount(T->rchild)+1; 
} 

void main(){ 
BiTree T; 
T=NULL; 
int select; 
//cout<<"请按先序次序输入各结点的值，以空格表示空树(输入时可连续输入):"<<endl; 
// CreateBiTree(T); 
while(1){ 
cout<<"\n\n请选择要执行的操作:\n"; 
cout<<"1.创建二叉树\n"; 
cout<<"2.二叉树的递归遍历算法（前、中、后）\n"; 
cout<<"3.二叉树的层次遍历算法\n"; 
cout<<"4.求二叉树的深度\n"; 
cout<<"5.求二叉树的叶子结点\n"; 
cout<<"6.求二叉树的结点总数\n"; 
cout<<"7.二叉树的非递归遍历算法（前、中、后）\n"; //此项可选做 
cout<<"0.退出\n"; 
cin>>select; 
switch(select){ 
case 0:return; 
case 1: 
cout<<"请按先序次序输入各结点的值，以空格表示空树(输入时可连续输入):"<<endl; 
CreateBiTree(T); 
break; 
case 2: 
if(!T) cout<<"未建立树，请先建树！"; 
else{ 
cout<<"\n先序遍历:\n"; 
PreOrderTraverse(T); 
cout<<"\n中序遍历:\n"; 
InOrderTraverse(T); 
cout<<"\n后序遍历:\n"; 
PostOrderTraverse(T); 
} 
break; 
case 3: 
cout<<"\n层序遍历:\n"; 
LevelOrderTraverse(T); 
break; 
case 4: 
cout<<"二叉树的深度为:\n"; 
cout<<BTDepth(T); 
break; 
case 5: 
cout<<"\n叶子节点数:\n"; 
cout<<Leaf(T); 
break; 
case 6: 
cout<<"总节点数:\n"; 
cout<<NodeCount(T); 
break; 
case 7: 
if(!T) cout<<"未建立树，请先建树！"; 
else{ 
cout<<"\n先序遍历:\n"; 
NRPreOrder(T); 
cout<<"\n中序遍历:\n"; 
NRInOrder(T); 
cout<<"\n后序遍历:\n"; 
NRPostOrder(T); 
} 
break; 
default: 
cout<<"请确认选择项:\n"; 
}//end switch 
}//end while 

} 
回答者： 6908270270 - 助理 三级   12-4 12:06
有什么可怕的 
回答者： yinggong86 - 初入江湖 三级   12-5 01:45
已通过tc编译： 
#include<stdio.h> 
#include<stdlib.h> 
typedef struct bitnode 
{ 
char data; 
struct bitnode *lchild,*rchild; 
}bitnode,*bitree;//二叉树节点类型和节点指针类型 

bitree create_tree() //先序创建二叉树 
{ 
char a;bitree root; 
scanf("%c",&a); 
fflush(stdin); 
if(a=='#')return NULL;//'#'代表空节点 
else 
{ 
root=(bitnode *)malloc(sizeof(bitnode)); 
root->data=a; 
root->lchild=create_tree(); 
root->rchild=create_tree(); 
} 
return root; 
} 
void layerorder(bitree T)//层次遍历 
{ 
int front=0;int rear=0; 
bitree Q[100];//Q足够大 
Q[rear++]=T; 
while(rear!=front) 
{ 
bitree p; 
p=Q[front++]; 
putchar(p->data); 
if(p->lchild)Q[rear++]=p->lchild; 
if(p->rchild)Q[rear++]=p->rchild; 
} 
} 
void preorder(bitree root)//前序遍历 
{ 
int top=0;bitree s[100];//s足够大 
while(root||top) 
{ 
while(root) 
{ 
putchar(root->data); 
s[++top]=root;root=root->lchild; 
} 
if(top)root=s[top--]->rchild; 
} 
} 
void main() 
{ 
bitree root=NULL; 
root=create_tree();//输入先序序列，节点为空输入＃ 
printf("层次遍历：\n"); 
layerorder(root); 
printf("\n"); 
printf("前序遍历：\n"); 
preorder(root); 
printf("\n"); 
} 
例如输入a（回车）b（回车）＃（回车）c（回车）＃（回车）＃（回车）d（回车）＃（回车）＃（回车）就能得到层次遍历abdc 前序遍历abcd