二叉树

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 如果是第三次访问的时候我们就访问