树与二叉树

1.树

树形结构可用于解决具有完全包含关系的问题，树的结点代表集合、树的边代表关系：

typedef struct Node {
    int data;
    struct Node *next;
} Node, *LinkedList;

typedef struct Node {
    int data;
    struct Node *next[3];
} Node, *Tree;

2.二叉树

完全二叉树：

1. 编号为i的子结点：左孩子编号为2 * i，右孩子编号为2 * i + 1
2. 可以用连续的空间存储（数组）

#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 length;//结点个数
} Tree;

//初始化结点
Node *initNode(int val) {
    Node *p = (Node *)malloc(sizeof(Node));
    p->data = val;
    p->lchild = p->rchild = NULL;
    return p;
}

//初始化二叉树
Tree *initTree() {
    Tree *t = (Tree *)malloc(sizeof(Tree));
    t->root = NULL;
    t->length = 0;
    return t;
}

//结点销毁
void destroyNode(Node *node) {
    if (node == NULL) return;
    destroyNode(node->lchild);
    destroyNode(node->rchild);
    free(node);
    return ;
}

//二叉树销毁
void clear(Tree *t) {
    if (t == NULL) return ;
    destroyNode(t->root);
    free(t);
    return ;
}

//结点插入
Node *insertNode(Node *root, int val, int *flag) {
    //1.如果节点不存在 则直接调用initNode方法创建结点并返回
    if (root == NULL) {
        *flag = 1;//插入成功则将flag置为1
        return initNode(val);
    }
    //2.采用二叉树排序树插入元素的方式 实现插入操作 
    if (root->data == val) return root;//根节点的值等于待插入结点的值 则不进行插入操作
    if (root->data > val) { 
        root->lchild = insertNode(root->lchild, val, flag);//根节点值大于待插入val值 则递归的向左子树上插入结点
    } else { 
        root->rchild = insertNode(root->rchild, val, flag);//根节点值小于待插入结点值 则递归的向右子树上插入结点
    }
    return root;
}

//二叉树结点插入
void insert(Tree *t, int val) {
    if (t == NULL) return ;
    int flag = 0;//结点插入操作是否插入成功
    t->root = insertNode(t->root, val, &flag);//调用结点插入方法
    t->length += flag;
    return ;
}

//前序遍历
void preOrderNode(Node *root) {
    if (root == NULL) return ;
    printf("%d ", root->data);
    preOrderNode(root->lchild);//递归访问左子树
    preOrderNode(root->rchild);//递归访问右子树
    return ;
}

//二叉树前序遍历
void preOrder(Tree *t) {
    if (t == NULL) return ;
    printf("preOrder : ");
    preOrderNode(t->root);
    printf("\n");
}

//中序遍历
void inOrderNode(Node *root) {
    if (root == NULL) return ;
    inOrderNode(root->lchild);
    printf("%d ", root->data);
    inOrderNode(root->rchild);
    return ;
}

//二叉树中序遍历
void inOrder(Tree *t) {
    if (t == NULL) return ;
    printf("inOrder : ");
    inOrderNode(t->root);
    printf("\n");
    return ;
}

//后序遍历
void postOrderNode(Node *root) {
    if (root == NULL) return ;
    postOrderNode(root->lchild);
    postOrderNode(root->rchild);
    printf("%d ", root->data);
    return ;
}

//二叉树后序遍历
void postOrder(Tree *t) {
    if (t == NULL) return ;
    printf("postOrder : ");
    postOrderNode(t->root);
    printf("\n");
    return ;
}

//以广义表的形式打印二叉树
void outputNode(Node *root) {
    if (root == NULL) return ;//根节点为空 直接返回
    printf("%d", root->data);
    if (root->lchild == NULL && root->rchild == NULL) return ;//根节点的左子树 or 右子树为空 直接返回
    printf("(");
    outputNode(root->lchild);//递归左子树内容
    printf(",");
    outputNode(root->rchild);//递归右子树内容
    printf(")");
    return ;
}

//二叉树打印操作
void output(Tree *t) {
    if (t == NULL) return ;
    printf("tree(%d) : ", t->length);//输出二叉树结点个数
    outputNode(t->root);//从当前根节点开始打印
    printf("\n");
    return ;
} 

int main(){
    srand(time(0));
    Tree *tree = initTree();
    #define MAX_OP 10
    for (int i = 0; i < MAX_OP; ++i) {
        int val = rand() % 100;//随机生成100以内的值 进行插入操作
        insert(tree, val);
        output(tree);
    }
    #undef MAX_OP
    preOrder(tree);
    inOrder(tree);
    postOrder(tree);
    clear(tree);
    return 0;
}

3.广义表转二叉树

广义表转二叉树类似与括号序列问题，可以借助栈结构来解决：

#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;
    int size;
} SqStack;

Node *initNode(char);//树结点初始化
Tree *initTree();//二叉树初始化
void clearNode(Node *);//销毁二叉树结点
void clearTree(Tree *);//销毁二叉树

SqStack *initStack(int);//栈的初始化
void DestroyStack(SqStack *);//栈的销毁
Node *top(SqStack *);//输出栈顶元素
int empty(SqStack *, Node *);
int push(SqStack *, Node *);
int pop(SqStack *);

//1-1.初始化结点
Node *initNode(char val) {
    Node *p = (Node *)malloc(sizeof(Node));
    p->data = val;
    p->lchild = p->rchild = NULL;
    return p;
}

//1-2.初始化二叉树
Tree *initTree() {
    Tree *t = (Tree *)malloc(sizeof(Tree));
    t->root = NULL;
    t->length = 0;
    return t;
}

//1-3.结点销毁
void destroyNode(Node *node) {
    if (node == NULL) return;
    destroyNode(node->lchild);
    destroyNode(node->rchild);
    free(node);
    return ;
}

//1-4.二叉树销毁
void clear(Tree *t) {
    if (t == NULL) return ;
    destroyNode(t->root);
    free(t);
    return ;
}

//2-1.初始化栈操作
SqStack *initStack(int n) {
    SqStack *s = (SqStack *)malloc(sizeof(SqStack));
    s->data = (Node **)malloc(sizeof(Node *) * n);
    s->top = -1;
    s->size = n;
    return s;
}

//2-2.栈的销毁操作
void DestroyStack(SqStack *s) {
    if (s == NULL) return;
    free(s->data);
    free(s);
    return;
}

//2-3.获取栈顶元素
Node *GetTop(SqStack *s) {
    return s->data[s->top];
}

//2-4.判断栈是否为空
int StackEmpty(SqStack *s) {
    return s->top == -1;
}

//2-5.入栈操作
int Push(SqStack *s, Node *val) {
    if (s == NULL) return 0;
    if (s->top == s->size - 1) return 0;//栈已满
    s->top++;//注意：这里栈顶指针指向的是栈顶元素故需要先++再赋值
    s->data[s->top] = val;
    return 1;
}

//2-6.出栈操作
int Pop(SqStack *s) {
    if (s == NULL) return 0;
    if (StackEmpty(s)) return 0;
    s->top--;
    return 1;
}

//广义表转二叉树（核心部分）
Node *build(const char *str, int *nodeNum) {
    SqStack *s = initStack(strlen(str));
    int flag = 0;
    Node *temp = NULL;
    Node *p = NULL;
    while (str[0]) {
        switch (str[0]) {
            case '(' :
                Push(s, temp);
                flag = 0;
                break;
            case ')' :
                p = GetTop(s);
                Pop(s);
                break;
            case ',' : flag = 1; break;
            case ' ' : break;
            default :
                temp = initNode(str[0]);
                if (!StackEmpty(s) && flag == 0) {
                    GetTop(s)->lchild = temp;
                } else if (!StackEmpty(s) && flag == 1) {
                    GetTop(s)->rchild = temp;
                }
                ++(*nodeNum);
                break;
        }
        ++str;
    }
    DestroyStack(s);
    if (temp && p == NULL) p == temp;
    return p;
}

//前序遍历
void preOrderNode(Node *root) {
    if (root == NULL) return ;
    printf("%c ", root->data);
    preOrderNode(root->lchild);//递归访问左子树
    preOrderNode(root->rchild);//递归访问右子树
    return ;
}

//二叉树前序遍历
void preOrder(Tree *t) {
    if (t == NULL) return ;
    printf("preOrder(%d) : ", t->length);
    preOrderNode(t->root);
    printf("\n");
}

//中序遍历
void inOrderNode(Node *root) {
    if (root == NULL) return ;
    inOrderNode(root->lchild);
    printf("%c ", root->data);
    inOrderNode(root->rchild);
    return ;
}

//二叉树中序遍历
void inOrder(Tree *t) {
    if (t == NULL) return ;
    printf("inOrder(%d) : ", t->length);
    inOrderNode(t->root);
    printf("\n");
    return ;
}

//后序遍历
void postOrderNode(Node *root) {
    if (root == NULL) return ;
    postOrderNode(root->lchild);
    postOrderNode(root->rchild);
    printf("%c ", root->data);
    return ;
}

//二叉树后序遍历
void postOrder(Tree *t) {
    if (t == NULL) return ;
    printf("postOrder(%d) : ", t->length);
    postOrderNode(t->root);
    printf("\n");
    return ;
}

int main() {
    char str[1000] = {0};
    int nodeNum = 0;
    
    scanf("%[^\n]s", str);
    getchar();

    Tree *t = initTree();
    t->root = build(str, &nodeNum);
    t->length = nodeNum;

    preOrder(t);
    inOrder(t);
    postOrder(t);
    clear(t);
    return 0;	
}