树的特点树是包含n(n>1)个结点,n-1条边的有穷集,其中:(1)每个元素称为结点;(2)有一个特定的结点称为根结点或者树根;(3)除根结点之外的其余数据元素组成的集合称为子树。
二叉树1. 每个结点有零或者多个子结点;
2. 没有父结点的结点称为根;
3. 非根结点只有一个父结点;
4. 没有子结点的结点称为叶子结点;
满二叉树每个结点最多有两个子结点。
完全二叉树1. 叶子结点都在最后一层;
2. 除叶子结点外,每个结点都拥有两个子结点;
二叉查找树(BST)结点的排列顺序为:从左到有,从上到下。除最后一层外,其余各层组成的树必须是满二叉树;并且最后一层结点的排列顺序为从左到有连续的排列。
1. 特殊的完全二叉树;
2. 左子树(存在时)上的结点值都小于父结点的值,右子树(存在时)上的结点值都大于父结点的值。