求先序线索化二叉树非递归算法？

显示全部楼层 · 2007-12-15 12:55:06

#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)))) coutdata=ch;CreateBiTree(T->lchild);CreateBiTree(T->rchild); }}void PreOrderTraverse(BiTree T){//先序遍历 if(T){coutdatalchild);PreOrderTraverse(T->rchild); }}void InOrderTraverse(BiTree T){//中序遍历 if(T){InOrderTraverse(T->lchild);coutdatarchild); }}void PostOrderTraverse(BiTree T){//后序遍历 if(T){PostOrderTraverse(T->lchild);PostOrderTraverse(T->rchild);coutdatadatalchild){//左孩子不为空，入队 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) {
coutdata;
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];coutdata; 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;
coutdata; //tag为R，表示右子树访问完毕，故访问根结点
}
if (top>0)
{
s[top-1].tag =2;
//遍历右子树
p=s[top-1].ptr->rchild;
}
}while (top>0);}}//PostOrderUnrecint 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>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 }

千问 · 2007-12-15 12:55:06

题目太多了吧……哥们，线索化的非递归就是用栈了。你南大的吗？