数据结构⼆叉树的⼀些性质及证明、树的路径长度、结点的路
径长度
树的介绍
1. 树的定义
树是⼀种数据结构，它是由n（n>=1）个有限节点组成⼀个具有层次关系的集合。
把它叫做“树”是因为它看起来像⼀棵倒挂的树，也就是说它是根朝上，⽽叶朝下的。它具有以下的特点：
(01) 每个节点有零个或多个⼦节点；
(02) 没有⽗节点的节点称为根节点；
(03) 每⼀个⾮根节点有且只有⼀个⽗节点；
(04) 除了根节点外，每个⼦节点可以分为多个不相交的⼦树。
2. 树的基本术语
若⼀个结点有⼦树，那么该结点称为⼦树根的"双亲"，⼦树的根是该结点的"孩⼦"。有相同双亲的结点互为"兄弟"。⼀个结点的所有⼦树上的任何结点都是该结点的后裔。从根结点到某个结点的路径上的所有结点都是该结点的祖先。
结点的度：结点拥有的⼦树的数⽬。
叶⼦：度为零的结点。
分⽀结点：度不为零的结点。
树的度：树中结点的最⼤的度。
层次：根结点的层次为1，其余结点的层次等于该结点的双亲结点的层次加1。
树的⾼度：树中结点的最⼤层次。
⽆序树：如果树中结点的各⼦树之间的次序是不重要的，可以交换位置。
有序树：如果树中结点的各⼦树之间的次序是重要的, 不可以交换位置。
森林：0个或多个不相交的树组成。对森林加上⼀个根，森林即成为树；删去根，树即成为森林。
⼆叉树的介绍
1. ⼆叉树的定义
⼆叉树是每个节点最多有两个⼦树的树结构。它有五种基本形态：⼆叉树可以是空集；根可以有空的左⼦树或右⼦树；或者左、右⼦树皆为空。
2. ⼆叉树的性质
⼆叉树有以下⼏个性质：TODO(上标和下标)
性质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.1 性质1：⼆叉树第i层上的结点数⽬最多为 2{i-1} (i≥1)
证明：下⾯⽤"数学归纳法"进⾏证明。
(01) 当i=1时，第i层的节点数⽬为2{i-1}=2{0}=1。因为第1层上只有⼀个根结点，所以命题成⽴。
(02) 假设当i>1，第i层的节点数⽬为2{i-1}。这个是根据(01)推断出来的！
下⾯根据这个假设，推断出"第(i+1)层的节点数⽬为2{i}"即可。
由于⼆叉树的每个结点⾄多有两个孩⼦，故"第(i+1)层上的结点数⽬" 最多是 "第i层的结点数⽬的2倍"。即，第(i+1)层上的结点数⽬最⼤值=2×2{i-1}=2{i}。
故假设成⽴，原命题得证！
2.2 性质2：深度为k的⼆叉树⾄多有2{k}-1个结点(k≥1)
证明：在具有相同深度的⼆叉树中，当每⼀层都含有最⼤结点数时，其树中结点数最多。利⽤"性质1"可知，深度为k的⼆叉树的结点数⾄多为：
20+21+…+2k-1=2k-1
故原命题得证！
2.3 性质3：包含n个结点的⼆叉树的⾼度⾄少为log2 (n+1)
证明：根据"性质2"可知，⾼度为h的⼆叉树最多有2{h}–1个结点。反之，对于包含n个节点的⼆叉树的⾼度⾄少为log2(n+1)。
2.4 性质4：在任意⼀棵⼆叉树中，若终端结点的个数为n0，度为2的结点数为n2，则n0=n2+1
证明：因为⼆叉树中所有结点的度数均不⼤于2，所以结点总数(记为n)="0度结点数(n0)" + "1度结点数(n1)" + "2度结点数(n2)"。由此，得到等式⼀。
(等式⼀) n=n0+n1+n2
      另⼀⽅⾯，0度结点没有孩⼦，1度结点有⼀个孩⼦，2度结点有两个孩⼦，故⼆叉树中孩⼦结点总数是：n1+2n2。此外，只有根不是任何结点的孩⼦。故⼆叉树中的结点总数⼜可表⽰为等式⼆。
(等式⼆) n=n1+2n2+1
由(等式⼀)和(等式⼆)计算得到：n0=n2+1。原命题得证！
3. 满⼆叉树，完全⼆叉树和⼆叉查树
3.1 满⼆叉树
定义：⾼度为h，并且由2{h} –1个结点的⼆叉树，被称为满⼆叉树。
3.2 完全⼆叉树
定义：⼀棵⼆叉树中，只有最下⾯两层结点的度可以⼩于2，并且最下⼀层的叶结点集中在靠左的若⼲位置上。这样的⼆叉树称为完全⼆叉树。
特点：叶⼦结点只能出现在最下层和次下层，且最下层的叶⼦结点集中在树的左部。显然，⼀棵满⼆叉树必定是⼀棵完全⼆叉树，⽽完全⼆叉树未必是满⼆叉树。
3.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）。
在实际应⽤中，⼆叉查树的使⽤⽐较多。下⾯，⽤C语⾔实现⼆叉查树。
⼆叉查树的C实现
1. 节点定义
1.1 节点定义
typedef int Type;
typedef struct BSTreeNode{
Type  key;                    // 关键字(键值)
struct BSTreeNode *left;    // 左孩⼦
struct BSTreeNode *right;    // 右孩⼦
struct BSTreeNode *parent;    // ⽗结点
}Node, *BSTree;
⼆叉查树的节点包含的基本信息：
(01) key      -- 它是关键字，是⽤来对⼆叉查树的节点进⾏排序的。
(02) left      -- 它指向当前节点的左孩⼦。
(03) right    -- 它指向当前节点的右孩⼦。
(04) parent -- 它指向当前节点的⽗结点。
1.2 创建节点
创建节点的代码
static Node* create_bstree_node(Type key, Node *parent, Node *left, Node* right)
{
Node* p;
if ((p = (Node *)malloc(sizeof(Node))) == NULL)
二叉树的基本性质return NULL;
p->key = key;
p->left = left;
p->right = right;
p->parent = parent;
return p;
}
2 遍历
这⾥讲解前序遍历、中序遍历、后序遍历3种⽅式。
2.1 前序遍历
若⼆叉树⾮空，则执⾏以下操作：
(01) 访问根结点；
(02) 先序遍历左⼦树；
(03) 先序遍历右⼦树。
前序遍历代码

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