前序遍历和中序遍历 & 后序遍历和中序遍历可以还原出唯一的二叉树,而前序遍历和后序遍历不行(满二叉树时貌似可以,但只有一个根节点和一个子孩子时一定不行)
//输入:
A(B(, D), C(E))
//输出:
preorder: A B D C E
inorder: B D A E C
postorder: D B E C A
自定义栈
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct Node {
char data;
Node *lchild, *rchild;
} Node;
typedef struct Tree {
Node *root;
int length;
} Tree;
typedef struct Stack {
Node **data;
int size, length;
} Stack;
Node *getNewNode(char data);
Tree *getNewTree();
void clear_node(Node *node);
void clear_tree(Tree *tree);
Tree *build_tree(const char *str);
void preorder_node(Node *node);
void preorder(Tree *tree);
void inorder_node(Node *node);
void inorder(Tree *tree);
void postorder_node(Node *node);
void postorder(Tree *tree);
Stack *init_stack(int size);
void clear_stack(Stack *stack);
int push(Stack *stack, Node *val);
Node *top(Stack *stack);
int empty(Stack *stack);
int pop(Stack *stack);
int main() {
char str[1000] = {0};
scanf("%[^\n]s", str);
getchar(); //读走scanf遗留下的'\n'(惯常操作)
Tree *tree = build_tree(str);
preorder(tree);
inorder(tree);
postorder(tree);
clear_tree(tree);
return 0;
}
Node *getNewNode(char data) {
Node *node = (Node *)malloc(sizeof(Node));
node->data = data;
node->lchild = node->rchild = NULL;
return node;
}
Tree *getNewTree() {
Tree *tree = (Tree *)malloc(sizeof(Tree));
tree->root = NULL;
tree->length = 0;
return tree;
}
void clear_node(Node *node) {
if (node == NULL) return;
clear_node(node->lchild);
clear_node(node->rchild);
free(node);
return;
}
void clear_tree(Tree *tree) {
if (tree == NULL) return;
clear_node(tree->root);
free(tree);
return;
}
//结构操作:广义表转二叉树
Tree *build_tree(const char *str) {
Tree *tree = getNewTree();
Stack *stack = init_stack(strlen(str));
Node *node = NULL;
int flag = 0;
while (str[0]) {
switch (str[0]) {
case '(':
push(stack, node);
flag = 0;
break;
case ')':
pop(stack);
break;
case ',':
flag = 1;
break;
case ' ':
break;
default:
node = getNewNode(str[0]);
if (empty(stack)) {
tree->root = node;
} else if (flag == 0) {
top(stack)->lchild = node;
} else {
top(stack)->rchild = node;
}
tree->length += 1;
break;
}
str++;
}
clear_stack(stack);
return tree;
}
//结构操作:前序遍历的递归操作
void preorder_node(Node *node) {
if (node == NULL) return;
printf("%c ", node->data);
preorder_node(node->lchild);
preorder_node(node->rchild);
return;
}
//结构操作:用前序遍历的方式输出所有元素
void preorder(Tree *tree) {
if (tree == NULL) return;
printf("preorder: ");
preorder_node(tree->root);
printf("\n");
return;
}
//结构操作:中序遍历的递归操作
void inorder_node(Node *node) {
if (node == NULL) return;
inorder_node(node->lchild);
printf("%c ", node->data);
inorder_node(node->rchild);
return;
}
//结构操作:用中序遍历的方式输出所有元素
void inorder(Tree *tree) {
if (tree == NULL) return;
printf("inorder: ");
inorder_node(tree->root);
printf("\n");
return;
}
//结构操作:后序遍历的递归操作
void postorder_node(Node *node) {
if (node == NULL) return;
postorder_node(node->lchild);
postorder_node(node->rchild);
printf("%c ", node->data);
return;
}
//结构操作:用后序遍历的方式输出所有元素
void postorder(Tree *tree) {
if (tree == NULL) return;
printf("postorder: ");
postorder_node(tree->root);
printf("\n");
return;
}
Stack *init_stack(int size) {
Stack *stack = (Stack *)malloc(sizeof(Stack));
stack->data = (Node **)malloc(sizeof(Node *) * size);
stack->size = size;
stack->length = 0;
return stack;
}
void clear_stack(Stack *stack) {
if (stack == NULL) return;
free(stack->data);
free(stack);
return;
}
int push(Stack *stack, Node *val) {
if (stack == NULL) return 0;
if (stack->length == stack->size) return 0;
stack->data[stack->length++] = val;
return 1;
}
Node *top(Stack *stack) {
return stack->data[stack->length - 1];
}
int empty(Stack *stack) {
return stack->length == 0;
}
int pop(Stack *stack) {
if (stack == NULL) return 0;
if (empty(stack)) return 0;
stack->length -= 1;
return 1;
}
系统栈(递归)
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct Node {
char data;
Node *lchild, *rchild;
} Node;
typedef struct Tree {
Node *root;
int length;
} Tree;
typedef struct Stack {
Node **data;
int size, length;
} Stack;
Node *getNewNode(char data);
Tree *getNewTree();
void clear_node(Node *node);
void clear_tree(Tree *tree);
char *build_recur(char *str, Node *last_node, Tree *tree);
Tree *build_tree(char *str);
void preorder_node(Node *node);
void preorder(Tree *tree);
void inorder_node(Node *node);
void inorder(Tree *tree);
void postorder_node(Node *node);
void postorder(Tree *tree);
int main() {
char str[1000] = {0};
scanf("%[^\n]s", str);
getchar(); //读走scanf遗留下的'\n'(惯常操作)
Tree *tree = build_tree(str);
preorder(tree);
inorder(tree);
postorder(tree);
clear_tree(tree);
return 0;
}
Node *getNewNode(char data) {
Node *node = (Node *)malloc(sizeof(Node));
node->data = data;
node->lchild = node->rchild = NULL;
return node;
}
Tree *getNewTree() {
Tree *tree = (Tree *)malloc(sizeof(Tree));
tree->root = NULL;
tree->length = 0;
return tree;
}
void clear_node(Node *node) {
if (node == NULL) return;
clear_node(node->lchild);
clear_node(node->rchild);
free(node);
return;
}
void clear_tree(Tree *tree) {
if (tree == NULL) return;
clear_node(tree->root);
free(tree);
return;
}
//结构操作:广义表转二叉树之递归
char *build_recur(char *str, Node *last_node, Tree *tree) {
Node *node = NULL;
int flag = 0;
while (str[0]) {
switch (str[0]) {
case '(':
str = build_recur(++str, node, tree);
flag = 0;
break;
case ')':
return str;
case ',':
flag = 1;
break;
case ' ':
break;
default:
node = getNewNode(str[0]);
if (last_node == NULL) {
tree->root = node;
} else if (flag == 0) {
last_node->lchild = node;
} else {
last_node->rchild = node;
}
tree->length += 1;
break;
}
str++;
}
return str;
}
//结构操作:广义表转二叉树
Tree *build_tree(char *str) {
Tree *tree = getNewTree();
build_recur(str, tree->root, tree);
return tree;
}
//结构操作:前序遍历的递归操作
void preorder_node(Node *node) {
if (node == NULL) return;
printf("%c ", node->data);
preorder_node(node->lchild);
preorder_node(node->rchild);
return;
}
//结构操作:用前序遍历的方式输出所有元素
void preorder(Tree *tree) {
if (tree == NULL) return;
printf("preorder: ");
preorder_node(tree->root);
printf("\n");
return;
}
//结构操作:中序遍历的递归操作
void inorder_node(Node *node) {
if (node == NULL) return;
inorder_node(node->lchild);
printf("%c ", node->data);
inorder_node(node->rchild);
return;
}
//结构操作:用中序遍历的方式输出所有元素
void inorder(Tree *tree) {
if (tree == NULL) return;
printf("inorder: ");
inorder_node(tree->root);
printf("\n");
return;
}
//结构操作:后序遍历的递归操作
void postorder_node(Node *node) {
if (node == NULL) return;
postorder_node(node->lchild);
postorder_node(node->rchild);
printf("%c ", node->data);
return;
}
//结构操作:用后序遍历的方式输出所有元素
void postorder(Tree *tree) {
if (tree == NULL) return;
printf("postorder: ");
postorder_node(tree->root);
printf("\n");
return;
}
总结:
- 栈操作之压栈 = 调用函数
- 栈操作之出栈 = 函数返回
- 栈操作之访问栈顶元素 = 将栈顶元素作为参数传入下一层函数