思路:栈操作
例如广义表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,则为右孩子
- 遇到左括号入栈,遇到右括号出栈
主要操作
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;
}
clear_Stack(s);
if (temp && !p) p = temp;
return p;
}
看代码
#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;
}
clear_Stack(s);
if (temp && !p) p = temp;
return 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;
}