该代码实现二叉查找树的建立、中序遍历、结点的插入与删除等操作。为什么该代码还没有输入要删除的结点,程序就自动执行了?
经过断点调试,scanf语句似乎没起到应有的作用。
···C++
#include <stdio.h>
#include <stdlib.h>
#include <vector>
using namespace std;
typedef int KeyType;
// 二叉查找树的结构体
typedef struct BSTNode {
KeyType key; // 数据
BSTNode *lchild, *rchild; // 左右子树
} BSTNode, *BiTree;
// 向二叉查找树插入结点
void insert_to_tree(BiTree& tree, KeyType key) {
BiTree tnode = (BiTree)calloc(1, sizeof(BSTNode)); // 新结点
tnode->key = key; // 把值放入
if (tree != NULL) {
BiTree tcur = tree, parent; // tcur为当前结点,parent为父节点
while (tcur) {
parent = tcur;
if (key < tcur->key) {
tcur = tcur->lchild;
} else {
tcur = tcur->rchild;
}
}
if (key < parent->key) {
parent->lchild = tnode;
} else {
parent->rchild = tnode;
}
return;
} else {
tree = tnode;
return;
}
}
// 建立二叉查找树
void create_BST(BiTree& tree) {
KeyType key;
vector<KeyType> vk;
while(scanf("%d", &key)) {
vk.push_back(key);
}
for (int i = 0; i < vk.size(); i++) {
key = vk[i];
insert_to_tree(tree, key);
}
}
void delete_BST(BiTree& tree, KeyType key) {
if (tree == nullptr) {
return;
}
if (tree->key < key) {
delete_BST(tree->rchild, key);
} else if (tree->key > key) {
delete_BST(tree->lchild, key);
} else {
// 找到待删除结点
BiTree temp = tree;
if (tree->lchild == nullptr) {
tree = tree->rchild;
free(temp);
} else if (tree->rchild == nullptr) {
tree = tree->lchild;
free(temp);
} else {
temp = tree->lchild;
while (temp->rchild) {
temp = temp->rchild;
}
tree->key = temp->key;
delete_BST(tree->lchild, temp->key);
}
}
}
void in_order(BiTree tree) {
if (tree) {
in_order(tree->lchild);
printf("%3d", tree->key);
in_order(tree->rchild);
}
}
int main() {
BiTree tree = nullptr;
create_BST(tree);
in_order(tree);
KeyType k;
printf("\nPlease input the key: ");
scanf("%d", &k);
delete_BST(tree, k);
in_order(tree);
return 0;
}
经过断点调试,scanf语句似乎没起到应有的作用。
···C++
#include <stdio.h>
#include <stdlib.h>
#include <vector>
using namespace std;
typedef int KeyType;
// 二叉查找树的结构体
typedef struct BSTNode {
KeyType key; // 数据
BSTNode *lchild, *rchild; // 左右子树
} BSTNode, *BiTree;
// 向二叉查找树插入结点
void insert_to_tree(BiTree& tree, KeyType key) {
BiTree tnode = (BiTree)calloc(1, sizeof(BSTNode)); // 新结点
tnode->key = key; // 把值放入
if (tree != NULL) {
BiTree tcur = tree, parent; // tcur为当前结点,parent为父节点
while (tcur) {
parent = tcur;
if (key < tcur->key) {
tcur = tcur->lchild;
} else {
tcur = tcur->rchild;
}
}
if (key < parent->key) {
parent->lchild = tnode;
} else {
parent->rchild = tnode;
}
return;
} else {
tree = tnode;
return;
}
}
// 建立二叉查找树
void create_BST(BiTree& tree) {
KeyType key;
vector<KeyType> vk;
while(scanf("%d", &key)) {
vk.push_back(key);
}
for (int i = 0; i < vk.size(); i++) {
key = vk[i];
insert_to_tree(tree, key);
}
}
void delete_BST(BiTree& tree, KeyType key) {
if (tree == nullptr) {
return;
}
if (tree->key < key) {
delete_BST(tree->rchild, key);
} else if (tree->key > key) {
delete_BST(tree->lchild, key);
} else {
// 找到待删除结点
BiTree temp = tree;
if (tree->lchild == nullptr) {
tree = tree->rchild;
free(temp);
} else if (tree->rchild == nullptr) {
tree = tree->lchild;
free(temp);
} else {
temp = tree->lchild;
while (temp->rchild) {
temp = temp->rchild;
}
tree->key = temp->key;
delete_BST(tree->lchild, temp->key);
}
}
}
void in_order(BiTree tree) {
if (tree) {
in_order(tree->lchild);
printf("%3d", tree->key);
in_order(tree->rchild);
}
}
int main() {
BiTree tree = nullptr;
create_BST(tree);
in_order(tree);
KeyType k;
printf("\nPlease input the key: ");
scanf("%d", &k);
delete_BST(tree, k);
in_order(tree);
return 0;
}