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

#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;

搜索“diyifanwen.net”或“第一范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，第一范文网，提供最新高中教育假设二叉树采用连接方式存储,编写一个对二叉树进行前序遍历的递归和非递归程序全文阅读和word下载服务。