大数据及人工智能基础知识复习系列1 二叉树及二叉搜索树

向右看齐 2022-06-10 00:25 204阅读 0赞

我将陆续讲解一些人工智能基础理论和算法。帮助大家系统学习人工智能知识。由于现在大家对这方面讨论很多，我将不会重复造车，网络上已有的知识会直接拿来分享。

感谢各位网友的分享精神。

二叉树是数据结构的一个重要基础。是后续讲解B B+树的基础。

感谢[Vamei][]的分享

[纸上谈兵: 树, 二叉树, 二叉搜索树][_ _]

作者：Vamei 出处：http://www.cnblogs.com/vamei 欢迎转载，也请保留这段声明。谢谢！

### 树的特征和定义 ###

树(Tree)是元素的集合。我们先以比较直观的方式介绍树。下面的数据结构是一个树：

![16224218-92e0f06926b443a9845653b27b2187d8.png][]

树有多个节点(node)，用以储存元素。某些节点之间存在一定的关系，用连线表示，连线称为边(edge)。边的上端节点称为父节点，下端称为子节点。树像是一个不断分叉的树根。

每个节点可以有多个子节点(children)，而该节点是相应子节点的父节点(parent)。比如说，3,5是6的子节点，6是3,5的父节点；1,8,7是3的子节点, 3是1,8,7的父节点。树有一个没有父节点的节点，称为根节点(root)，如图中的6。没有子节点的节点称为叶节点(leaf)，比如图中的1,8,9,5节点。从图中还可以看到，上面的树总共有4个层次，6位于第一层，9位于第四层。树中节点的最大层次被称为深度。也就是说，该树的深度(depth)为4。

如果我们从节点3开始向下看，而忽略其它部分。那么我们看到的是一个以节点3为根节点的树：

![16232143-93d719390c3e472c9768534d0a27e70f.png][]

三角形代表一棵树

再进一步，如果我们定义孤立的一个节点也是一棵树的话，原来的树就可以表示为根节点和子树(subtree)的关系:

![16233042-9861fb0986b74612b35faa40d49804f3.png][]

上述观察实际上给了我们一种严格的定义树的方法：

1. 树是元素的集合。

2. 该集合可以为空。这时树中没有元素，我们称树为空树 (empty tree)。

3. 如果该集合不为空，那么该集合有一个根节点，以及0个或者多个子树。根节点与它的子树的根节点用一个边(edge)相连。

上面的第三点是以递归的方式来定义树，也就是在定义树的过程中使用了树自身(子树)。由于树的递归特征，许多树相关的操作也可以方便的使用递归实现。我们将在后面看到。

(上述定义来自"Data Structures and Algorithm Analysis in C, by Mark Allen Weiss"。 我觉得有一点不太严格的地方。如果说空树属于树，第三点应该是 “...以及0个和多个非空子树...” )

### 树的实现 ###

树的示意图已经给出了树的一种内存实现方式: 每个节点储存元素和多个指向子节点的指针。然而，子节点数目是不确定的。一个父节点可能有大量的子节点，而另一个父节点可能只有一个子节点，而树的增删节点操作会让子节点的数目发生进一步的变化。这种不确定性就可能带来大量的内存相关操作，并且容易造成内存的浪费。

一种经典的实现方式如下:

![16235249-529d7d9dafee4f7192e6c57094372004.png][]

树的内存实现

拥有同一父节点的两个节点互为兄弟节点(sibling)。上图的实现方式中，每个节点包含有一个指针指向第一个子节点，并有另一个指针指向它的下一个兄弟节点。这样，我们就可以用统一的、确定的结构来表示每个节点。

计算机的文件系统是树的结构，比如[Linux文件管理背景知识][Linux]中所介绍的。在UNIX的文件系统中，每个文件(文件夹同样是一种文件)，都可以看做是一个节点。非文件夹的文件被储存在叶节点。文件夹中有指向父节点和子节点的指针(在UNIX中，文件夹还包含一个指向自身的指针，这与我们上面见到的树有所区别)。在git中，也有类似的树状结构，用以表达整个文件系统的版本变化 (参考[版本管理三国志][Link 1])。

![16230341-b8873fc15d314641ae33399d473cf2d2.jpg][]

文件树

### 二叉搜索树的C实现 ###

二叉树(binary)是一种特殊的树。二叉树的每个节点最多只能有2个子节点：

![17000135-75060e3ee81847c6892d2167710b4317.png][]

二叉树

由于二叉树的子节点数目确定，所以可以直接采用上图方式在内存中实现。每个节点有一个左子节点(left children)和右子节点(right children)。左子节点是左子树的根节点，右子节点是右子树的根节点。

如果我们给二叉树加一个额外的条件，就可以得到一种被称作二叉搜索树(binary search tree)的特殊二叉树。二叉搜索树要求：每个节点都不比它左子树的任意元素小，而且不比它的右子树的任意元素大。

(如果我们假设树中没有重复的元素，那么上述要求可以写成：每个节点比它左子树的任意节点大，而且比它右子树的任意节点小)

![17001935-1b9faa8518a14f95b3bb9eb3083f683c.png][]

二叉搜索树，注意树中元素的大小

二叉搜索树可以方便的实现搜索算法。在搜索元素x的时候，我们可以将x和根节点比较:

1. 如果x等于根节点，那么找到x，停止搜索 (终止条件)

2. 如果x小于根节点，那么搜索左子树

3. 如果x大于根节点，那么搜索右子树

二叉搜索树所需要进行的操作次数最多与树的深度相等。n个节点的二叉搜索树的深度最多为n，最少为log(n)。

下面是用C语言实现的二叉搜索树，并有搜索，插入，删除，寻找最大最小节点的操作。每个节点中存有三个指针，一个指向父节点，一个指向左子节点，一个指向右子节点。

(这样的实现是为了方便。节点可以只保存有指向左右子节点的两个指针，并实现上述操作。)

删除节点相对比较复杂。删除节点后，有时需要进行一定的调整，以恢复二叉搜索树的性质(每个节点都不比它左子树的任意元素小，而且不比它的右子树的任意元素大)。

*  叶节点可以直接删除。
 *  删除非叶节点时，比如下图中的节点8，我们可以删除左子树中最大的元素(或者右树中最大的元素)，用删除的节点来补充元素8产生的空缺。但该元素可能也不是叶节点，所以它所产生的空缺需要其他元素补充…… 直到最后删除一个叶节点。上述过程可以递归实现。

![17004331-c29bb56faa7f469fbdc52aade30beac8.png][]

删除节点

![17004501-b9e0747212684604afc4c5aebb109932.png][]

删除节点后的二叉搜索树

![复制代码][copycode.gif]

/* By Vamei */
    /* binary search tree */ #include <stdio.h> #include <stdlib.h> typedef struct node *position; typedef int ElementTP; struct node { position parent; ElementTP element; position lchild; position rchild; }; /* pointer => root node of the tree */ typedef struct node *TREE; void print_sorted_tree(TREE); position find_min(TREE); position find_max(TREE); position find_value(TREE, ElementTP); position insert_value(TREE, ElementTP); ElementTP delete_node(position); static int is_root(position); static int is_leaf(position); static ElementTP delete_leaf(position); static void insert_node_to_nonempty_tree(TREE, position); void main(void) { TREE tr; position np; ElementTP element; tr = NULL; tr = insert_value(tr, 18); tr = insert_value(tr, 5); tr = insert_value(tr, 2); tr = insert_value(tr, 8); tr = insert_value(tr, 81); tr = insert_value(tr, 101); printf("Original:\n"); print_sorted_tree(tr); np = find_value(tr, 8); if(np != NULL) { delete_node(np); printf("After deletion:\n"); print_sorted_tree(tr); } } /* * print values of the tree in sorted order */
    void print_sorted_tree(TREE tr) { if (tr == NULL) return; print_sorted_tree(tr->lchild); printf("%d \n", tr->element); print_sorted_tree(tr->rchild); } /* * search for minimum value * traverse lchild */ position find_min(TREE tr) { position np; np = tr; if (np == NULL) return NULL; while(np->lchild != NULL) { np = np->lchild; } return np; } /* * search for maximum value * traverse rchild */ position find_max(TREE tr) { position np; np = tr; if (np == NULL) return NULL; while(np->rchild != NULL) { np = np->rchild; } return np; } /* * search for value * */ position find_value(TREE tr, ElementTP value) { if (tr == NULL) return NULL; if (tr->element == value) { return tr; } else if (value < tr->element) { return find_value(tr->lchild, value); } else { return find_value(tr->rchild, value); } } /* * delete node np */ ElementTP delete_node(position np) { position replace; ElementTP element; if (is_leaf(np)) { return delete_leaf(np); } else { /* if a node is not a leaf, then we need to find a replacement */ replace = (np->lchild != NULL) ? find_max(np->lchild) : find_min(np->rchild); element = np->element; np->element = delete_node(replace); return element; } } /* * insert a value into the tree * return root address of the tree */ position insert_value(TREE tr, ElementTP value) { position np; /* prepare the node */ np = (position) malloc(sizeof(struct node)); np->element = value; np->parent  = NULL; np->lchild  = NULL; np->rchild  = NULL; if (tr == NULL) tr = np; else { insert_node_to_nonempty_tree(tr, np); } return tr; } //=============================================
    
    /* * np is root? */
    static int is_root(position np) { return (np->parent == NULL); } /* * np is leaf? */
    static int is_leaf(position np) { return (np->lchild == NULL && np->rchild == NULL); } /* * if an element is a leaf, * then it could be removed with no side effect. */
    static ElementTP delete_leaf(position np) { ElementTP element; position parent; element = np->element; parent = np->parent; if(!is_root(np)) { if (parent->lchild == np) { parent->lchild = NULL; } else { parent->rchild = NULL; } } free(np); return element; } /* * insert a node to a non-empty tree * called by insert_value() */
    static void insert_node_to_nonempty_tree(TREE tr, position np) { /* insert the node */
        if(np->element <= tr->element) { if (tr->lchild == NULL) { /* then tr->lchild is the proper place */ tr->lchild = np; np->parent = tr; return; } else { insert_node_to_nonempty_tree(tr->lchild, np); } } else if(np->element > tr->element) { if (tr->rchild == NULL) { tr->rchild = np; np->parent = tr; return; } else { insert_node_to_nonempty_tree(tr->rchild, np); } } }

![复制代码][copycode.gif]

运行结果:

Original:  
2  
5  
8  
18  
81  
101  
After deletion:  
2  
5  
18  
81  
101

上述实现中的删除比较复杂。有一种简单的替代操作，称为懒惰删除(lazy deletion)。在懒惰删除时，我们并不真正从二叉搜索树中删除该节点，而是将该节点标记为“已删除”。这样，我们只用找到元素并标记，就可以完成删除元素了。如果有相同的元素重新插入，我们可以将该节点找到，并取消删除标记。

懒惰删除的实现比较简单，可以尝试一下。树所占据的内存空间不会因为删除节点而减小。懒惰节点实际上是用内存空间换取操作的简便性。

### 总结 ###

树, 二叉树, 二叉搜索树

二叉搜索树的删除

懒惰删除

欢迎继续阅读[“纸上谈兵: 算法与数据结构”][Link 2]系列。

[Vamei]: http://www.cnblogs.com/vamei/
[_ _]: http://www.cnblogs.com/vamei/archive/2013/03/17/2962290.html
[16224218-92e0f06926b443a9845653b27b2187d8.png]: /images/20220610/3c47147f06e2446782e5e17d4fa06a58.png
[16232143-93d719390c3e472c9768534d0a27e70f.png]: /images/20220610/b3a9f77ca8834b6ea049349d675d5093.png
[16233042-9861fb0986b74612b35faa40d49804f3.png]: /images/20220610/2daef273c4354046a85aa78ae3a4f5c7.png
[16235249-529d7d9dafee4f7192e6c57094372004.png]: /images/20220610/b71512331b974cc3823092462ae398c9.png
[Linux]: http://www.cnblogs.com/vamei/archive/2012/09/09/2676792.html
[Link 1]: http://www.cnblogs.com/vamei/archive/2013/02/21/2918069.html
[16230341-b8873fc15d314641ae33399d473cf2d2.jpg]: /images/20220610/f21d76d06b1a47b99f3bbc9e63a4678f.png
[17000135-75060e3ee81847c6892d2167710b4317.png]: /images/20220610/9a491bd5cd3b49c083a50ff50d6480d7.png
[17001935-1b9faa8518a14f95b3bb9eb3083f683c.png]: /images/20220610/f62c6fedb05f4efc9d1459fcf26e4d5b.png
[17004331-c29bb56faa7f469fbdc52aade30beac8.png]: /images/20220610/7fce03a72bd84a45986802ec5ac5b7a9.png
[17004501-b9e0747212684604afc4c5aebb109932.png]: /images/20220610/209d10cfd795455bb2f60ffb5cd166a3.png
[copycode.gif]: /images/20220610/bf9e0ae385e6481189ca7f5056757120.png
[Link 2]: http://www.cnblogs.com/vamei/archive/2013/03/22/2974052.html