关于#二叉树#的问题，如何解决？

您好，我是一名自学生。现在正在看C prime plus的最后一章。学到了二叉树部分。有个问题想向您请教：

img

img

img


图片是书里的二叉树的删除项的函数及其子函数，请问这几行代码

img


为什么不能替换成：

else:
  DeleteNode(&look.child);

引用new bing部分回答作答：
这是因为，如果要删除一个节点，需要同时知道要删除节点的父节点和要删除的节点本身。因为在二叉树中，每个节点都有一个左子节点和一个右子节点，删除一个节点时需要将其父节点的左子节点或右子节点指向其另一个子节点，否则会导致二叉树结构的错误。

在你提到的代码中，look.parent是要删除节点的父节点，look.child是要删除的节点本身。如果使用DeleteNode(&look.child)，虽然可以删除节点，但无法修改其父节点的子节点指针。因此，这种方法不能保证删除节点后的二叉树结构是正确的。

相比之下，使用原始代码中的条件语句，可以根据要删除节点的位置选择正确的子节点指针进行修改，以保证二叉树结构的正确性。

以下答案由GPT-3.5大模型与博主波罗歌共同编写：
在删除二叉树节点时，我们需要找到待删除节点的前驱或后继，以保证二叉树的结构不被破坏。一般来说，我们可以使用递归的方式进行删除。

在这个代码片段中，look是待删除节点的父节点，target是待删除节点本身。

注释中说到：

target不是最低级子节点，就用最靠左子树节点代替它，
但如果最靠左子树节点有右子节点，
也需要将此右子节点移植到它的父节点下面。

这实际上是在处理某个节点有两个子节点的情况，我们需要找到该节点的后继节点，将其值赋给该节点，然后再将后继节点删除。这个过程需要保证二叉树的结构不被破坏。

具体来说，look.child == target说明待删除节点是其父节点的左节点，此时可以用它的最靠左叶子节点代替它（即 DeleteNode(&look.child->right)），并将该节点的值赋给待删除节点。这个叶子节点只可能存在于其父节点的左子树上，因此用递归的方式可以很好地解决。

相反，如果 look.child != target，说明待删除节点是其父节点的右节点。此时不能直接递归调用 DeleteNode(&look.child)，因为这样会导致我们在查找待删除节点的前驱节点时跳过该节点的右子树。因此，我们要将递归调用改为 DeleteNode(&look.child->right)，以正确地遍历该节点的右子树。

下面是一个可能更加清晰的代码实现：

typedef struct node
{
    int data;
    node* left;
    node* right;
} Node;

void DeleteNode(Node** root, int value)
{
    if (*root == nullptr)
        return;

    if ((*root)->data == value)
    {
        if ((*root)->left == nullptr)  // 左子树为空
        {
            Node* tmp = *root;
            *root = (*root)->right;
            delete tmp;
        }
        else if ((*root)->right == nullptr)  // 右子树为空
        {
            Node* tmp = *root;
            *root = (*root)->left;
            delete tmp;
        }
        else  // 左右子树均不为空
        {
            Node* min = (*root)->right;
            while (min->left != nullptr)
                min = min->left;

            (*root)->data = min->data;
            DeleteNode(&(*root)->right, min->data);
        }
    }
    else if ((*root)->data > value)
    {
        DeleteNode(&(*root)->left, value);
    }
    else
    {
        DeleteNode(&(*root)->right, value);
    }
}

这个实现中，我们使用递归的方式遍历二叉树，找到待删除节点后，分三种情况进行处理：

  1. 待删除节点没有左子树，直接用右子树代替它
  2. 待删除节点没有右子树，直接用左子树代替它
  3. 待删除节点既有左子树又有右子树，找到其后继节点，将其值赋给待删除节点，并递归地删除后继节点

对于第三种情况，我们在递归中寻找待删除节点的后继节点，确保二叉树的结构不被破坏。

此外，由于我们使用了指向指针（即二重指针）的参数传递方式，可以方便地修改二叉树根节点的值。

希望以上解释和代码可以帮助您理解二叉树删除的过程。如果您还有任何疑问，请随时提出。
如果我的回答解决了您的问题，请采纳！

以下内容引用CHATGPT：

这几行代码不能替换成 else: DeleteNode(&look.child); 的原因是，DeleteNode(&look.child); 并没有将 look.child 的值删除，而是删除了 look.child 的子节点。如果 look.child 恰好是要删除的节点，那么这个节点没有被删除，而且还会出现内存泄漏的问题。因此，需要将 look.child 的值替换为其子节点的值，并删除子节点。

这里是正确的代码实现：

void DeleteNode(TreeNode *ptr) {
    TreeNode * temp;
    if (ptr->right == NULL) {
        temp = ptr;
        ptr = ptr->left;
        free(temp);
    } else if (ptr->left == NULL) {
        temp = ptr;
        ptr = ptr->right;
        free(temp);
    } else {
        temp = ptr->left;
        while (temp->right != NULL) {
            temp = temp->right;
        }
        temp->right = ptr->right;
        temp = ptr;
        ptr = ptr->left;
        free(temp);
    }
}

其中，temp 是一个临时指针，用于保存要删除的节点或其子节点。如果要删除的节点没有右子节点，则用左子节点替代要删除的节点。同理，如果要删除的节点没有左子节点，则用右子节点替代要删除的节点。如果要删除的节点既有左子节点又有右子节点，则找到其左子树中的最右节点，用其右子节点替代要删除的节点，然后删除该最右节点。

在替换子节点时，需要注意将子节点的值复制到要删除的节点上，避免出现内存泄漏问题。

主要是每个被删除的节点，还有父节点指向它，所以删除时要把指向它的那个指针值设置为null

亲，您好，引用new bing部分回答作答：

bool DeleteItem(const Item * pi, Tree * ptree)
{
    Pair look;
    look = SeekItem(pi,ptree);
    if (look.child == NULL)
        return false;
    
    if (look.parent == NULL)  /* 删除根项目 */
        DeleteNode(&ptree->root);
    else if (look.parent->left == look.child)
        DeleteNode(&look.parent->left);
    else
        DeleteNode(&look.parent->right);
        
    ptree->size--;
    return true;   
}

这段代码中如果将 DeleteNode(&look.parent->right); 替换成 DeleteNode(&look.child);，会导致一个逻辑错误。因为 look.child 指向的是要删除的节点，而 DeleteNode 函数的参数是一个指向指针的指针，它会修改指针的值，使其指向 NULL。这样，look.parent->right 就不会被修改，仍然指向已经被释放的内存，造成一个悬空指针。这会导致程序运行时出现未定义行为，可能引发内存泄漏、崩溃或其他错误（Segmentation fault）。所以，正确的做法是传递 look.parent->right 的地址给 DeleteNode 函数，让它修改父节点的右子节点指针。

不知道你这个问题是否已经解决, 如果还没有解决的话:
  • 这有个类似的问题, 你可以参考下: https://ask.csdn.net/questions/7485075
  • 除此之外, 这篇博客: 数据结构-图的实现以及基础算法-C语言实现中的  2.3 图最小生成树的Prime算法 部分也许能够解决你的问题, 你可以仔细阅读以下内容或者直接跳转源博客中阅读:
    #define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>

// 图的结点的数据类型为Char
typedef char VertexDataType;
// 边的权值类型为Int
typedef int EdgeWeightDataType;

typedef struct {
	VertexDataType lowAdjVex; // 与最小边相邻接的顶点的值
	EdgeWeightDataType lowEdgeWeight; // 最小边的权值
}closedge;

typedef struct {
	VertexDataType* setsOfVertex; // 一维数组存储顶点的值
	EdgeWeightDataType** AdjacencyMatrix; // 二维数组表示邻接矩阵
	closedge* flag; // 标记数组
	int numsOfVertex; // 顶点的个数
	int numsOfEdge;  // 边的条数
	int MaxSizeCnt; // 限制顶点的最大个数
}MatrixGraph; // 邻接矩阵表示图的结构

void InitGraph(MatrixGraph* Graph, int n); // 初始化图的结构

void InsertVertex(MatrixGraph* Graph, VertexDataType vertex); // 在图中插入顶点

void InsertEdge(MatrixGraph* Graph, int v1, int v2, EdgeWeightDataType weight); // 添加顶点间的联系

void ShowMatrix(MatrixGraph* Graph); // 显示图的邻接矩阵表示

int searchVerIndex(MatrixGraph* Graph, VertexDataType verValue); // 在邻接矩阵中寻找值为verIndex的顶点的索引

int Min(MatrixGraph* Graph); // 在辅助数组中寻找最小边，目的是添加顶点

void MST_Prim(MatrixGraph* Graph, VertexDataType vertexValue); // 借助图的邻接矩阵来实现Prim算法

int main() {
	MatrixGraph graph;
	InitGraph(&graph, 6);
	InsertVertex(&graph, 'a'); // 0
	InsertVertex(&graph, 'b'); // 1
	InsertVertex(&graph, 'c'); // 2
	InsertVertex(&graph, 'd'); // 3
	InsertVertex(&graph, 'e'); // 4
	InsertVertex(&graph, 'f'); // 5

	InsertEdge(&graph, 0, 5, 13);
	InsertEdge(&graph, 0, 1, 9);
	InsertEdge(&graph, 0, 2, 7);
	InsertEdge(&graph, 0, 3, 8);
	InsertEdge(&graph, 1, 5, 17);
	InsertEdge(&graph, 1, 4, 12);
	InsertEdge(&graph, 4, 5, 18);
	InsertEdge(&graph, 2, 4, 10);
	InsertEdge(&graph, 2, 3, 5);
	InsertEdge(&graph, 3, 4, 24);

	//ShowMatrix(&graph);
	MST_Prim(&graph, 'c');
	return 0;
}
	
// 初始化图的结构
void InitGraph(MatrixGraph* Graph, int n) {
	Graph->setsOfVertex = (VertexDataType*)malloc(sizeof(VertexDataType) * n);
	Graph->AdjacencyMatrix = (EdgeWeightDataType**)malloc(sizeof(int*) * n);
	for (int i = 0; i < n; i++) {
		Graph->AdjacencyMatrix[i] = (EdgeWeightDataType*)malloc(sizeof(EdgeWeightDataType) * n);
	}
	if (Graph->AdjacencyMatrix == NULL) {
		exit(0);
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			Graph->AdjacencyMatrix[i][j] = 2147483647;
		}
	}

	Graph->flag = (closedge*)malloc(sizeof(closedge) * n);
	Graph->numsOfEdge = 0;
	Graph->numsOfVertex = 0;
	Graph->MaxSizeCnt = n;
}

// 在图中插入顶点
void InsertVertex(MatrixGraph* Graph, VertexDataType vertex) {
	int i = Graph->numsOfVertex;
	if (i < Graph->MaxSizeCnt) {
		Graph->setsOfVertex[i] = vertex;
		(Graph->numsOfVertex)++;
	}
}

// 添加顶点间的联系
void InsertEdge(MatrixGraph* Graph, int v1, int v2, EdgeWeightDataType weight) {
	Graph->AdjacencyMatrix[v1][v2] = weight;
	Graph->AdjacencyMatrix[v2][v1] = weight;
	Graph->numsOfEdge++;
}

// 显示图的邻接矩阵表示
void ShowMatrix(MatrixGraph* Graph) {
	printf("\n\n\n");
	for (int i = 0; i < Graph->numsOfVertex; i++) {
		printf("       [ ");
		for (int j = 0; j < Graph->numsOfVertex; j++) {
			if (j != Graph->numsOfVertex - 1) {
				printf("%02d ", Graph->AdjacencyMatrix[i][j]);
			}
			else {
				printf("%02d ", Graph->AdjacencyMatrix[i][j]);
			}
		}
		printf("]");
		printf("\n");
	}
}

// 在邻接矩阵中寻找值为verIndex的顶点的索引
int searchVerIndex(MatrixGraph* Graph, VertexDataType verValue) {
	for (int i = 0; i < Graph->numsOfVertex; i++) {
		if (verValue == Graph->setsOfVertex[i]) {
			return i;
		}
	}

	return -1;
}

int Min(MatrixGraph* Graph) {
	int min = 100, minIndex = 0;
	for (int i = 0; i < Graph->numsOfVertex; i++) {
		if ((Graph->flag[i].lowEdgeWeight != 0) && (Graph->flag[i].lowEdgeWeight < min)) {
			min = Graph->flag[i].lowEdgeWeight;
			minIndex = i;
		}
	}

	return minIndex;
}

// 借助图的邻接矩阵来实现Prim算法
void MST_Prim(MatrixGraph* Graph, VertexDataType vertexValue) {
	MatrixGraph retGraph;
	InitGraph(&retGraph, Graph->numsOfVertex);

	int initIndex = searchVerIndex(Graph, vertexValue);

	// 初始化flag数组，以被选择的顶点作为一个单独的集合，其他的所有点看成另外一个集合
	for (int i = 0; i < Graph->numsOfVertex; i++) {
		InsertVertex(&retGraph, Graph->setsOfVertex[i]);
		if (i == initIndex) { // 所选择的点的到所选择的点无边，权值记为0
			Graph->flag[i].lowEdgeWeight = 0;
		}
		else {
			// 其他点到所被选择的点之间的权值由生成的邻接矩阵可得
			// 由于此时被选择的点为一个单独的集合，且当前状态只有
			// 其一个元素，所以其他点到的邻接矩阵到看作是被选择的
			// 点，因为我们要选择一条具有最权值的边，这条边是与当
			// 前被选择的点相邻接的
			Graph->flag[i].lowAdjVex = vertexValue;
			Graph->flag[i].lowEdgeWeight = Graph->AdjacencyMatrix[initIndex][i];
		} 
	}
	int weights = 0;
	for (int i = 1; i < Graph->numsOfVertex; i++) {
		int minWeightEdgeIndex = Min(Graph);

		// 与最小边相连的顶点值（from）
		VertexDataType vertex_0 = Graph->flag[minWeightEdgeIndex].lowAdjVex;
		// 所选择的最小边指向的顶点（to）
		VertexDataType vertex_1 = Graph->setsOfVertex[minWeightEdgeIndex];

		// 根据最优边得到所选择的两个顶点在图中的索引，重新加入到所要构造的最小生成树中
		int i_1 = searchVerIndex(Graph, vertex_0);
		int i_2 = searchVerIndex(Graph, vertex_1);

		// 逐步构造最小生成树
		InsertEdge(&retGraph, i_1, i_2, Graph->flag[minWeightEdgeIndex].lowEdgeWeight);
		// 累计每次选择的最优边的权值
		weights += Graph->flag[minWeightEdgeIndex].lowEdgeWeight;

		printf("The %d times two vertices selected are：%c %c\n", i, vertex_0, vertex_1);
		(Graph->flag)[minWeightEdgeIndex].lowEdgeWeight = 0;
		// 以当前选择的最小权值的边指向的顶点为基准，更新flag数组
		for (int i = 0; i < Graph->numsOfVertex; i++) {
			int edge_0 = Graph->AdjacencyMatrix[minWeightEdgeIndex][i];
			int edge_1 = Graph->flag[i].lowEdgeWeight;
			if (edge_0 < edge_1) { 
				/*              ----更新flag数组----
				 与基准作比较，如果基准值小于flag数组中储存着的到相应顶点的权值，则
				 更新flag数组中到相应的顶点的最小权值(由贪心思想可知，flag数组储存
				 的是已构造出的部分最小生成树中到未被选择的顶点的最小权值）为基准值
				 */
				(Graph->flag)[i].lowAdjVex = vertex_1;
				(Graph->flag)[i].lowEdgeWeight = edge_0;
			}
		}
	}
	printf("\n");
	// 打印最小生成树的邻接矩阵
	printf("MST generated with Prim is：\n");
	for (int i = 0; i < retGraph.numsOfVertex; i++) {
		for (int j = 0; j < retGraph.numsOfVertex; j++) {
			if (j == 0) {
				printf("\t   [");
			}
			if (retGraph.AdjacencyMatrix[i][j] == 2147483647) {
				// 不直接连通的两个点：简化其之间的权值
				printf("00 ");
			}
			else {
				printf("%02d ", retGraph.AdjacencyMatrix[i][j]);
				
			}
			if (j == retGraph.numsOfVertex - 1) {
				printf("]");
			}
			
		}
		printf("\n");
	}
	printf("Minimum Cost Spanning is: %d", weights);
}

如果你已经解决了该问题, 非常希望你能够分享一下解决方案, 写成博客, 将相关链接放在评论区, 以帮助更多的人 ^-^

//方式一：使用二级指针
//供外部调用
void CreateBinTree_1(BinTree *bt)
{
    CreateBinTree_1(bt,&(bt->root));
}
//内部实现
void CreateBinTree_1(BinTree *bt, BinTreeNode **t)
{
    ElemType Item; //接收数据
    scanf("%c",&Item);
    if(Item == bt->refvalue) //判断输入是否为一个结束标记
        (*t) = NULL;//是 说明这棵二叉树是空树
    else
    {//否
        //创建树（子树）根结点
        (*t) = (BinTreeNode*)malloc(sizeof(BinTreeNode));
        assert((*t) != NULL);
        (*t)->data = Item;//为结点赋值
        CreateBinTree_1(bt,&((*t)->leftChild)); //创建左子树
        CreateBinTree_1(bt,&((*t)->rightChild)); //创建右子树
    }
}


//方式二：使用指针引用方式
//对外调用
void CreateBinTree_2(BinTree *bt)
{
    CreateBinTree_2(bt,bt->root);
}
//内部实现
void CreateBinTree_2(BinTree *bt, BinTreeNode *&t)
{
    ElemType Item;//接收数据
    scanf("%c",&Item);
    if(Item == bt->refvalue)//判断输入是否为一个结束标记
        t = NULL;//是 说明这棵二叉树是空树
    else
    {//否
        //创建树（子树）根结点
        t = (BinTreeNode*)malloc(sizeof(BinTreeNode));
        assert(t != NULL);
        t->data = Item;//为结点赋值
        CreateBinTree_2(bt,t->leftChild); //创建左子树
        CreateBinTree_2(bt,t->rightChild); //创建右子树
    }
}