假设二叉树采用连接方式存储,编写一个对二叉树进行前序遍历的递归和非递归程序

#include "iostream.h"

#include "string.h"

#include "malloc.h"

#include "stdio.h"

typedef struct btree

{

int data;//树结点的值域

int ltag,rtag;//树结点的左右线索

struct btree *left,*right;//树结点的左右指针，ltag，rtag=1时指向前驱和后继，否则指向左右孩子

}node;

node *SearchNode(node *q,node *r)

{//在根结点地址为q的中序线索二叉树中查找结点r将要插入的结点

node *p;

p=q;

while(1)

{

while(r->data<p->data&&p->ltag!=1){p=p->left;}//一直向左寻找

while(r->data>p->data&&p->rtag!=1){p=p->right;}//一直向右寻找

if(r->data<p->data&&p->ltag==1||r->data>p->data&&p->rtag==1||r->data==p->data)break; //当r->data<p->data并且p没有左孩子或r->data>p->data并且p没有由孩子 //或r->data==p->data时，结点p找到，跳出循环

}

return(p);//返回p结点

}

node *InsertNode(node *rot,node *s)

{//在根结点地址为rot的中序线索二叉树中插入结点s

node *p;

if(rot==NULL)

{//如果根结点为空，s结点作为根结点插入。

rot=s;

rot->data=s->data;

rot->ltag=1;

rot->left=NULL;

rot->rtag=1;

rot->right=NULL;

return(rot);

}

p=SearchNode(rot,s);//调用SearchNode函数查找s将要插入的结点p的位置

if(s->data==p->data)

{//如果结点在树中已经存在，释放该结点并返回

free(s);

return(rot);

}

if(s->data<p->data)

{//如果s->data<p->data，则做为p的左孩子插入，此时s的前驱是插入前p的前驱，s的后继是p

s->ltag=1;

s->left=p->left;

s->rtag=1;

s->right=p;

p->ltag=0;

p->left=s;

}

if(s->data>p->data)

{//如果s->data>p->data，则做为p的右孩子插入，此时s的后继是插入前p的后继，s的前驱是p

s->rtag=1;

s->right=p->right;

s->ltag=1;

s->left=p;

p->rtag=0;

p->right=s;

}

return(rot);

}

node *CreatTree(node *rt)

{//以根结点为空开始构造中序线索二叉排序树，并返回根结点的地址

int m;//用于输入根结点的值域

node *q;

while(1)

{

printf("Please input number:\nm=");

//scanf("%d",&m);

cin>>m;//输入结点的值

if(m==-1) return(rt);

node *s;//建一个有待插入的新结点

s=(node *)malloc(sizeof(node));//给s开辟一个结点空间

s->data=m;

q=InsertNode(rt,s);//调用InsertNode函数一个个结点插入已生成的中序线索二叉树中，形成新的树

rt=q;

}

return(rt);

}

node *Search(node *root,int x)

{//在根结点地址为root的中序线索二叉树中查找结点值为x的结点p并返回p，若结点不存在则返回NULL。

node *p;//返回值为x的结点的位置

p=root;

while(1)

{

while(x<p->data&&p->ltag!=1){p=p->left;}

while(x>p->data&&p->rtag!=1){p=p->right;}

if(x<p->data&&p->ltag==1||x>p->data&&p->rtag==1||x==p->data)break;

}

if(x!=p->data) p=NULL;

return(p);

}

node *P_Next(node *root,int x)

{//查找根结点地址为root的中序线索二叉树中结点值为x的结点p按后序遍历的后继结点q node *p,*q;//p是结点值为x的结点，q用来返回p按后序遍历的后继结点

p=Search(root,x);//调用Search函数查找结点p的位置

if(p==NULL)//值为x结点不存在，出错

{

return NULL;

}

if(p->ltag==0) return(p->left);//如果此结点有左孩子，返回左孩子结点

else

{

if(p->rtag==0) return(p->right);//如果此结点无左孩子有右孩子，返回右孩子结点 else//如果此结点为叶子结点

{

q=p->right;//寻找此结点的后继结点

if(q==NULL)//后继为空，此结点是按前序遍历的最后一个结点，返回空 {

printf("this node is last node\n");

return NULL;

}

else

{

while(q->rtag==1&&q->right!=NULL) {q=q->right;}//如果结点的后继没有右孩子，一直向后继方向寻找结点

if(q->right==NULL)

{

return NULL;

}

else return(q->right);//返回结点的右孩子结点

}

}

}

}

void display(node *t)

{//非递归中序遍历中序线索二叉排序树

printf("中序序列为：");

while(t->ltag!=1){t=t->left;}//寻找最左结点，即中序遍历的第一个结点

while(t!=NULL)

{

printf("%d ",t->data);//打印结点值

while(t->rtag==1)//结点右指针指向后继结点

{

t=t->right;

if(t==NULL)return;//t空，遍历结束

else printf("%d ",t->data);//打印结点值

}

if(t->rtag==0)//如果结点有右孩子

{

t=t->right;//从右孩子结点开始

while(t->ltag!=1){t=t->left;}//继续向左寻找此子树的最左结点

}

}

}

int main()

{

int w;

printf("输入一串正整数建立一棵中序线索二叉排序树最后以-1作为结束标志\n"); node *root;

root=NULL;

node *p;

node *q;

p=CreatTree(root);

display(p);

while(1)

{

cout<<"\n查找按前序遍历x的后继结点\nx=";

cin>>w;

q=P_Next(p,w);

if(q==NULL) cout<<"此结点不在树中或是按前序遍历的最后一个结点\n"; else

{

cout<<"\n此结点的后继结点为：";

cout<<q->data;

}

}

}

本文来源：https://www.bwwdw.com/article/gi31.html