这段代码存在一个问题,即在删除结点x时,只考虑了将bt指针置为空的情况,但没有处理其他结点的连接关系。因此,在DeleX函数中需要修改如下:
在找到待删除的结点后,判断其是否为根节点:
- 如果是根节点,则直接销毁整棵二叉树。
- 如果不是根节点,则需通过父节点将其删除。
修改递归遍历左右子树部分,使其能够正确处理删除操作:
- 如果左子树非空且左子树的值等于x,则将该左子树置为空。
- 如果右子树非空且右子树的值等于x,则将该右子树置为空。
以下是修改后的代码,请参考:
#include <iostream>
using namespace std;
#define MaxSize 100
typedef char ElemType;
typedef struct tnode {
ElemType data;
struct tnode* lchild, *rchild;
} BTNode;
// 建立二叉树
void CreateBTree(BTNode*& bt, char* str) {
BTNode* St[MaxSize], *p = NULL;
int top = -1, k, j = 0;
char ch;
bt = NULL; // 建立的二叉树初始时为空
ch = str[j];
while (ch != '\0') { // str未扫描完时循环
switch (ch) {
case '(':
top++;
St[top] = p;
k = 1;
break; // 为左孩子结点
case ')':
top--;
break;
case ',':
k = 2;
break; // 为右孩子结点
default:
p = new BTNode();
p->data = ch;
p->lchild = p->rchild = NULL;
if (bt == NULL) {
bt = p; // *p为二叉树的根结点
} else { // 已建立二叉树根结点
switch (k) {
case 1:
St[top]->lchild = p;
break;
case 2:
St[top]->rchild = p;
break;
}
}
}
j++;
ch = str[j];
}
}
// 销毁二叉树
void DestroyBTree(BTNode*& bt) {
if (bt != NULL) {
DestroyBTree(bt->lchild);
DestroyBTree(bt->rchild);
free(bt);
}
}
// 输出二叉树
void DispBTree(BTNode* bt) {
if (bt != NULL) {
cout << bt->data;
if (bt->lchild != NULL || bt->rchild != NULL) {
cout << "(";
DispBTree(bt->lchild);
if (bt->rchild != NULL)
cout << ",";
DispBTree(bt->rchild);
cout << ")";
}
}
}
// 删除结点x
void DeleX(BTNode*& bt, ElemType x) {
if (bt != NULL) {
if (bt->data == x) {
if (bt->lchild == NULL && bt->rchild == NULL) { // 当前结点为叶子结点
delete bt;
bt = NULL;
} else { // 当前结点有子结点
DestroyBTree(bt);
bt = NULL;
}
} else {
if (bt->lchild != NULL && bt->lchild->data == x) {
DestroyBTree(bt->lchild);
bt->lchild = NULL;
}
if (bt->rchild != NULL && bt->rchild->data == x) {
DestroyBTree(bt->rchild);
bt->rchild = NULL;
}
DeleX(bt->lchild, x);
DeleX(bt->rchild, x);
}
}
}
int main() {
BTNode* bt;
char tree[MaxSize];
cin >> tree; // 输入二叉树的表示字符串
char x;
cin >> x; // 输入待删除的结点值
CreateBTree(bt, tree); // 建立二叉树
DeleX(bt, x); // 删除结点x
DispBTree(bt);
cout << endl;
DestroyBTree(bt); // 销毁二叉树
return 0;
}
希望对你有所帮助!如还有疑问,请随时追问。
内容由零声教学AI助手提供,问题来源于学员提问