(创作不易，感谢有你，你的支持，就是我前行的最大动力，如果看完对你有帮助，请留下您的足迹）
目录
初识树：
1.树是n个结点的有限集
2.结点个数为零的树称为空树 （n=0）
3.任意一颗非空树中（n>0）
有且仅有一个特定的称为根的结点
非根的结点可分为互不相交的有限集，每个集合本身又是一棵树，这些树称为根的子树
“发散思维”主题的思维导图 —— 树
主题和子主题 —— 结点
主题 —— 根（根结点）
子主题“抽象”—— 叶（叶结点）
子主题“形”—— 内部结点 （分支结点）
结点的层次：主题“发散思维”为第一层，子主题“跳跃、想象、形”为第二层
结点一共有三层，所以树的深度为3
结点的度数：主题“发散思维”有五个子主题，所以结点度数为5
结点的最大度数为5，所以树的度为5
初识森林：
森林——删除根节点后不相交的树的集合
有序树——结点各子树从左至右有序，不能互换（左为第一）
无序树——结点各子树可以交换位置
初识二叉树:
二叉树（Binary Tree）是n(n≥0)个结点所构成的集合，它或为空树(n=0);或为非空树，对
于非空树𝑻 ：
有且仅有一个称之为根的结点
除根以外的其余结点分为两个互不相交的子集𝑻 1 和𝑻 2 ，分别称为𝑻的左子树和右子 树，且𝑻 1 和𝑻 2 本身又都是二叉树
二叉树与树的区别:
二叉树的几种形态:
满二叉树和完全二叉树：
满二叉树：深度为k且含有2的k次方-1个结点的二叉树
特点：
1.每一层上的结点数都是最大结点数
2.每一层i的结点数都具有最大值2的（i-1）次方
完全二叉树：深度为k的，有n个结点的二叉树,当且仅当其每一个结点都与深度为k的满二叉树中（自上而下从左往右）编号从1至n的结点一一对应。
特点：
1.叶子结点只可能在层次最大的两层出现
2.对任一结点，若其右分支下的子孙的最大层次为x, ,则其左分支下的子孙的最大层 次必为x或x+1
3.最下层的叶结点一定集中在左部连续位置
4.倒数第二层若有叶结点，一直都在右部连续位置
5.如果结点度为1，则该结点只有左子树（即不存在只有右子树的情况）
6.同样结点数的二叉树，完全二叉树的深度最小
二叉树的性质：
性质1：在二叉树的第 𝒊 层上至多有2的(i-1)次方个结点
性质2：深度为 𝒊 的二叉树至多有2的i次方-1个结点。
性质3：对于任何一棵二叉树，若2度的结点数有x个。则叶子数y必定为x+1（y=x+1）
性质4：具有𝑛个结点的完全二叉树的深度必为[log2n]＋1。（[ ]表示向下取整）（2为下标，但是打不出来o(╥﹏╥)o））
性质5：对完全二叉树，若从上至下、从左至右编号，则编号为𝒊的结点，其左孩子编号必为2𝒊 ，其右孩子编号必为2𝒊＋1；其双亲的编号必为[𝒊/2]
二叉树的顺序储存结构：
特点：
1 、结点间关系蕴含在其存储位置中
2、 浪费空间，适用于存满二叉树和完全二叉树
初始化二叉树：
/** 一维数组能够存放的最大结点数 */ #define MAX_SIZE 1024 /** 定义顺序树类型 */ typedef char SeqTree[MAX_SIZE]; /** 初始化空二叉树 */ void InitSeqTree(SeqTree tree) { //将字符数组中的每个元素都设置为空字符 for (int i = 0; i < MAX_SIZE; i++) { tree[i] = '\0'; } }
创建二叉树：
/** 创建完全二叉树，i为数组中的下标 */ void CreateSeqTree(SeqTree tree, int i) { char ch; ch = getchar(); if (ch == '^') { //输入^符号表示结束当前结点的输入 tree[i] = '\0'; return; } tree[i] = ch; //某个结点输入完毕后，还需要让用户输入左孩子和右孩子 printf("左孩子结点："); CreateSeqTree(tree, 2 * i + 1); //递归调用 printf("右孩子结点："); CreateSeqTree(tree, 2 * (i + 1)); }
获取数的相关数据：
/** 获取树的根结点元素 */ char GetSeqTreeRoot(SeqTree tree) { return tree[0]; } /** 获取树的结点总数 */ int GetSeqTreeLength(SeqTree tree) { int len = 0; for (int i = 0; i < MAX_SIZE; i++) { if (tree[i] == '\0') { continue; } len++; } return len; } /** 获取树的深度 */ int GetSeqTreeDepth(SeqTree tree) { //性质2：深度为k的二叉树最多有2^k-1个结点 int depth = 0; //深度 int len = GetSeqTreeLength(tree); while ((int)pow(2, depth) - 1 < len) { depth++; } return depth; }
二叉树的链式储存结构： 
//二叉树的二叉链表存储表示 typedef struct BiNode { /*结点数据域*/ Element data; /*左孩子指针*/ struct BiNode* lchild； /*右孩子指针*/ struct BiNode* rchild; }BiTNode, * BiTree；
注意：
在含有n 个结点的二叉链表中有 n+1 个空链域，利用这些空链域可以存储其他有用信息，
从而得到另一种链式存储结构 —— 线索链表
初始化二叉树：
/** 数据元素 */ typedef struct { int id; char name[NAME_SIZE]; }ElementType; /** 树结点 */ typedef struct treeNode { ElementType data; //树结点的数据域 struct treeNode* left; //左子树 struct treeNode* right; //右子树 }TreeNode; /** 二叉链表 */ typedef struct { TreeNode* root; //二叉链的根结点 int length; //二叉链表结点的总数 int depth; //二叉链表的深度 int diameter; //直径 - 从叶结点到叶结点的最长路径 }BinaryTree; /** 初始化空二叉树 */ void InitBinaryTree(BinaryTree* tree) { tree->root = NULL; tree->depth = 0; tree->diameter = 0; tree->length = 0; }
创建二叉树：
/** 用来实现结点id的自增长 */ static int id = 0; /** 构造二叉树 - 外部需要事先对结点分配内存 */ int CreateBinaryTree(TreeNode* root) { //根结点如果为空，就退出创建过程 if (!root) return 0; char inputName[NAME_SIZE]; //用户输入的结点名 gets_s(inputName); //用户输入回车表示结束当前子树的创建 if (strcmp(inputName, "\0") == 0) return 0; //创建当前结点 root->data.id = ++id; strcpy(root->data.name, inputName); //为输入左右结点做准备 - 为左右结点指针分配内存 root->left = (TreeNode*)malloc(sizeof(TreeNode)); root->right = (TreeNode*)malloc(sizeof(TreeNode)); //分别递归创建左子树和右子树 printf("左结点："); if (CreateBinaryTree(root->left) == 0) { //不再创建这个结点则销毁结点刚分配的内存 free(root->left); root->left = NULL; } printf("右结点："); if (CreateBinaryTree(root->right) == 0) { free(root->right); root->right = NULL; } return 1; }
