C++ 二叉排序树

1. 二叉排序树的要求：树根的左子树，均要小于树根；树根的右子树，均要大于树根。对于任意一个结点及其子树，均要满足二叉排序树的要求。
2. 基于二叉排序树的基本特性，可知：左子树的最一定位于左子树的最右边；右子树的最大数据一定位于右子树的最左边。
3. 对于二叉排序树的构建，依次与树 / 子树的根结点进行对比，小于根结点，放在左边；大于根结点，放在右边，直到插入位置左右子树为空时停止，在该位置插入。
4. 二叉排序树的最大查找次数，就是树的深度，类似于折半查找，每查一次排除一半的树。
5. 删除二叉排序树的过程： 基于二叉树的查找，找到要删除的 root 结点，如果 root 结点没有左子树 / 没有右子树，则非常好办，直接将右子树 / 左子树覆盖 root 结点即可，不论下面多么复杂，都符合二叉排序树的要求。如果左右子树均不为空，那就进入该 root 结点的左子树，找到左子树的最大数据结点 tempNode ，将最大数据覆值给要删除的结点，再在 root 结点的左子树删除 tempNode 结点。主要思想就是：找到要删除结点的左子树中的最大结点当做“替死鬼”，再删除该“替死鬼”，并不是真的删除 root 结点。

代码实践

代码语言：javascript

AI代码解释

/* 二叉排序树（又叫二叉查找树） */ #include <iostream> using namespace std; typedef int KeyType; // 树 typedef struct BSTNode { KeyType key; // 数据域 struct BSTNode *lchild, *rchild; // 左孩子，右孩子 } BSTNode, *BiTree; // 插入结点 int BST_Insert(BiTree &T, KeyType k) { if (T == NULL) { // 第一个结点作为树根 T = (BSTNode *)malloc(sizeof(BSTNode)); T->key = k; T->lchild = T->rchild = NULL; return 1; } else if (k == T->key) { return 0; // 发现相同元素，不插入 } else if (k < T->key) { return BST_Insert(T->lchild, k); // 插入结点小于当前结点，插入左边 } else { return BST_Insert(T->rchild, k); // 插入结点小于当前结点，插入右边 } } // 构建二叉排序树 void Creat_BST(BiTree &T, KeyType str[], int n) { T = NULL; int i = 0; while (i < n) { BST_Insert(T, str[i]); // 把某一结点放入二叉排序树 i++; } } // 二叉排序树的查找 BSTNode *BST_Search(BiTree T, KeyType key, BSTNode *&p) { p = NULL; while (T != NULL && key != T->key) { p = T; if (key < T->key) { T = T->lchild; } else { T = T->rchild; } } return T; // 没有引用，不会造成影响 } // 删除结点 void DeleteNode(BSTNode *&root, KeyType x) { if (root == NULL) { return; } if (root->key > x) { DeleteNode(root->lchild, x); } else if (root->key < x) { DeleteNode(root->rchild, x); } else { // 查找到了删除结点 if (root->lchild == NULL) { // 左子树为空 BSTNode *tempNode = root; root = root->rchild; // 直接将右子树赋值该结点，然后释放 free(tempNode); } else if (root->rchild == NULL) { // 右子树为空 BSTNode *tempNode = root; root = root->lchild; // 直接将右子树赋值该结点，然后释放 free(tempNode); } else { // 左右子树都不为空 // 删除策略：选取左子树的最大数据 或 右子树的最小数据 // 此处策略寻找左子树的最大数据 BSTNode *tempNode = root->lchild; if (tempNode->rchild != NULL) { tempNode = tempNode->rchild; // 左子树的最大数据，一定位于左子树的最右结点，右子树的最小数据，一定位于右子树的最左结点 } root->key = tempNode->key; // 将左子树的最大结点置于根结点，再删除左子树的对应结点 DeleteNode(root->lchild, tempNode->key); } } } // 中序遍历：左根右 void InOrder(BiTree T) { if (T != NULL) { InOrder(T->lchild); cout << T->key << " "; // putchar(T->key); InOrder(T->rchild); } } int main() { BiTree T; // 树根 BSTNode *parent; // 存储父亲结点的地址 BSTNode *search; // 查找结点 KeyType str[] = {54, 20, 66, 40, 28, 79, 58}; Creat_BST(T, str, 7); InOrder(T); printf("\n"); search = BST_Search(T, 40, parent); if (search) { printf("找到对应结点，值=%d\n", search->key); } else { printf("未找到对应结点\n"); } DeleteNode(T, 40); InOrder(T); return 0; }