思路：栈操作

例如广义表A(B(D,R),K(G))

• 前序遍历：A, B, D, R, K, G
• 中序遍历：D, B, R, A, G, K
• 后序遍历：D, R, B, G, K, A

怎么判断左右孩子？

仔细观察，左孩子前面有左括号，右孩子前面为逗号，故可以定义一个flag判断左右孩子。

• 定义一个flag, 初始化为0，遇左括号变为0，遇到逗号变为1
• 遇到字母只需判断flag，flag 为0，则为左孩子，为1，则为右孩子
• 遇到左括号入栈，遇到右括号出栈

主要操作

xxxxxxxxxx
Node *build(const char *str, int *Node_num) { //广义表转二叉树函数 
    Stack *s = init_Stack(strlen(str));
    int flag = 0;
    Node *temp = NULL, *p = NULL;
    while (str[0]) {
        switch (str[0]) {
            case '(' :
                push(s, temp); // 根节点进行压栈操作
                flag = 0;
                break;
            case ')' :
                p = top(s); 
                pop(s);
                break;
            case ',' : flag = 1; break;
            case ' ' : break;
            default :
                temp = getNewNode(str[0]); //包装成节点
                if (!empty(s) && flag == 0) {
                    top(s)->lchild = temp; //左孩子
                } else if (!empty(s) && flag == 1) {
                    top(s)->rchild = temp; //右孩子
                }
                ++(*Node_num); // 计算
                break;
        }
        ++str; //指针右移, 每次只需判断str[0].
    }
    clear_Stack(s);
    if (temp && !p) p = temp; 
    return p;
}

看代码

​x
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

//二叉树结构定义 
typedef struct Node {
    char data;
    struct Node *lchild, *rchild;
} Node;

typedef struct Tree {
    Node *root;
    int length;
} Tree;
//栈的结构定义（存储二叉树的节点地址） 
typedef struct Stack {
    Node **data;
    int top, size;
} Stack;

Node *getNewNode(char); //节点初始化 
Tree *getNewTree();
void clear_Node(Node *);
void clear_Tree(Tree *);
Stack *init_Stack(int); //栈的初始化 
Node *top(Stack *); // 输出栈顶元素 
int empty(Stack *); // 栈的判空 
int push(Stack *); // 入栈操作 
int pop(Stack *);  // 出栈操作 

Node *getNewNode(char val) {
    Node *p = (Node *)malloc(sizeof(Node));
    p->data = val;
    p->lchild = p->rchild = NULL;
    return p;
} 

Tree *getNewTree() {
    Tree *t = (Tree *)malloc(sizeof(Tree));
    t->length = 0;
    t->root = NULL;
    return t;
}

void clear_Node(Node *root) {
    if (root == NULL) return ;
    clear_Node(root->lchild);
    clear_Node(root->rchild);
    free(root);
    return ;
}

void clear_Tree(Tree *t) {
    if (t == NULL) return ;
    clear_Node(t->root);
    free(t);
    return ;
}

Stack *init_Stack(int n) {
    Stack *s = (Stack *)malloc(sizeof(Stack));
    s->data = (Node **)malloc(sizeof(Node *) * n);
    s->top = -1;
    s->size = n;
    return s;
}

void clear_Stack(Stack *s) {
    if (s == NULL) return ;
    free(s->data);
    free(s);
    return ;
    
} 

//栈的主要操作 
Node *top(Stack *s) {
    return s->data[s->top];
}

int empty(Stack *s) {
    return s->top == -1;
}

int push(Stack  *s, Node *val) {
    if (s == NULL) return 0;
    if (s->top == s->size - 1) return 0;
    s->data[++(s->top)] = val;
    return 1;
}

int pop(Stack *s) {
    if (s == NULL) return 0;
    if (empty(s)) return 0;
    s->top -= 1; // 不进行销毁操作，只需把该节点剔除
    return 1;
}


Node *build(const char *str, int *Node_num) { //广义表转二叉树函数 
    Stack *s = init_Stack(strlen(str));
    int flag = 0;
    Node *temp = NULL, *p = NULL;
    while (str[0]) {
        switch (str[0]) {
            case '(' :
                push(s, temp); // 根节点进行压栈操作
                flag = 0;
                break;
            case ')' :
                p = top(s); 
                pop(s);
                break;
            case ',' : flag = 1; break;
            case ' ' : break;
            default :
                temp = getNewNode(str[0]); //包装成节点
                if (!empty(s) && flag == 0) {
                    top(s)->lchild = temp; //左孩子
                } else if (!empty(s) && flag == 1) {
                    top(s)->rchild = temp; //右孩子
                }
                ++(*Node_num); // 计算
                break;
        }
        ++str; //指针右移, 每次只需判断str[0].
    }
    clear_Stack(s);
    if (temp && !p) p = temp; 
    return p; //p指向根节点
}

//前中后序遍历输出
void in_order_Node(Node *root) {
    if (root == NULL) return ;
    in_order_Node(root->lchild);
    printf("%c ", root->data);
    in_order_Node(root->rchild);
    return ;
}

void in_order(Tree *t) {
    if (t == NULL) return ;
    printf("in_rder(%d) : ", t->length);
    in_order_Node(t->root);
    printf("\n");
    return ;
} 

void pre_order_Node(Node *root) {
    if (root == NULL) return ;
    printf("%c ", root->data);
    pre_order_Node(root->lchild);
    pre_order_Node(root->rchild);
    return ;
}

void pre_order(Tree *t) {
    if (t == NULL) return ;
    printf("per_rder(%d) : ", t->length);
    pre_order_Node(t->root);
    printf("\n");
    return ;
} 

void post_order_Node(Node *root) {
    if (root == NULL) return ;
    post_order_Node(root->lchild);
    post_order_Node(root->rchild);
    printf("%c ", root->data);
    return ;
}

void post_order(Tree *t) {
    if (t == NULL) return ;
    printf("post_rder(%d) : ", t->length);
    post_order_Node(t->root);
    printf("\n");
    return ;
} 

int main() {
    char str[1000] = {0};
    scanf("%[^\n]s", str);
    getchar();
    Tree *t = getNewTree();
    int Node_num = 0;
    t->root = build(str, &Node_num);
    t->length = Node_num;
    pre_order(t);
    in_order(t);
    post_order(t);
    return 0;
}