树与二叉树

二叉树性质：度为0的节点比度为2的节点多一个。

解释：度为1的节点均可忽略；度为2的节点就相当于分割点，而度为0的节点就相当于线段；不分割时即有一条线段，当每多一个分割点时，线段也就相应会多一个。

二叉树分类（国际版）：

1. 完全二叉树（可编号）：设二叉树的深度为 h，除第 h 层外，其它各层 (1～h-1) 的节点数都达到最大个数，第 h 层所有的节点都连续集中在最左边
2. 满二叉树
3. 完美二叉树

二叉树可用广义表进行表示：A(B(D, E), C(F,)) 或 1(2(4, 5), 3(6,))（完全二叉树）

深搜遍历（栈或递归）：

1. 前序遍历
2. 中序遍历
3. 后序遍历

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

//结构定义：链表节点
typedef struct Node {
    int data;
    Node *lchild, *rchild;
} Node;

//结构定义：树
typedef struct Tree {
    Node *root;
    int length;
} Tree;

//结构操作
Node *getNewNode(int val);
Tree *getNewTree();
void clear_node(Node *node);
void clear_tree(Tree *tree);
Node *insert_node(Node *node, int val, int *flag);
int insert(Tree *tree, int val);
void output_node(Node *node);
void output(Tree *tree);
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() {
    srand(time(0));
    #define MAX_N 10
    Tree *tree = getNewTree();
    for (int i = 0; i < MAX_N; i++) {
        int val = rand() % 100;
        insert(tree, val);
        output(tree);
    }
    preorder(tree);
    inorder(tree);
    postorder(tree);
    #undef MAX_N
    clear_tree(tree);
    return 0;
}

//结构操作：获得一个新节点
Node *getNewNode(int val) {
    Node *node = (Node *)malloc(sizeof(Node));
    node->data = val;
    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;
}

//结构操作：插入元素的递归操作(排序二叉树)
Node *insert_node(Node *node, int val, int *flag) {
    if (node == NULL) {
        *flag = 1;
        return getNewNode(val);
    }
    if (val == node->data) return node;
    if (val < node->data) node->lchild = insert_node(node->lchild, val, flag);
    else node->rchild = insert_node(node->rchild, val, flag);
    return node;
}

//结构操作：插入一个元素
int insert(Tree *tree, int val) {
    if (tree == NULL) return 0;
    int flag = 0;
    tree->root = insert_node(tree->root, val, &flag);
    tree->length += flag;
    return flag;
}

//结构操作：输出该树的递归操作
void output_node(Node *node) {
    if (node == NULL) return;
    printf("%d", node->data);
    if (node->lchild == NULL && node->rchild == NULL) return;
    printf("(");
    output_node(node->lchild);
    printf(", ");
    output_node(node->rchild);
    printf(")");
    return;
}

//结构操作：用广义表的形式输出该树
void output(Tree *tree) {
    if (tree == NULL) return;
    printf("tree(%d): ", tree->length);
    output_node(tree->root);
    printf("\n");
    return;
}

//结构操作：前序遍历的递归操作
void preorder_node(Node *node) {
    if (node == NULL) return;
    printf("%d ", 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("%d ", 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("%d ", node->data);
    return;
}

//结构操作：用后序遍历的方式输出所有元素
void postorder(Tree *tree) {
    if (tree == NULL) return;
    printf("postorder: ");
    postorder_node(tree->root);
    printf("\n");
    return;
}