图论
图论是数学的一个分支。它以图为研究对象。图论中的图是由若干给定的点及连接两点的线所构成的图形，这种图形通常用来描述某些事物之间的某种特定关系，用点代表事物，用连接两点的线表示相应两个事物间具有这种关系。
树
树是一种数据结构，它是由n(n≥1)个有限节点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。它具有以下的特点：
其中每个元素称为结点(node),每个节点有零个或多个子节点；没有父节点的节点称为根节点；每一个非根节点有且只有一个父节点；除了根节点外，每个子节点可以分为多个不相交的子树。
如图是一棵树：
一棵树中至少有1个结点，即根结点。
一个结点的子树个数，称为这个结点的度（如结点1的度为3，结点3的度为0）。
度为0的结点称为叶结点（leaf）（如结点3、5、6、8、9）。
树中各结点的度的最大值称为这棵树的度（此树的度为3）。
上端结点为下端结点的父结点，称同一个父结点的多个子结点为兄弟结点（如结点1是结点2、3、4的父结点，结点 2、3、4是结点1的子结点，它们又是兄弟结点）。
遍历
树结构解决问题时，按照某种次序获得树中全部结点的信息，这种操作叫作树的遍历。
先序(根)遍历
先访问根结点，再从左到右按照先序思想遍历各棵子树（如，上图先序遍历的结果为125634789）。
后序（根）遍历
先从左到右遍历各棵子树，再访问根结点（如，上图后序遍历的结果为562389741）。
层次遍历
按层次从小到大逐个访问，同一层次按照从左到右的次序（如，上图层次遍历的结果为123456789）。
叶结点遍历
即从左到右遍历所有叶节点（如，上图叶节点遍历的结果为56389）。
二叉树
二叉树是一种特殊的树型结构，它是度数为2的树，即二叉树的每个结点最多有两个子结点。
每个结点的子结点分别称为左儿子、右儿子。
五种基本形态
性质
性质一
二叉树的第i层最多有2i-1个结点（i>=1）（可用二进制性质解释。）。
性质二
深度为k的二叉树至多有2k–1个结点（k>=1）。
性质三
任意一棵二叉树，如果其叶结点数为n0，度为2的结点数为n2，则一定满足：n0=n2+1。
性质四
有n个结点的完全二叉树的深度为floor(log2n)+1。
性质五
一棵n个结点的完全二叉树，对任一个结点(编号为i)，有：如果i=1，则结点i为根，无父结点；如果i>1,则其父结点编号为floor（i/2），如果i为父节点编号，那么2i是左孩子，2i+1是右孩子。
图A-满二叉树
图B-完全二叉树
编号示意图
遍历
二叉树的遍历是指按一定的规律和次序访问树中的各个结点。
遍历一般按照从左到右的顺序，共有3种遍历方法，先（根）序遍历，中（根）序遍历，后（根）序遍历。
先序遍历
若二叉树为空，则空操作，否则：
访问根结点、先序遍历左子树、先序遍历右子树
void preorder(tree bt)//先序递归算法 { if(bt) { cout << bt->data; preorder(bt->lchild); preorder(bt->rchild); } }
先序遍历此图结果为：124753689
中序遍历
若二叉树为空，则空操作，否则：
中序遍历左子树、访问根结点、中序遍历右子树
void inorder(tree bt)//中序遍历递归算法 { if(bt) { inorder(bt->lchild); cout << bt->data; inorder(bt->rchild); } }
中序遍历上图结果为：742513869
后序遍历
若二叉树为空，则空操作，否则：
后序遍历左子树、后序遍历右子树、访问根结点
void postorder(tree bt)//后序递归算法 { if(bt) { postorder(bt->lchild); postorder(bt->rchild); cout << bt->data; } }
后序遍历上图结果为：745289631
已知先序序列和中序序列可唯一确定一棵二叉树；
已知中序序列和后序序列可唯一确定一棵二叉树；
已知先序序列和后序序列不可唯一确定一棵二叉树；
二叉树操作（建树、删除、输出）
普通树转二叉树
由于二叉树是有序的，而且操作和应用更广泛，所以在实际使用时，我们经常把普通树转换成二叉树进行操作。
通用法则：“左孩子，右兄弟”
建树
删除树
插入一个结点到排序二叉树中
在排序二叉树中查找一个数
相关题目
扩展二叉树
由于先序、中序和后序序列中的任一个都不能唯一确定一棵二叉树，所以对二叉树做如下处理，将二叉树的空结点用“.”补齐，称为原二叉树的扩展二叉树，扩展二叉树的先序和后序序列能唯一确定其二叉树。
现给出扩展二叉树的先序序列，要求输出其中序和后序序列。
输入样例：
ABD..EF..G..C..
输出样例：
DBFEGAC
DFGEBCA
二叉树的建立和输出
以二叉链表作存储结构，建立一棵二叉树，并输出该二叉树的先序、中序、后序遍历序列、高度和结点总数。
输入样例：
12##3##
//#为空
输出样例：
123
//先序排列
213
//中序排列
231
//后序排列
2
//高度
3
//结点总数
因为本蒟蒻不太会用指针，所以自己写了一个不带指针的，代码很丑，见谅QwQ
/1 
