05 数据结构与算法之二叉排序树(建树 广义表 前中后序)（C语言实现）

注：只给出C语言实现代码，涉及到的数据结构相关概念请自行阅读相关书籍或参考其他博文；

本文代码功能：给定整数建立二叉排序树，以广义表形式打印建树过程。建树完成后输出前中后序版。额外增加调试版帮助理解递归插入过程。

①版本1(建树，广义表打印，前中后序)

#include 
#include 
#include 




typedef struct Node {
    int data;//树节点数据域存整数
    struct Node *lchild, *rchild;
} Node;

typedef struct Tree {
    Node *root;
    int length;//总结点数
} Tree;

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

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

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

void clear_tree(Tree *tree) {
    if (tree == NULL) return ;
    clear_node(tree->root);
    free(tree);
    return ;
}
Node *insert_node(Node *, int, int *);
void insert(Tree *tree, int val) { //二叉排序树插入方式插入
    if (tree == NULL) return ;
    int flag = 0;
    tree->root = insert_node(tree->root, val, &flag);
    tree->length += flag;
    return ;
}

Node *insert_node(Node *root, int val, int *flag) {
    if (root == NULL) { //条件成立则一定插入成功
        *flag = 1; //加入falg判断插入是否成功，原来就有的节点就不能插入
        return init_node(val);
    }
    if (root->data == val) return root; //原来就有的节点就不能插入
    if (root->data > val) root->lchild = insert_node(root->lchild, val, flag);
    else root->rchild = insert_node(root->rchild, val, flag);
    return root;
}

void pre_order_node(Node *);
void pre_order(Tree *tree) {//前序遍历
    if (tree == NULL) return ;
    printf("pre_order :");
    pre_order_node(tree->root); //封装一个方法 打印节点
    printf("n");
    return ;
}

void pre_order_node(Node *root) {
    if (root == NULL) return ;
    printf("%2d ", root->data);
    pre_order_node(root->lchild); //递归打印左子树值
    pre_order_node(root->rchild); //递归打印右子树值
    return ;
}

void in_order_node(Node *);
void in_order(Tree *tree) {
    if (tree == NULL) return ;
    printf("in_order  :");
    in_order_node(tree->root);
    printf("n");
    return ;
}

void in_order_node(Node *root) {
    if (root == NULL) return ;
    in_order_node(root->lchild); //递归打印左子树值
    printf("%2d ", root->data);
    in_order_node(root->rchild); //递归打印右子树值
    return ;
}

void post_order_node(Node *);
void post_order(Tree *tree) {
    if (tree == NULL) return ;
    printf("post_order:");
    post_order_node(tree->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("%2d ", root->data);
    return ;
}

void output_node(Node *);
void output(Tree *tree) {
    if (tree == NULL) return ;
    printf("tree(%2d):", tree->length);
    output_node(tree->root);
    printf("n");
    return ;
}

void output_node(Node *root) {//以广义表形式打印树结构
    if (root == NULL) return ;
    printf("%d", root->data);
    if (root->lchild == NULL && root->rchild == NULL) return ;
    printf("(");
    output_node(root->lchild);
    printf(",");
    output_node(root->rchild);
    printf(")");
    return ;
}

int main() {
    srand(time(0));
    Tree *tree = init_tree();
    #define MAX_OP 10
    for (int i = 0; i < MAX_OP; i++) {
        int val = rand() % 100;
        insert(tree, val);
        output(tree);
    }
    pre_order(tree);
    in_order(tree);
    post_order(tree);
    #undef MAX_OP
    clear_tree(tree);
    return 0;
}

②版本2(调试版，帮助理解递归插入过程)

#include 
#include 
#include 



#define GREEN(a) "33[32m" a "33[0mn"
#define Blue(a) "33[34m" a "33[0m"
typedef struct Node {
    int data;//树节点数据域存整数
    struct Node *lchild, *rchild;
} Node;

typedef struct Tree {
    Node *root;
    int length;//总结点数
} Tree;

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

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

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

void clear_tree(Tree *tree) {
    if (tree == NULL) return ;
    clear_node(tree->root);
    free(tree);
    return ;
}

Node *insert_node(Node *, int, int *, int *);
void insert(Tree *tree, int val) { //二叉排序树插入方式插入
    if (tree == NULL) return ;
    int flag = 0, count = 0;;
    tree->root = insert_node(tree->root, val, &flag, &count);
    tree->length += flag;
    
    return ;
}

Node *insert_node(Node *root, int val, int *flag, int *count) {
    if (root == NULL) { //条件成立则一定插入成功
        *flag = 1; //加入falg判断插入是否成功，原来就有的节点就不能插入
        printf(GREEN("root count = %d"), (*count)++);
        return init_node(val);
    }
    if (root->data == val) return root; //原来就有的节点就不能插入
    //printf("pre:root->left or right count = %dn", (*count)++);
    if (root->data > val) {
        printf(Blue("left in  count = %dn"), (*count)++);
        root->lchild = insert_node(root->lchild, val, flag, count);
        printf("left out count = %dn", (*count)++);
    }
    else {
        printf(Blue("right in  count = %dn"), (*count)++);
        root->rchild = insert_node(root->rchild, val, flag, count);
        printf("right out count = %dn", (*count)++);
    }

    printf("post: over count = %dn", (*count)++);
    return root;
}


void pre_order_node(Node *root) {
    if (root == NULL) return ;
    printf("%2d ", root->data);
    pre_order_node(root->lchild); //递归打印左子树值
    pre_order_node(root->rchild); //递归打印右子树值
    return ;
}


void in_order_node(Node *root) {
    if (root == NULL) return ;
    in_order_node(root->lchild); //递归打印左子树值
    printf("%2d ", root->data);
    in_order_node(root->rchild); //递归打印右子树值
    return ;
}



void post_order_node(Node *root) {
    if (root == NULL) return ;
    post_order_node(root->lchild); //递归打印左子树值
    post_order_node(root->rchild); //递归打印右子树值
    printf("%2d ", root->data);
    return ;
}



void output_node(Node *root) {//以广义表形式打印树结构
    if (root == NULL) return ;
    printf("%d", root->data);
    if (root->lchild == NULL && root->rchild == NULL) return ;
    printf("(");
    output_node(root->lchild);
    printf(",");
    output_node(root->rchild);
    printf(")");
    return ;
}

int main() {
    srand(time(0));
    Tree *tree = init_tree();
    #define MAX_OP 10
    for (int i = 0; i < MAX_OP; i++) {
        int val = rand() % 100;
        insert(tree, val);
        printf("tree(%2d):", tree->length);
        output_node(tree->root);
        printf("n");
    }
    printf("pre :");pre_order_node(tree->root); printf("n");
    printf("in  :");in_order_node(tree->root);  printf("n");
    printf("post:");post_order_node(tree->root);printf("n");
    #undef MAX_OP
    clear_tree(tree);
    return 0;
}

③广义表转二叉树(自建栈）

#include 
#include 
#include 


typedef struct Node { //二叉树节点
    char data;
    struct Node *lchild, *rchild;
} Node;

typedef struct Tree {
    Node *root;
    int length;
} Tree;

typedef struct Stack {
    Node **data;//data指针存“Node *”类型数据
    int top, capacity;
} Stack;

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

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

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

void ClearTree(Tree *tree) {
    if (tree == NULL) return ;
    ClearNode(tree->root);
    free(tree);
    return ;
}

Stack *GetNewStack(int n) {
    Stack *stack = (Stack *)malloc(sizeof(Stack));
    stack->data = (Node **)malloc(sizeof(Node *) * n);
    stack->capacity = n;
    stack->top = -1;
    return stack;
}

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

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

Node *top(Stack *stack) {
    return stack->data[stack->top];
}

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

int pop(Stack *stack) {
    if (stack == NULL) return 0;
    if (empty(stack)) return 0;
    stack->top -= 1;
    return 1;
}

Node *build(const char *str, int *node_num){//返回值为整个树的根节点
  Stack *s = GetNewStack(strlen(str));//初始化栈的大小为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;//flag标记，为上一个节点的右孩子
      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;//将字符串的地址+1
  }
  ClearStack(s);
  if(temp && !p) p = temp;//特殊处理当树只有一个节点的情况，此时p为空
  return p;//返回最后一次弹栈的元素即为根
}

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 *tree) {
    if (tree == NULL) return;
    printf("pre_order(%d) : ", tree->length);
    pre_order_node(tree->root);
    printf("n");
    return ;
}

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 *tree) {
    if (tree == NULL) return;
    printf("in_order(%d) : ", tree->length);
    in_order_node(tree->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 *tree) {
    if (tree == NULL) return;
    printf("post_order(%d) : ", tree->length);
    post_order_node(tree->root);
    printf("n");
    return ;
}

int main(){
  char str[1000] = {0};
  int node_num = 0;
  scanf("%[^n]s",str);//输入带有空格的字符串 A (B (, D) , C(E) )
  getchar();//吞掉上一个空格
  Tree *tree = GetNewTree();
  tree->root = build(str, &node_num);
  tree->length = node_num;
  pre_order(tree);
  in_order(tree);
  post_order(tree);
  return 0;
}