二叉树的创建、（中先后序，广义表）遍历

50 阅读 0 评论 33 点赞

我是靠谱客的博主繁荣路灯，最近开发中收集的这篇文章主要介绍二叉树的创建、（中先后序，广义表）遍历，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

typedef struct Node {
        int data;
        struct Node *lchild, *rchild;
} Node;

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

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

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

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

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

Node *insert_node(Node *root, int val, int *flag) {
        if (root == NULL) {
                *flag = 1;
                return getNewNode(val);
        }
        if (root->data == val) return root;
        if (val < root->data) root->lchild = insert_node(root->lchild, val, flag);
        else root->rchild = insert_node(root->rchild, val, flag);
        return root;
}

void insert(Tree *tree, int val) {
        int flag = 0;
        tree->root = insert_node(tree->root, val, &flag);
        tree->n += flag;
        return ;
}

void pre_order_node (Node *node) {
        if (node == NULL) return ;
        printf("%d ", node->data);
        pre_order_node(node->lchild);
        pre_order_node(node->rchild);
        return ;
}

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

void in_order_node (Node *node) {
        if (node == NULL) return ;
        in_order_node(node->lchild);
        printf("%d ", node->data);
        in_order_node(node->rchild);
        return ;
}

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

void post_order_node (Node *node) {
        if (node == NULL) return ;
        post_order_node(node->lchild);
        post_order_node(node->rchild);
        printf("%d ", node->data);
        return ;
}

void post_order(Tree *tree) {
        if (tree == NULL) return ;
        printf("post_order: ");
        post_order_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 ;
}

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

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