二叉树、树及有序树的区别 从定义上看，二叉树既不是只有两个子 树的树，也不是最多只有两个子树的树。 主要差别在于二叉树的子树有左右之分。 在有序树中，虽然一个结点的孩子之间 是有左右次序的，但若该结点只有一个孩 子时，就无须区分其左右次序。而在二叉 树中，即使是一个孩子也有左右之分
二叉树、树及有序树的区别 从定义上看，二叉树既不是只有两个子 树的树，也不是最多只有两个子树的树。 主要差别在于二叉树的子树有左右之分。 在有序树中，虽然一个结点的孩子之间 是有左右次序的，但若该结点只有一个孩 子时，就无须区分其左右次序。而在二叉 树中，即使是一个孩子也有左右之分
二叉树的五种基本形态： 空树 只含根结点 N 左右子 树均不 右子树为空树 左子树为空树 为空树 N N N L R L R
二叉树的五种基本形态： N 空树 只含根结点 N N N L R R 右子树为空树 L 左子树为空树 左右子 树均不 为空树
6.2.2二叉树的性质 性质1： 在二叉树的第i层上至多有2-1个 结点。 (i≥1) 用归纳法证明 归纳基：i=1层时，只有一个根结点： 2-1=20=1; 归纳假设：假设对所有的j,1≤j<i,命题成立； 归纳证明：二叉树上每个结点至多有两棵子树， 则第i层的结点数=22×2=21
性质 1 ： 在二叉树的第 i 层上至多有2 i-1 个 结点。 (i≥1) 用归纳法证明： 归纳基： 归纳假设： 归纳证明： i = 1 层时，只有一个根结点： 2 i-1 = 2 0 = 1； 假设对所有的 j，1≤ j i，命题成立； 二叉树上每个结点至多有两棵子树， 则第 i 层的结点数 = 2 i-2 2 = 2 i-1 。 6.2.2 二叉树的性质
性质2： 深度为k的二叉树上至多含2k-1个 结点（k≥1)。 证明： 基于上一条性质，深度为k的二叉 树上的结点数至多为 20+21+..···.+2k-1=2k-1
性质 2 ： 深度为 k 的二叉树上至多含 2 k -1 个 结点（k≥1）。 证明： 基于上一条性质，深度为 k 的二叉 树上的结点数至多为 2 0+21+ +2k-1 = 2k -1
性质3： 对任何一棵二叉树，若它含有o个叶 子结点、2个度为2的结点，则必存在 关系式：no=n2+l。 证明： 设二叉树上结点总数n=no+n1+n2 又二叉树上分支总数b=n+2n2 而b=n-l=no+n1+n2-1 由此，no=n2+1
性质 3 ： 对任何一棵二叉树，若它含有n0 个叶 子结点、n2 个度为 2 的结点，则必存在 关系式：n0 = n2+1。 证明： 设 二叉树上结点总数 n = n0 + n1 + n2 又 二叉树上分支总数 b = n1+2n2 而 b = n-1 = n0 + n1 + n2 - 1 由此， n0 = n2 + 1