开发者社区> 问答> 正文

编写递归算法,二叉树中以元素值为X的结点为根的子树的深度。要用C++6.0编程

考考大家,嘿嘿

展开
收起
知与谁同 2018-07-18 20:48:31 2792 0
1 条回答
写回答
取消 提交回答
  • 12535
    #include "stdio.h"
    #include "stdlib.h"
    #include "string.h"
    #define null 0

    struct node
    {
    char data;
    struct node *lchild;
    struct node *rchild;
    };

    //先序,中序 建树
    struct node *create(char *pre,char *ord,int n)
    {
    struct node * head;
    int ordsit;

    head=null;
    if(n<=0)
    {
    return null;
    }
    else
    {
    head=(struct node *)malloc(sizeof(struct node));
    head->data=*pre;
    head->lchild=head->rchild=null;
    ordsit=0;
    while(ord[ordsit]!=*pre)
    {
    ordsit++;
    }
    head->lchild=create(pre+1,ord,ordsit);
    head->rchild=create (pre+ordsit+1,ord+ordsit+1,n-ordsit-1);
    return head;
    }
    }

    //中序递归遍历
    void inorder(struct node *head)
    {
    if(!head)
    return;
    else
    {
    inorder(head->lchild );
    printf("%c",head->data );
    inorder(head->rchild );
    }
    }

    //中序非递归遍历

    void inorder1(struct node *head)
    {
    struct node *p;
    struct node *stack[20];
    int top=0;

    p=head;
    while(p||top!=0)
    {
    while (p)
    {
    stack[top++]=p;
    p=p->lchild ;
    }
    p=stack[--top];
    printf("%c ",p->data );
    p=p->rchild ;
    }
    }

    //主函数
    int main()
    {
    struct node * head;
    char pre[30],ord[30];
    int n;

    gets(pre);
    gets(ord);
    n=strlen(pre);
    head=create(pre,ord,n);
    inorder(head);
    printf("\n");
    inorder1(head);
    printf("\n");
    }
    2019-07-17 22:55:21
    赞同 展开评论 打赏
问答分类:
问答地址:
问答排行榜
最热
最新

相关电子书

更多
使用C++11开发PHP7扩展 立即下载
GPON Class C++ SFP O;T Transce 立即下载
GPON Class C++ SFP OLT Transce 立即下载