总结&＃xff1a;

树&＃xff1a;树是一种数据结构&＃xff0c;它是由n&＃xff08;n>&＃61;1&＃xff09;个有限节点组成一个具有层次关系的集合。
二叉树&＃xff1a;可以是空集&＃xff1b;根可以有空的左子树或右子树&＃xff1b;或者左、右子树皆为空。
1. 完整二叉树&＃xff1a;2{h} –1节点&＃xff0c;h是高度
2. 满二叉树&＃xff08;包括完整二叉树&＃xff09;&＃xff1a;两层结点的度可以小于2&＃xff0c;并且最下一层的叶结点集中在靠左的若干位置上
3. 二叉查找树&＃xff1a;左子树节点值<它的根节点值<右子树节点值&＃xff08;如果节点不为空&＃xff09;。

---

二叉查找树&＃xff08;http://www.cnblogs.com/skywang12345/p/3576328.html&＃xff09;

树定义

把它叫做“树”是因为它看起来像一棵倒挂的树&＃xff0c;也就是说它是根朝上&＃xff0c;而叶朝下的。它具有以下的特点&＃xff1a;
(01) 每个节点有零个或多个子节点&＃xff1b;
(02) 没有父节点的节点称为根节点&＃xff1b;
(03) 每一个非根节点有且只有一个父节点&＃xff1b;
(04) 除了根节点外&＃xff0c;每个子节点可以分为多个不相交的子树。

树 术语

若一个结点有子树&＃xff0c;那么该结点称为子树根的”双亲”&＃xff0c;子树的根是该结点的”孩子”。有相同双亲的结点互为”兄弟”。一个结点的所有子树上的任何结点都是该结点的后裔。从根结点到某个结点的路径上的所有结点都是该结点的祖先。

结点的度&＃xff1a;结点拥有的子树的数目。
叶子&＃xff1a;度为零的结点。
分支结点&＃xff1a;度不为零的结点。
树的度&＃xff1a;树中结点的最大的度。
层次&＃xff1a;根结点的层次为1&＃xff0c;其余结点的层次等于该结点的双亲结点的层次加1。
树的高度&＃xff1a;树中结点的最大层次。
无序树&＃xff1a;如果树中结点的各子树之间的次序是不重要的&＃xff0c;可以交换位置。
有序树&＃xff1a;如果树中结点的各子树之间的次序是重要的, 不可以交换位置。
森林&＃xff1a;0个或多个不相交的树组成。对森林加上一个根&＃xff0c;森林即成为树&＃xff1b;删去根&＃xff0c;树即成为森林。

二叉树的定义

二叉树是每个节点最多有两个子树的树结构。它有五种基本形态&＃xff1a;二叉树可以是空集&＃xff1b;根可以有空的左子树或右子树&＃xff1b;或者左、右子树皆为空。

二叉树的性质

性质1&＃xff1a;二叉树第i层上的结点数目最多为 2{i-1} (i≥1)。
性质2&＃xff1a;深度为k的二叉树至多有2{k}-1个结点(k≥1)。
性质3&＃xff1a;包含n个结点的二叉树的高度至少为log2 (n&＃43;1)。
性质4&＃xff1a;在任意一棵二叉树中&＃xff0c;若终端结点的个数为n0&＃xff0c;度为2的结点数为n2&＃xff0c;则n0&＃61;n2&＃43;1。

满二叉树&＃xff0c;完全二叉树&＃xff0c;二叉查找树

满二叉树

定义&＃xff1a;高度为h&＃xff0c;并且由2{h} –1个结点的二叉树&＃xff0c;被称为满二叉树。

完全二叉树

定义&＃xff1a;一棵二叉树中&＃xff0c;只有最下面两层结点的度可以小于2&＃xff0c;并且最下一层的叶结点集中在靠左的若干位置上。这样的二叉树称为完全二叉树。
特点&＃xff1a;叶子结点只能出现在最下层和次下层&＃xff0c;且最下层的叶子结点集中在树的左部。显然&＃xff0c;一棵满二叉树必定是一棵完全二叉树&＃xff0c;而完全二叉树未必是满二叉树。

二叉查找树

定义&＃xff1a;二叉查找树(Binary Search Tree)&＃xff0c;又被称为二叉搜索树。
(01) 若任意节点的左子树不空&＃xff0c;则左子树上所有结点的值均小于它的根结点的值&＃xff1b;
(02) 任意节点的右子树不空&＃xff0c;则右子树上所有结点的值均大于它的根结点的值&＃xff1b;
(03) 任意节点的左、右子树也分别为二叉查找树。
(04) 没有键值相等的节点&＃xff08;no duplicate nodes&＃xff09;。

二叉查找树

(01) 前序遍历结果&＃xff1a; 3 1 2 5 4 6
(02) 中序遍历结果&＃xff1a; 1 2 3 4 5 6
(03) 后序遍历结果&＃xff1a; 2 1 4 6 5 3

(01) 新建”二叉查找树”root

(02) 依次插入1,5,4,3,2,6

前序遍历结果: 1 5 4 3 2 6
中序遍历结果: 1 2 3 4 5 6
后序遍历结果: 2 3 4 6 5 1
最小值是1&＃xff0c;而最大值是6。

(03) 删除节点 3