【c++】【数据结构笔记】<在二叉排序树中按顺序输出>=x的节点值>

false_554 发表于 2020-11-28 17:15

进行到查找的章节，来敲一下二叉排序树的相关代码{: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;
}``
```

生成的二叉排序树：

调试结果：

QingYi. 发表于 2020-11-28 17:38

倒数第二张图是自己画的吗

false_554 发表于 2020-11-28 18:35

QingYi. 发表于 2020-11-28 17:38
倒数第二张图是自己画的吗

对，自己用画图画的

无名氏wyw 发表于 2020-11-28 19:39

那是中序遍历，不是先序。。
建议再补补，比如这两道题
https://www.luogu.com.cn/problem/P1030
https://www.luogu.com.cn/problem/P1087

false_554 发表于 2020-11-29 15:58

无名氏wyw 发表于 2020-11-28 19:39
那是中序遍历，不是先序。。
建议再补补，比如这两道题
https://www.luogu.com.cn/problem/P1030

哈哈哈笔误写错了，当时脑子里想的是中序，敲出来却是先序{:1_908:}

false_554 发表于 2020-11-29 15:59

false_554 发表于 2020-11-29 15:58
哈哈哈笔误写错了，当时脑子里想的是中序，敲出来却是先序

算法思想那里写的是中序遍历{:1_908:}

页: [1]

吾爱破解 - 52pojie.cn's Archiver

【c++】【数据结构笔记】<在二叉排序树中按顺序输出>=x的节点值>