[摘要]二进制排序树

1概述二进制排序树（Binary Sorting Tree）是一个空树或具有以下属性:

（1）如果具有左子树，则左子树上所有节点的数据都小于根节点的数据；

（2）如果具有右子树，则右子树中所有节点的数据都大于根节点的数据；

（3）左和右子树本身就是二进制排序树.

如下所示:

易于理解: 非空二进制排序树中的节点数据按左子树，树和右子树的顺序排列. 因此，通过遍历获得的节点序列是有序序列. 对于上图所示的二进制排序树，顺序遍历的结果为:

12,24,28,37,40,45,53,55,60,70

可以看出序列是按升序排列的.

通常，二进制链接列表可以用作二进制排序树的存储结构，并且可以在此基础上执行诸如搜索，插入和删除之类的操作. 存储结构如下: typedef struct bst {int data; struct bst *左; struct bst *正确； } BSTREE，* pBSTREE; 2二进制排序树搜索二进制排序树也称为二进制搜索树. 当二元排序树不为空时，首先将键值与根节点的关键字进行比较，如果相等，则搜索成功，否则根据给定值与根节点的关键字的大小关系，分别在其左侧或右侧子树上查找.

2.1二进制排序树搜索的递归实现递归在根指针t指向的二进制排序树中查找一个键等于键的元素. 如果搜索成功，则返回指向数据元素的指针二叉排序树查找 算法，否则返回Null指针. pBSTREE SearchBST_recur（pBSTREE t，int key）{if（！t || key == t-> data）返回t;否则（key data）返回（SearchBST_recur（t-> left，key））; else return（SearchBST_recur（t-> right，key））;} 2.2二进制排序树搜索的非递归实现是相同的. 您可以根据二进制排序树的特征执行非递归搜索. 如果搜索成功，则返回指向数据元素的Pointer，否则返回空指针: pBSTREE SearchBST（pBSTREE t，int key）{while（t）{if（key == t-> data）break;否则（key data）t = t-> left; else t = t-> right;} return t;} 3插入二进制排序树二进制排序树是一个动态表. 其特征在于二叉排序树查找 算法，通常不会一次生成树的结构，但是会在搜索过程中插入树中不存在的关键字时将其插入. 新插入的节点必须是新添加的叶节点，并且是搜索失败时在搜索路径上访问的最后一个节点的左子节点或右子节点.

在插入二进制排序树之前，您需要找到插入位置. 与上述简单的元素搜索不同，您还需要知道所插入节点的父节点. 仍然假设t是根指针，然后将一个新节点添加到二叉树中，键为键，具体过程如下:

（1）申请保存节点pnew的内存，并将关键字保存在节点的data字段中；

（2）在二进制排序树中找到插入节点pnew的父节点；

（3）将节点p的数据与父节点的数据进行比较，并确定是否将pnew插入到父节点的左侧或右侧子树中.

这里也用两种方法来实现，即递归和非递归.

3.1对递归搜索算法的小修改由于您需要了解插入节点的父节点，因此对2.1中的搜索算法进行小修改，以在搜索不成功时返回到插入位置.

在根指针t指向的二进制排序树中递归搜索其键等于键的数据元素. 如果搜索成功，则指针p指向的数据元素节点返回true；否则，返回true. 否则，p指向搜索路径. 访问最后一个节点并返回false；否则，返回false. 指针parent指向t的父对象，其初始化调用为NULL. bool SearchBST_recur_v2（pBSTREE t，int key，pBSTREE parent，pBSTREE p）{if（！t）{p = parent;返回false;}否则，如果（t-> data == key）{p = t;返回true;}否则，如果（t-> data left，key，t，p）;否则返回SearchBST_recur_v2（t-> right，key，t，p）;}将父节点置于插入位置后，即可插入. bool InsertBST（pBSTREE t，int key）{pBSTREE p，pnew;如果（！SearchBST_recur_v2（t，key，NULL，p））{assert（pnew =（pBSTREE）malloc（sizeof（BSTREE）））; pnew-> data =键; pnew-> left = p-> right = NULL;如果（！p）t = pnew;否则（key data）p-> left = pnew;否则p-> right = pnew;返回true；}否则返回false；} 3.2二进制排序树插入的非递归算法也可以使用以下方法将数据元素插入二进制排序树.

这里有两个部分来查找插入点和插入数据. void InsertBST（BSTREE * t，int key）{BSTREE * pnew，* parent，* p; p = t; assert（pnew =（BSTREE *）malloc（sizeof（BSTREE）））;; pnew-> data =键; pnew-> left = pnew-> right = NULL; while（p）{parent = p;如果（键 data）p = p->左;否则p = p->对； } // parent此时的父节点if（key data）parent-> left = pnew;否则，parent-> right = pnew; }从以上插入过程中可以看到，每个新插入节点都是二进制排序树中的所有新叶节点. 插入时，无需移动其他节点，只需将某个节点的指针从空更改为非空即可. 这相当于在不移动其他记录的情况下按有序序列插入记录.

这表明二元排序树不仅具有半查找的特征，而且还使用链作为存储结构，具有链存储结构的一些优点.

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-280381-1.html