第五章 树和二叉树

第五章 树和二叉树 一、树

树的定义：树是n(n>=0)个结点的有限集，或为空树，或为非空树。

结点的度：结点拥有的子树数

树的度：树内各结点度的最大值

二、二叉树 1、二叉树的定义

树中节点的度不大于2的有序树。（有序树的最左边的子树的根称为第一个孩子，最右边的称为最后一个孩子）

 2、二叉树的性质

2.1二叉树的第i层最多有2^（i-1）个结点

2.2二叉树最多有2^k-1个结点

2.3二叉树的 叶子结点数=度为2的节点数+1

2.4具有n个结点的完全二叉树的深度为（log 以2为底 n的对数 向下取余）+1

2.5对于完全二叉树，编号为i的结点，其左孩子编号为2i,右孩子编号为2i+1,双亲编号为i/2

3、满二叉树与完全二叉树

满二叉树：深度为k且含有2^k-1个结点

完全二叉树：  1、叶子结点只能在层次最大的两层出现

                        2、左分支的子孙层次大于等于右分支的子孙层次