进行到查找的章节，来敲一下二叉排序树的相关代码{:301_998:}
实现功能：写出递归算法，从小到大输出二叉排序树中所有数据值>=x的结点的数据。要求先找到第一个满足条件的结点后，再依次输出其他满足条件的结点。
算法思想：1、找两个[第一个]: 1、从根节点向右找出【第一个】值>=x的节点，并记录为bst
2、以bst为根节点的二叉树中向左找到【第一个】值<x的节点p，在以bst为根节点的二叉树中删除以p为根结点的子树
2、再中序遍历bst为根节点的二叉排序树（整棵树的节点值都>=x）。
二叉排序树结构以及生成、插入操作的代码：
//树节点
struct TreeNode {//现在不用typedef，但考试需要
TreeNode* lchild;
TreeNode* rchild;
int value;
};
//二叉排序树
struct BinaryTree {
int Num; //节点个数
TreeNode *root; //根节点
};
//生成二叉排序树，根节点为15
BinaryTree* creatBinaryTree() {
BinaryTree *tree = (BinaryTree*)malloc(sizeof(BinaryTree));
TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));
if (root) {
root->lchild = NULL;
root->rchild = NULL;
root->value = 15;
tree->Num = 1;
tree->root = root;
printf("初始化树成功！\n");
return tree;
}
}
//插入节点
bool insertNode(BinaryTree *tree, int x) {
TreeNode* p_parent = tree->root;
TreeNode* p = tree->root;
//找父节点
while (p!=NULL) {
if (x == p->value) {
cout << "节点已存在" << endl;
return false;
}
else if (x > p->value) {
p_parent = p;
p= p->rchild;
}
else {
p_parent = p;
p = p->lchild;
}
}
//插入节点
TreeNode* child = (TreeNode*)malloc(sizeof(TreeNode));
child->lchild = NULL;
child->rchild = NULL;
child->value = x;
if (x > p_parent->value) {
p_parent->rchild = child;
(tree->Num)++;
}
else {
p_parent->lchild = child;
(tree->Num)++;
}
return true;
}
具体算法代码：
//中序遍历二叉排序树
void Print(TreeNode *root) {
if (root->lchild != NULL) Print(root->lchild);
cout << root->value << " ";
if (root->rchild != NULL) Print(root->rchild);
}
//算法入口
void PrintABThanX(TreeNode *root,int x) {
if (root == NULL) return;
TreeNode *p = root;
if (p) {
while (x > p->value&&p->rchild != NULL) p = p->rchild;//向右找到一个比x大的节点
TreeNode *bst = p;//储存这棵树的根节点
if (bst) {
TreeNode *p_pre = p;//p的父节点
p = p->lchild;
//在bst为根的二叉树中从左分支向下找到第一个<x的节点
while (p&&p->value >= x) {
p_pre = p;
p = p->lchild;
}
//此时会出现两种情况：1、p遍历到最左的节点（即为空指针） 2、找到一个比x小的节点，此时要断开这棵子树，得到一颗节点值全部>=x的二叉排序树
if (p) p_pre->lchild = NULL;
//直接中序遍历这颗新二叉排序树
Print(bst);
}
}
}
主程序代码：
BinaryTree *tree = creatBinaryTree();
int num = 0;
insertNode(tree, 7);
insertNode(tree, 40);
insertNode(tree, 11);
insertNode(tree, 4);
insertNode(tree, 20);
insertNode(tree, 5);
insertNode(tree, 9);
insertNode(tree, 1);
insertNode(tree, 50);
insertNode(tree, 17);
insertNode(tree, 30);
insertNode(tree, 48);
insertNode(tree, 43);
insertNode(tree, 49);
insertNode(tree, 16);
insertNode(tree, 60);
cout << "先序遍历二叉树:" << endl;
Print(tree->root);
cout << endl;
int x = -1;
while (x != -2) {
int x = -1;
cout << "输入x值:";
cin >> x;
PrintABThanX(tree->root, x);
cout << endl << endl;
}``
生成的二叉排序树：
调试结果：
| 
发表于 2020-11-28 17:15
|
发表于 2020-11-28 18:35
