开发者社区> 问答> 正文

C/C++ 利用栈并且采用非递归先序算法建立二叉树,是建立~,请问有谁能回答,重奖~需要完整可在VC++6.0

知与谁同 2018-07-18 19:49:03 480
需要完整可在VC++6.0运行的源代码,最好能有一定的注释~谢谢
算法 C++
分享到
取消 提交回答
全部回答(2)
  • 马铭芳
    2019-07-17 22:55:16
    建立,还是遍历
    0 0
  • boxti
    2019-07-17 22:55:16
    #include <stdio.h>
    #include<malloc.h>
    #define MaxSize 100

    typedef char ElemType;
    typedef struct node
    {
    ElemType data;
    struct node *left,*right;
    } BTree;

    void creatree(BTree **BT,char *str)
    {
    BTree *stack[MaxSize],*p;
    int top=-1,k,j=0;
    char ch;
    *BT=NULL;
    ch=str[j];
    while (ch!='\0')
    {
    switch(ch)
    {
    case '(':
    top++;
    stack[top]=p;
    k=1; //k=1为左结点
    break;
    case ')':
    top--;
    break;
    case ',':
    k=2; //k=2为右结点
    break;
    default:
    p=(BTree *)malloc(sizeof(BTree));
    p->data=ch;
    p->left=p->right=NULL;
    if (*BT==NULL)
    *BT=p;
    else
    {
    switch(k)
    {
    case 1:stack[top]->left=p;
    break;
    case 2:stack[top]->right=p;
    break;
    }
    }
    }
    ch=str[++j];
    }
    }

    void preorder(BTree *BT)//前序遍历递归算法
    {
    if (BT!=NULL)
    {
    printf("%c",BT->data);
    preorder(BT->left);
    preorder(BT->right);
    }
    }
    void preorder1(BTree *BT)//前序遍历非递归算法
    {
    BTree*p,*stack[MaxSize];
    int top=-1;
    p=BT;
    while(top!=-1||p!=NULL)
    {
    while(p!=NULL)
    {
    printf("%c",p->data);
    stack[++top]=p;
    p=p->left;
    }
    if(top!=-1)
    {
    p=stack[top--];
    p=p->right;
    }
    }
    }

    void inorder(BTree *BT)//中序遍历递归算法
    {
    if (BT!=NULL)
    {
    inorder(BT->left);
    printf("%c",BT->data);
    inorder(BT->right);
    }
    }
    void inorder1(BTree *BT)//中序遍历非递归算法
    {
    BTree *p,*stack[MaxSize];
    int top=-1;
    p=BT;
    while(top!=-1||p!=NULL)
    {
    while(p!=NULL)
    {
    stack[++top]=p;
    p=p->left;
    }
    if(top!=-1)
    {
    p=stack[top--];
    printf("%c",p->data);
    p=p->right;
    }
    }
    }

    void postorder(BTree *BT)//后序遍历递归算法
    {
    if (BT!=NULL)
    {
    postorder(BT->left);
    postorder(BT->right);
    printf("%c",BT->data);
    }
    }
    void postorder1(BTree *BT)//后序遍历非递归算法
    {
    typedef enum{L,R} tagtype;
    typedef struct
    {
    BTree *ptr;
    tagtype tag;
    }stacknode;
    stacknode x;
    BTree *p;
    stacknode stack[MaxSize];
    int top=-1;
    p=BT;
    do
    {
    while (p!=NULL)
    {
    x.ptr = p;
    x.tag = L;//标记为左子树
    stack[++top]=x;
    p=p->left;
    }
    while (top!=-1 && stack[top].tag==R)
    {
    x=stack[top];
    top--;
    p=x.ptr;
    printf("%c",p->data);
    }
    if (top!=-1)
    {
    stack[top].tag=R;//标记为左子树
    p=stack[top].ptr->right;
    }
    }while (top!=-1);
    }

    int BTreeDepth(BTree *BT)//树的深度
    {
    int leftdep,rightdep;
    if (BT==NULL)
    return(0);
    else
    {
    leftdep=BTreeDepth(BT->left);
    rightdep=BTreeDepth(BT->right);
    if (leftdep>rightdep)
    return(leftdep+1);
    else
    return(rightdep+1);
    }
    }

    int leafcount(BTree *BT)//叶子结点数
    {
    if (BT==NULL)
    return(0);
    else if (BT->left==NULL && BT->right==NULL)
    return(1);
    else
    return(leafcount(BT->left)+leafcount(BT->right));
    }

    void main()
    {
    BTree *BT;
    char *s="A(B(D,E(H,I)),C(F,G))";
    creatree(&BT,s);
    printf("\n前序遍历(递归算法):");
    preorder(BT);
    printf("\n前序遍历(非递归算法):");
    preorder1(BT);
    printf("\n中序遍历(递归算法):");
    inorder(BT);
    printf("\n中序遍历(非递归算法):");
    inorder1(BT);
    printf("\n后序遍历(递归算法):");
    postorder(BT);
    printf("\n后序遍历(非递归算法):");
    postorder1(BT);
    printf("\nThe depth is %d\n",BTreeDepth(BT));
    printf("The leaves is %d\n",leafcount(BT));
    }
    0 0
添加回答
+ 订阅

了解行业+人工智能最先进的技术和实践,参与行业+人工智能实践项目

推荐文章
相似问题