1.二叉树的性质
1.具有 n 个节点的二叉树第 n 层最多2的 n-1 次方个节点
2.具有 n 个节点的二叉树最多有 2 的 n 次方减 1 个节点
3.度为 0 的节点数等于度为 2 的节点数加 1
节点度的关系 n=n0+n1+n2
边的条数就是 n-1 ,也就是节点的关系的个数 另外一方面就是从父亲的方面来看就是利用度来计算 n0*0+n1*1+n2*2
也就是从不同的角度来理解这个东西获得一个等式从而得到的
2.两个小概念：
满二叉树：所有的节点排满了
完全二叉树:按顺序从左向右排放可以不满
3.线索化
1.中序线索化
rtag=0 右子树最左边的节点
rtag=1 rchild 指向
ltag=0 左子树的最右边节点
ltag=1 lchild 指向
4.树
任何一棵树我们如果使用孩子兄弟表示法的话 我们自然就会把这个树转化成一个二叉树
当然也可以使用双亲表示法，就是用map 然后记录双亲的位置
也可以使用孩子表示法就是使用一个索引链表
也可以把上面两个方法结合起来就是使用双亲孩子表示法
5.层序遍历
就是先把根节点放在队列里面，然后只要这个队列不空的话，就访问这个节点然后出队，然后分别把这个节点的左右节点分别入队列
6.中序和先序遍历的非递归的算法
使用一个栈，中序的话就是第二次经过这个节点的时候我们访问，先序就是第一次经过这个节点的时候去访问这个节点
因为一般来说我们知道他会进过两次，但是什么时候第三次经过我们并不知道。我们可以每个节点设置一个 mark 如果是第三次访问的时候我们就访问