假设二叉树采用连接方式存储,编写一个对二叉树进行前序遍历的递归和非递归程序-问答-阿里云开发者社区-阿里云

开发者社区> 问答> 正文
阿里云
为了无法计算的价值
打开APP
阿里云APP内打开

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

2018-07-22 13:27:04 1731 3
假设二叉树采用连接方式存储,编写一个对二叉树进行前序遍历的递归和非递归程序
取消 提交回答
全部回答(3)
  • kissjz
    2019-07-17 22:54:28

    可以参考我的这篇博客,使用Java写的:算法之树(一,B-树原理详解)(Java版)-持续更新补充

    0 0
  • 小哇
    2019-07-17 22:54:28
    <算法与数据结构>书上有,现成的例子啊
    0 0
  • 一键天涯
    2019-07-17 22:54:28
    下面是我以前写的程序对你是否有帮助
    #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;}//继续向左寻找此子树的最左结点
    }

    }

    }

    void 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;
    }
    }

    }
    0 0
添加回答
相关问答

1

回答

是什么在flask中提供了很多与程序相关的属性和方法?

2021-11-06 16:56:37 112浏览量 回答数 1

1

回答

存储的Procs-将消息传递回用户应用程序的最佳方法

2019-12-28 23:21:18 772浏览量 回答数 1

1

回答

在哪里找到远程连接的按钮啊?

2019-04-04 09:12:27 1123浏览量 回答数 1

2

回答

我编写了一个TCP的服务端程序,在绑定公网ip时提示地址不可用。

2018-10-30 15:04:35 752浏览量 回答数 2

2

回答

编写程序:用冒泡排序法对15个浮点数进行排序。这15个浮点数用数组存放.

2018-07-18 09:28:50 3794浏览量 回答数 2

1

回答

域名shenghuate,她不想与原服务商合作,请告诉我提供她公司执照,不通过原服务商转出的流程

2018-06-18 10:01:07 470浏览量 回答数 1

6

回答

一个虚拟空间放多个程序

2017-09-14 11:19:49 2662浏览量 回答数 6

1

回答

c语言,一个连接两字符串的函数。

2016-06-06 14:06:40 1963浏览量 回答数 1

1

回答

C++中成员函数、静态成员函数、虚函数都是怎么存储的?他们哪一个先被调用?

2016-03-06 15:22:56 2137浏览量 回答数 1

3

回答

我爱上一个程序员

2016-02-25 17:27:52 7116浏览量 回答数 3
+关注
文章
问答
问答排行榜
最热
最新
相关电子书
更多
低代码开发师(初级)实战教程
立即下载
阿里巴巴DevOps 最佳实践手册
立即下载
冬季实战营第三期:MySQL数据库进阶实战
立即下载