⼆叉树基本概念（满⼆叉树、完全⼆叉树，满⼆叉树，⼆叉树
的遍历）
1. ⼆叉树
⼆叉树是每个节点最多有两个⼦树的树结构。它有五种基本形态：⼆叉树可以是空集；根可以有空的左⼦树或右⼦树；或者左、右⼦树皆为空。
性质1：⼆叉树第i层上的结点数⽬最多为 2{i-1} (i≥1)。
性质2：深度为k的⼆叉树⾄多有2{k}-1个结点(k≥1)。
性质3：包含n个结点的⼆叉树的⾼度⾄少为log2 (n+1)。
性质4：在任意⼀棵⼆叉树中，若终端结点的个数为n0，度为2的结点数为n2，则n0=n2+1。
2. 满⼆叉树，完全⼆叉树和⼆叉查树（ADT）
2.1 满⼆叉树
定义：⾼度为h，并且由2{h} –1个结点的⼆叉树，被称为满⼆叉树。二叉树的基本性质
2.2 完全⼆叉树
定义：⼀棵⼆叉树中，只有最下⾯两层结点的度可以⼩于2，并且最下⼀层的叶结点集中在靠左的若⼲位置上。这样的⼆叉树称为完全⼆叉树。
考试点：完全⼆叉树如果有N个节点，那么叶⼦节点M=(N+1)/2
特点：叶⼦结点只能出现在最下层和次下层，且最下层的叶⼦结点集中在树的左部。显然，⼀棵满⼆叉树必定是⼀棵完全⼆叉树，⽽完全⼆叉树未必是满⼆叉树。
2.3 ⼆叉查树
定义：⼆叉查树(Binary Search Tree)，⼜被称为⼆叉搜索树。设x为⼆叉查树中的⼀个结点，x节点包含关键字key，节点x的key值记为key[x]。如果y是x的左⼦树中的⼀个结点，则key[y] <= key[x]；如果y是x的右⼦树的⼀个结点，则key[y] >= key[x]。
在⼆叉查树中：
(01) 若任意节点的左⼦树不空，则左⼦树上所有结点的值均⼩于它的根结点的值；
(02) 任意节点的右⼦树不空，则右⼦树上所有结点的值均⼤于它的根结点的值；
(03) 任意节点的左、右⼦树也分别为⼆叉查树。
(04) 没有键值相等的节点（no duplicate nodes）。
3. ⼆叉树的遍历
⼆叉树的遍历有前序遍历、中序遍历、后序遍历3种⽅式。
以下是三种遍历的顺序，前提条件都是⼆叉树⾮空。
3.1 前序遍历
(01) 访问根结点；
(02) 先序遍历左⼦树；
(03) 先序遍历右⼦树。
3.2 中序遍历
(01) 中序遍历左⼦树；
(02) 访问根结点；
(03) 中序遍历右⼦树。
3.3 后序遍历
(01) 后序遍历左⼦树；
(02) 后序遍历右⼦树；
(03) 访问根结点。
未完待续（改天⽤python写⼀下相应的代码）

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。