二叉树简单实现问题解决-白红宇的个人博客

二叉树简单实现问题解决

发布日期：2021-05-07 10:44:57 浏览次数：11 分类：精选文章

本文共 1097 字，大约阅读时间需要 3 分钟。

今天终于解决了一个长时间耽搁的问题：查找父结点的功能。之前的困难主要源于两个错误的想法，最终在同学的帮助下找到了原因并加以修正。

问题分析

错误想法一：结点值为NULL的意义

在之前的理解中，我误以为树的一个结点值为NULL表示该节点不存在，或者是一个空节点，没有左、右子树，也没有数据。这种理解本身并没有问题。但是，后来我发现，这种理解导致了另一个错误。

错误想法二：结点比较的逻辑

在寻找父结点的过程中，我一直使用的是比较两个结点是否相等（即 == 运算符）。这种比较方式是错误的。正确的逻辑应该是先比较两个结点的数据是否相等，再判断是否是同一个节点。简单来说，只有数据相等并不足以说明是同一个结点。

问题根源

由于上述两个错误，我之前在寻找父结点时总是找不到正确的结点。原因在于，每次比较的结点都只是比较它们是否相等，而不是先比较数据是否相等。这样会导致即使两个结点的数据相等，但如果它们不是同一个节点，仍然无法找到正确的父结点。

解决方案

这次修改的核心是对比值的逻辑进行修正。具体来说，我在函数中增加了一层条件判断：

特殊情况处理

如果某个结点的左子结点为空，但左子结点的数据赋值给某个变量，则继续比较。这一步是为了处理一些特殊情况。

修改后的寻找父结点函数

更新后的函数逻辑如下：

BinTreeNode* BinTree::Father(BinTreeNode *t, BinTreeNode *p) {    BinTreeNode *q;    if (t == NULL || p == NULL)        return NULL;    if (t->GetLeft() != NULL) {        if ((t->GetLeft())->GetData() == p->GetData())            return t;    }    if (t->GetRight() != NULL) {        if ((t->GetRight())->GetData() == p->GetData())            return t;    }    if ((q = Father(t->GetLeft(), p)) != NULL)        return q;    else        return Father(t->GetRight(), p);}

优化后的内容

修改后的函数将比较节点的数据而非结点本身，并增加了对特殊情况的处理。这种方式可以有效解决问题，确保能够正确找到父结点。

通过上述修改，问题得以解决。

上一篇：剑指offer JZ7 斐波那契数列

下一篇：剑指offer JZ6 旋转数组的最小数字

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！