树与二叉树原理与心得
一、树、二叉树性质
一般这种题会问你结点数、高度、空指针域等问题
需牢记：
1.二叉树：n0 + n1 + n2 = n1 + 2*n2 + 1 = n
这个方程最重要！！！可以解决度、边、结点数直接关系的问题。题中出现度、结点直接用此公式就对了
2.二叉树：0 = 2 + 1，即叶节点数 = 度为2的结点数 + 1（由1的前两个组成方程推导出来）
3.二叉树：2n个孩子指针，只有n-1个结点可以作为孩子被指，故有2n-(n-1)=n+1个空指针（空链域）
4.完全/满二叉树：一行的起始结点号 = 该行可容纳的结点数 = 2^(n-1)；一行的末尾结点号 = 整棵树的结点数 = 2^n-1
5.完全二叉树：高度公式里上外下（+1在对数里面就向上取整，外面就向下取整）
6.完全二叉树的叶节点只有可能出现在倒数两行，一个完全二叉树的叶节点要么处于上面那行，要么出现在下面那行
二、二叉树的遍历
前序遍历，根左右，对于一个结点而言，先访问它，再访问其左子树，再访问其右子树。最后被访问到的是该结点右子树的最右下的叶节点。最先访问到的是结点本身。
中序遍历，左根右，对于一个结点而言，先访问其左子树，再访问它，再访问其右子树。最后被访问到的是该结点右子树的最右下转折处的结点。最先访问到的是其左子树最左下转折处的结点。
后序遍历，左右根，对于一个结点而言，先访问其左子树，再访问其右子树，再访问它。最后被访问到的是结点本身。最先访问到的是该结点左子树最左下的叶节点。
层次遍历，利用队列，从根节点进入队列开始，每次出一个，并将其孩子添加到队列中知道队列为空。
四个遍历一定要烂熟于心。
三、创造线索二叉树
介绍：线索二叉树的创造依赖于前、中、后遍历序列。结点的左孩子为空，则设置左孩子指针为其前驱的位置并置ltag = 1；结点的右孩子为空，则设置右孩子指针为其后继的位置并置rtag = 1。ltag与rtag表明了该结点的指针是否为线索。
将一棵二叉树改为线索二叉树：需要对二叉树遍历，而遍历分为先序中序与后序。遍历的种类决定了线索二叉树的种类。
先序：先设置当前结点的前驱（空左孩子）再设置pre的后继（空右孩子），再递归到左孩子，最后递归到右孩子。
中序：先递归到左孩子，再设置当前结点的前驱（空左孩子）再设置pre的后继（空右孩子），最后递归到右孩子。
后序：先递归到左孩子，再递归到右孩子，最后设置当前结点的前驱（空左孩子）再设置pre的后继（空右孩子）。
特别注意：先序遍历创造线索二叉树中，递归到左孩子小心此时的左孩子指针可能不指向其左孩子而指向其前驱。
四、遍历线索二叉树
方法：线索二叉树的遍历需由该线索二叉树的种类决定。但思想是一致的：多米诺骨牌——找到序列的首结点，从序列的首结点出发，想尽办法找到下一个结点。
先序：
找到序列首结点：即一个序列的根节点
找到下一个结点的办法：后继线索存在则用之。否则（右孩子存在），若左孩子不存 在，则下一个结点为右孩子；若左孩子存在，则下一个结点为左孩子。
中序：
找到序列首结点：最左下转折处的结点
找到下一个结点的办法：后继线索存在则用之。否则（右孩子存在），找到右子树序
列首结点。
后序：
找到序列首结点：最左下的叶节点
找到下一个结点的办法：后继线索存在则用之；否则，若其为左孩子，找到其双亲右子树的最左下的结点