以单个字符作为一个结点的信息，构 造一棵二叉树,然后输出该树中所有度为 1 的结点。

Question

根据输入的二叉树后序序列（以单个字符作为一个结点的信息）和中序序列，来构
造一棵二叉树，然后输出该树的前序序列，以及该树中所有度为 1 的结点。

Answer 1

你题目的解答代码如下：

#include<stdio.h>
#include<stdlib.h>
#define max 50
typedef char Elemtype;
Elemtype pre[max], in[max], post[max];

typedef struct BTNode{
    Elemtype data;
    struct BTNode *lchild, *rchild;
}BTree;

/* according to the postorder and inorder travelsal
    sequences to create a binary tree */
BTree* create(Elemtype postL, Elemtype postR, Elemtype inL, Elemtype inR){
    if(postL > postR)
        return NULL;
    BTree *root;
    root =  (BTree*)malloc(sizeof(BTree));
    root->data = post[postR];                //后序遍历序列的最后一个结点就是当前树的根结点
    int k;
    for(k = inL; k <= inR; k++){
        if(in[k] == post[postR])             //寻找当前树的根节点在中序遍历序列中的位置
            break;
    }
    int numLeft = k - inL;                   //root的左子树的结点总数
    root->lchild = create(postL, postL + numLeft - 1, inL, k - 1);  //root的左孩子所在的区间:中序 in[inL, k-1]
                                                                    //后序post[postL, postL + numLeft - 1]
    root->rchild = create(postL + numLeft, postR - 1, k + 1, inR);
    return root;                                                    //递归返回根结点地址
}

/* preorder traversal bases on user-defined stack*/
void preorderstack(BTree *root){
    BTree *stack[max];                      //自定义顺序栈
    int top = -1;                           //栈顶指针
    stack[++top] = root;                    //根结点进栈
    BTree *p;
    while(top != -1){
        p = stack[top--];                   //出栈，访问根
          printf("%c", p->data);
          if(p->rchild != NULL)               //若右孩子存在，让它进栈
            stack[++top] = p->rchild;       //注意，先让右孩子入栈
        if(p->lchild != NULL)               //若左孩子存在，让它进栈
            stack[++top] = p->lchild;
    }
}

/* level-order traversal bases on user-defined stack*/
void levelorder(BTree *root){
    BTree *queue[max];                      //自定义顺序循环队列
    int front =0, rear = 0;                 //队头/尾
    rear = (rear +1) % max;
    queue[rear] = root;                     //根结点进队
    BTree *p;
    while(front != rear){
          front = (front + 1)%max;
          p = queue[front];
          printf("%c", p->data);
          if(p->lchild != NULL){
              rear = (rear + 1) % max;
            queue[rear] = p->lchild;
        }
        if(p->rchild != NULL){
               rear = (rear + 1) % max;
            queue[rear] = p->rchild;
        }
    }
}

int main(){
    int n;        //树的结点个数
    printf("Total number of nodes: ");
    scanf("%d", &n);
    getchar();
    printf("Postorder: ");
    for(int i = 0; i < n; i++){
        scanf("%c", &post[i]);
    }
    getchar();
    printf("Inorder: ");
    for(int i = 0; i < n; i++){
        scanf("%c", &in[i]);
    }
    BTree *root = create(0, n - 1, 0, n - 1);
    printf("Preorder: ");
    preorderstack(root);

    printf("\nLevelorder: ");
    levelorder(root);
    return 0;
}

如有帮助，请点击我的回答下方的【采纳该答案】按钮帮忙采纳下，谢谢!