本节以二叉树为例学习一种比较复杂但是常见的数据结构----树,包括各种类型的二叉树及性质,如完全二叉树,平衡二叉树及二叉搜索树.

树的基本结构:

树是一种数据结构,他是由n个有限节点组成的一个具有层次关系的集合.二叉树则是每个节点最多有两个子树的树结构.二叉树一般具有以下性质.

1.二叉树的第k层上的节点数目最多为2的k-1次方.

2.深度为h的二叉树至多有2的h-1个节点.

3.包含n个节点的二叉树的高度至少为log2(n+1)

4.在任意一棵二叉树中,若叶子节点的个数为n0,度为2的节点数为n2,则n0=n2+1

下面介绍几种常见的二叉树:

满二叉树:如果一个二叉树的节点要么是叶子节点,要么他有两个子节点,那么这样的树就是满二叉树.

完全二叉树:如果一棵具有n个节点的深度为k的二叉树,他的每一个节点都与深度为k的满二叉树中编号为1~n的节点一一对应,那么这棵二叉树称为完全二叉树.

平衡二叉树:一棵空树或它的左右两个子树的高度差的绝对值不超过1,且左右两个子树都是一棵平衡二叉树

二叉搜素树:若它的左子树不空,则左子树上所有节点的值均小于它的根节点的值;若它的右子树不空,则右子树上所有节点的值均大于他的根节点的值.