数据结构——树和二叉树
1、树
1、定义
（1）是一种非线性的数据结构，又叫做树型数据结构
（2）树是n(n >=0)个节点的有限集合,当n=0时，叫空树
（3）非空树必须满足两个条件：①有且仅有一个特定的称为根的节点；②其余的节点可以分为m(m >=0)个互不相交的有限集合T1、T2、......、Tm，其中每一个集合又是一棵树，并称其为根的子树
2、相关概念
（1）节点的度：树中一个节点的孩子个数称为该节点的度，所有节点的度的最大值是树的度；eg：节点A的度：3；节点B的度：2；节点M的度：0；树的度：3
（2）分支节点：度大于0（有孩子）的节点称为分支节点；eg：分支节点：A B C D E H
（3）叶子结点：度为0（无孩子）的节点称为叶子结点；eg：叶子节点：K L F G M I J
（4）节点的层次（深度）：从上往下数，根节点为1层，依次往下加1；eg：E节点的层次：第3层
（5）树的高度（深度）：树中节点的最大层次；eg：树的高度：4
（6）若树中节点的各子树从左至右是有次序的，不能互换，则该树称为有序树，否则称为无序树
（7）双亲节点或父节点：若一个节点含有子节点，则这个节点就是其子节点的父节点；eg：节点M的父节点：H
（8）孩子节点或子节点：一个节点含有的子树的根节点就是该节点的子节点；eg：节点A的子节点：B C D
（9）兄弟节点：具有相同父节点的节点互称为兄弟节点；eg：B、C是兄弟节点
（10）森林：森林是m（m>= 0)棵互不相交的树的集合
（11）树去掉根节点就成为森林，森林加上根节点就是树
树的逻辑结构：树中任何节点都可以有0个或多个直接后继节点(子节点)，但最多只有一个直接前驱节点(父节点)，根节点没有前驱节点，叶子节点没有后继节点
2、二叉树
1、概念
二叉树Binary Tree是n个节点的有限集合，它或者是空集，或者是由一个根节点以及两颗互不相交、分别称为左子树和右子树的二叉树组成
2、特点
（1）二叉树与普通的有序树不同，二叉树严格区分左子和右子，即使只有一个子节点，也要区分左右
（2）二叉树的度数为2
3、性质
（1）二叉树的第k层上的节点最多有2^(k-1)个
（2）深度为k的二叉树，最多有2^k-1个节点
（3）在任意一颗二叉树中，叶子结点的数目比度数为2的节点数目多1
4、特殊的二叉树
（1）满二叉树：除叶子结点外，每个节点都有两个子节点
（2）完全二叉树：只有最下面两层可以有度数小于2的节点，且最下面一层的结点集中在最左边的若干位置上
满二叉树也是特殊的完全二叉树
3、二叉树的实现
逻辑结构：树形结构
存储结构有两种：顺序存储和链式存储
（1）顺序存储
二叉树的顺序存储，指的是使用顺序表（数组）存储二叉树。需要注意，顺序存储只适用于完全二叉树。换句话说，只有完全二叉树才可以用顺序表存储。因此，如果我们想要顺序存储普通二叉树，就需要将其提前转换成完全二叉树
这样会造成内存浪费，所以推荐使用链式存储
（2）链式存储
链式存储二叉树，从根结点开始，将各个结点以及其左右子的地址使用链表进行存储
（3）遍历
先序遍历：根 -> 左 -> 右
中序遍历：左 -> 根 -> 右
后序遍历：左 -> 右 -> 根
4、二叉树的操作
先序创建：ABC##D##E##
为什么C、D、E后面会有##呢？
因为把图中的每一个节点都可以看成根节点，例如：C是根节点，但没有左、右子树，所有后面要加上##，代表C后没有左、右子树
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>//定义二叉树的结构体类型
typedef char ele;
typedef struct BTree_Node {
ele val; //存放二叉树节点元素值
struct BTree_Node* left; //指向左子节点
struct BTree_Node* right; //指向右子节点
}BTN;//二叉树的初始化
//就是把树的所有节点存进去的过程
void init_BTree(BTN** btn);
//先序遍历：根-左-右
void pre_order(BTN* btn);
//中序遍历：左-根-右
void mid_order(BTN* btn);
//后序遍历：左-右-根
void nex_order(BTN* btn);int main() {
BTN* btn = NULL; //二叉树根节点指针
//二叉树的初始化
init_BTree(&btn);
//先序遍历
pre_order(btn);
printf("\n");
//中序遍历
mid_order(btn);
printf("\n");
//后序遍历
nex_order(btn);
return 0;
}//二叉树的初始化
//就是把树的所有节点存进去的过程
void init_BTree(BTN** btn) {
//先序创建
ele val = 0;
scanf(" %c", &val);
if (val == '#') { //空树
*btn = NULL;
}else {
//创建新节点
*btn = (BTN*)malloc(sizeof(BTN));
(*btn)->val = val;
init_BTree(&((*btn)->left)); //创建左子树
init_BTree(&((*btn)->right)); //创建右子树
}
}//先序遍历：根-左-右
void pre_order(BTN* btn) {
if (btn == NULL) {
return;
}
printf("%c ", btn->val); //根
pre_order(btn->left); //左子树
pre_order(btn->right); //右子树
}//中序遍历：左-根-右
void mid_order(BTN* btn) {
if (btn == NULL) {
return;
}
mid_order(btn->left); //左子树
printf("%c ", btn->val); //根
mid_order(btn->right); //右子树
}//后序遍历：左-右-根
void nex_order(BTN* btn) {
if (btn == NULL) {
return;
}
nex_order(btn->left); //左子树
nex_order(btn->right); //右子树
printf("%c ", btn->val); //根
}