数据结构：树和二叉树

第一节：二叉树的定义与基本操作

定义：我们把满足以下两个条件的树型结构叫做二叉树(Binary Tree)：
(1)每个结点的度都不大于2；
(2)每个结点的孩子结点次序不能任意颠倒。

由定义得出：二叉树的每个结点只能含有0、1或2个孩子，且有左右之分。

(1)二叉树的五种基本形态：

(2)二叉树性质

性质1 二叉树第i层上的结点数目最多为2^i-1(i≥1)。

性质2 深度为k的二叉树至多有2^k-1个结点(k≥1)。

性质3 在任意二叉树中，若终端结点的个数为n_{0，度为2的结点数为n2，则no=n2+1。}

_{性质4 具有n个结点的完全二叉树的深度为[log n]+1}

(3)

第二节：