数据结构-二叉树

树的相关概念：

1、节点的度：树中一个节点的孩子个数称为该节点的度， 所有节点的度的最大值是树的度

2、分支节点：度大于0的节点称为分支节点

3、叶子结点：度为0的节点称为叶子结点

4、节点的层次（深度）：从上往下数，根节点为1层，依次往下加1

5、树的高度（深度）：树中节点的最大层次

6、树中节点的各子树从左至又是有次序的，不能互换，则该树称为有序树，否则称为无序树

7、双亲节点或父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点

8、孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点；

9、兄弟节点：具有相同父节点的节点互称为兄弟节点； 如上图：B、C是兄弟节点

10、森林：森林是m（m >= 0 )棵互不相交的树的集合，

11、树去掉根节点就成为森林，森林加上根节点就是树

1.逻辑结构：树形结构（元素之间存在一对二关系）

2.存储结构：既可以顺序存储，也可以链式存储
注意：如果是顺序存储，必须是完全二叉树，如果是普通二叉树，需要转换成完全二叉树，在进行存储，
会造成内存浪费，推荐使用链式存储

3.二叉树链式存储适用于所有的二叉树

二叉树的性质：
1、二叉树的度数为2
2、二叉树严格区分左子树和右子树
3、二叉树的第k层上最多有2^(k-1)个节点
4、深度为k的二叉树，最多有2^k  + 1个节点
5、任意一棵二叉树，叶子结点的个数比度数为2的节点个数多1  

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>

//定义二叉树的结构体
typedef char BT;
typedef struct BTreeBode {
    BT val;//存放二叉树节点元素值
    struct BTreeBode* left;//指向左子节点
    struct BTreeBode* right;//指向右子节点
}BTN;

//创建二叉树的三个函数
void init_tree(BTN** bt);
void init_tree1(BTN** bt);
void init_tree2(BTN** bt);

void PreOrder(BTN* bt);
void MidOrder(BTN* bt);
void EndOrder(BTN* bt);

int main() {
    BTN* bt = NULL;//二叉树的根节点指针

    //二叉树的初始化
    printf("请先序创建一个二叉树\n");
    init_tree(&bt);

    printf("请中序创建一个二叉树\n");
    init_tree1(&bt);

    printf("请后序创建一个二叉树\n");
    init_tree2(&bt);

    //先序遍历
    PreOrder(bt);
    printf("\n");

    //中序遍历
    MidOrder(bt);
    printf("\n");

    //后序遍历
    EndOrder(bt);
    return 0;
}

//先序创建：根左右   初始化函数，就是把树的所有节点存进去的过程   
void init_tree(BTN** bt) {
    BT val = 0;
    scanf("%c", &val);   //%c,一次只接收一个字符
    if (val == '#') {
        //空树
        *bt = NULL;
    }
    else {
        //创建新节点
        *bt = (BTN*)malloc(sizeof(BTN));
        (*bt)->val = val;
        init_tree(&(*bt)->left);//创建左子树
        init_tree(&(*bt)->right);//创建右子树
    }
}

//中序创建：左根右   初始化函数，就是把树的所以节点存进去的过程   
void init_tree1(BTN** bt) {
    BT val = 0;
    scanf("%c", &val);   //%c,一次只接收一个字符
    if (val == '#') {
        //空树
        *bt = NULL;
    }
    else {
        //创建新节点
        *bt = (BTN*)malloc(sizeof(BTN));
        init_tree1(&(*bt)->left);//创建左子树
        (*bt)->val = val;
        init_tree1(&(*bt)->right);//创建右子树
    }
}

//后序创建：左右根   初始化函数，就是把树的所以节点存进去的过程   
void init_tree2(BTN** bt) {
    BT val = 0;
    scanf(" %c", &val);   //%c,一次只接收一个字符
    if (val == '#') {
        //空树
        *bt = NULL;
    }
    else {
        //创建新节点
        *bt = (BTN*)malloc(sizeof(BTN));
        init_tree2(&(*bt)->left);//创建左子树
        init_tree2(&(*bt)->right);//创建右子树
        (*bt)->val = val;
    }
}

//先序遍历函数          根  左  右      A B C D E
void PreOrder(BTN* bt) {
    if (bt == NULL) {
        return;
    }
    printf("%c ", bt->val);
    PreOrder(bt->left);//左子树
    PreOrder(bt->right);//右子树
}

//中序遍历函数          左  根  右     C B D A E
void MidOrder(BTN* bt) {
    if (bt == NULL) {//递归调用
        return;
    }
    MidOrder(bt->left);//左子树
    printf("%c ", bt->val);
    MidOrder(bt->right);//右子树
}

//后序遍历函数          左  右  根        C D B E A
void EndOrder(BTN* bt) {
    if (bt == NULL) {//递归调用
        return;
    }
    EndOrder(bt->left);//左子树
    EndOrder(bt->right);//右子树
    printf("%c ", bt->val);
}