性质1 在二叉树的第i层至多有(2^{i-1})个结点（i$geq$1）
性质2 深度为K的二叉树至多有(2^k-1)个节点 (k$geq$1）
二叉树的遍历
前序遍历
中序遍历
后序遍历
线索二叉树
一棵结点数目为n的二叉树，采用二叉链表的形式存储。对于每个结点均有指向左右孩子的两个指针域，而结点为n的二叉树一共有n-1条有效分支路径。那么，则二叉链表中存在2n-(n-1)=n+1个空指针域。那么，这些空指针造成了空间浪费。
线索化
若结点的左子树为空，则该结点的左孩子指针指向其前驱结点。
若结点的右子树为空，则该结点的右孩子指针指向其后继结点。
线索二叉树
线索化带来新问题
ltag为0时，指向左孩子，为1时指向前驱
rtag为0时，指向右孩子，为1时指向后继
添加ltag和rtag属性后的结点结构如下：
添加标志线索二叉树结点
线索二叉树转变二叉树
添加标志位的线索二叉树
二叉排序树
构造一个有n个结点的二叉排序树，在最坏的情况下，深度不超过n。
现有序列：61 87 59 47 35 73 51 98 37 93
构造过程如下：
1）索引 i = 0，A[i] = 61，结点61作为根结点，如图2.1：
2）索引 i = 1，A[1] = 87, 87 > 61，且结点61右孩子为空，故81为61结点的右孩子，如图2.2：
3）索引 i = 2，A[i] = 59，59 <
61，且结点61左孩子为空，故59为61结点的左孩子，如图2.3：
4）索引 i = 3，A[3] = 47，47 < 59，且结点59左孩子为空，故47为59结点的左孩子，如图2.4：
5）索引 i = 4，A[4] = 35，35 < 47，且结点47左孩子为空，故35为47结点的左孩子，如图2.5：
采用同样规则遍历整个数组得到如图2.6所示的一棵排序二叉树。
