2023年6月22日发(作者：)

数据结构⼆叉树的⼀些性质及证明、树的路径长度、结点的路径长度

树的介绍

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) 先序遍历右⼦树。前序遍历代码void preorder_bstree(BSTree tree){ if(tree != NULL) { printf("%d ", tree->key); preorder_bstree(tree->left); preorder_bstree(tree->right); }}2.2 中序遍历若⼆叉树⾮空，则执⾏以下操作：(01) 中序遍历左⼦树；(02) 访问根结点；(03) 中序遍历右⼦树。中序遍历代码void inorder_bstree(BSTree tree){ if(tree != NULL) { inorder_bstree(tree->left); printf("%d ", tree->key); inorder_bstree(tree->right); }}2.3 后序遍历若⼆叉树⾮空，则执⾏以下操作：(01) 后序遍历左⼦树；(02) 后序遍历右⼦树；(03) 访问根结点。后序遍历代码void postorder_bstree(BSTree tree){ if(tree != NULL) { postorder_bstree(tree->left); postorder_bstree(tree->right); printf("%d ", tree->key); }}下⾯通过例⼦对这些遍历⽅式进⾏介绍。对于上⾯的⼆叉树⽽⾔，(01) 前序遍历结果： 3 1 2 5 4 6(02) 中序遍历结果： 1 2 3 4 5 6

(03) 后序遍历结果： 2 1 4 6 5 33. 查找递归版本的代码Node* bstree_search(BSTree x, Type key){ if (x==NULL || x->key==key) return x; if (key < x->key) return bstree_search(x->left, key); else return bstree_search(x->right, key);}⾮递归版本的代码Node* iterative_bstree_search(BSTree x, Type key){ while ((x!=NULL) && (x->key!=key)) { if (key < x->key) x = x->left; else x = x->right; } return x;}4. 最⼤值和最⼩值查找最⼤值的代码Node* bstree_maximum(BSTree tree){ if (tree == NULL) return NULL; while(tree->right != NULL) tree = tree->right; return tree;}查找最⼩值的代码Node* bstree_minimum(BSTree tree){ if (tree == NULL) return NULL; while(tree->left != NULL) tree = tree->left; return tree;}5. 前驱和后继节点的前驱：是该节点的左⼦树中的最⼤节点。节点的后继：是该节点的右⼦树中的最⼩节点。查找前驱节点的代码Node* bstree_predecessor(Node *x){ // 如果x存在左孩⼦，则"x的前驱结点"为 "以其左孩⼦为根的⼦树的最⼤结点"。 if (x->left != NULL) return bstree_maximum(x->left); // 如果x没有左孩⼦。则x有以下两种可能： // (01) x是"⼀个右孩⼦"，则"x的前驱结点"为 "它的⽗结点"。 // (01) x是"⼀个左孩⼦"，则查找"x的最低的⽗结点，并且该⽗结点要具有右孩⼦"，找到的这个"最低的⽗结点"就是"x的前驱结点"。 Node* y = x->parent; while ((y!=NULL) && (x==y->left)) { x = y; y = y->parent; } return y;}查找后继节点的代码Node* bstree_successor(Node *x){ // 如果x存在右孩⼦，则"x的后继结点"为 "以其右孩⼦为根的⼦树的最⼩结点"。 if (x->right != NULL) return bstree_minimum(x->right); // 如果x没有右孩⼦。则x有以下两种可能： // (01) x是"⼀个左孩⼦"，则"x的后继结点"为 "它的⽗结点"。 // (02) x是"⼀个右孩⼦"，则查找"x的最低的⽗结点，并且该⽗结点要具有左孩⼦"，找到的这个"最低的⽗结点"就是"x的后继结点"。 Node* y = x->parent; while ((y!=NULL) && (x==y->right)) { x = y; y = y->parent; } return y;}6. 插⼊插⼊节点的代码static Node* bstree_insert(BSTree tree, Node *z){ Node *y = NULL; Node *x = tree; // 查找z的插⼊位置 while (x != NULL) { y = x; if (z->key < x->key) x = x->left; else x = x->right; } z->parent = y; if (y==NULL) tree = z; else if (z->key < y->key) y->left = z; else y->right = z; return tree;}Node* insert_bstree(BSTree tree, Type key){ Node *z; // 新建结点 // 如果新建结点失败，则返回。 if ((z=create_bstree_node(key, NULL, NULL, NULL)) == NULL) return tree; return bstree_insert(tree, z);}bstree_insert(tree, z)是内部函数，它的作⽤是：将结点(z)插⼊到⼆叉树(tree)中，并返回插⼊节点后的根节点。insert_bstree(tree, key)是对外接⼝，它的作⽤是：在树中新增节点，key是节点的值；并返回插⼊节点后的根节点。注：本⽂实现的⼆叉查找树是允许插⼊相同键值的节点的！若⽤户不希望插⼊相同键值的节点，将bstree_insert()修改为以下代码即可。static Node* bstree_insert(BSTree tree, Node *z){ Node *y = NULL; Node *x = tree; // 查找z的插⼊位置 while (x != NULL) { y = x; if (z->key < x->key) x = x->left; else if (z->key > x->key) x = x->right; else { free(z); // 释放之前分配的系统。 return tree; } } z->parent = y; if (y==NULL) tree = z; else if (z->key < y->key) y->left = z; else y->right = z; return tree;}7. 删除删除节点的代码static Node* bstree_delete(BSTree tree, Node *z){ Node *x=NULL; Node *y=NULL; if ((z->left == NULL) || (z->right == NULL) ) y = z; else y = bstree_successor(z); if (y->left != NULL) x = y->left; else x = y->right; if (x != NULL) x->parent = y->parent; if (y->parent == NULL) tree = x; else if (y == y->parent->left) y->parent->left = x; else y->parent->right = x; if (y != z)

z->key = y->key; if (y!=NULL) free(y); return tree;}Node* delete_bstree(BSTree tree, Type key){ Node *z, *node;

if ((z = bstree_search(tree, key)) != NULL) tree = bstree_delete(tree, z); return tree;}bstree_delete(tree, z)是内部函数，它的作⽤是：删除⼆叉树(tree)中的节点(z)，并返回删除节点后的根节点。delete_bstree(tree, key)是对外接⼝，它的作⽤是：在树中查找键值为key的节点，找到的话就删除该节点；并返回删除节点后的根节点。8. 打印打印⼆叉树的代码void print_bstree(BSTree tree, Type key, int direction){ if(tree != NULL) { if(direction==0) // tree是根节点 printf("%2d is rootn", tree->key); else // tree是分⽀节点 printf("%2d is %2d's %6s childn", tree->key, key, direction==1?"right" : "left"); print_bstree(tree->left, tree->key, -1); print_bstree(tree->right,tree->key, 1); }}print_bstree(tree, key, direction)的作⽤是打印整颗⼆叉树(tree)。其中，tree是⼆叉树节点，key是⼆叉树的键值，⽽direction表⽰该节点的类型：direction为 0，表⽰该节点是根节点;direction为-1，表⽰该节点是它的⽗结点的左孩⼦;direction为 1，表⽰该节点是它的⽗结点的右孩⼦。9. 销毁⼆叉树销毁⼆叉树的代码void destroy_bstree(BSTree tree){ if (tree==NULL) return ; if (tree->left != NULL) destroy_bstree(tree->left); if (tree->right != NULL) destroy_bstree(tree->right); free(tree);}转载出处：