二叉树递归查找遇到的问题。

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了二叉树递归查找遇到的问题。，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1529字，纯文字阅读大概需要3分钟。

内容图文

本以为树查找和遍历算法一摸一样，无非就是找到元素后return节点地址。但是写代码的时候还是发现有区别。
先看这个代码，这是一棵树，每一个节点有多个子节点（数目不定，不是二叉树）。树的结构如下：

class Node
{
public:
    Node(int d = 0) : data(d)
    {
        children.clear();
    }
    int data;
    vector<Node *> children;
};

为了简化操作，用了vector，反正这是一个无序的树,用vector比自己再写一个链表方便多了.
最初树的查找算法如下：

Node *find(Node *parent, int d)
{
    static bool yesfind = false;
    if (parent == nullptr)
        return nullptr;
    if (parent->data == d)
    {
        yesfind = true;
        return parent;
    }
    else
    {
        for (auto it = parent->children.begin(); it != parent->children.end(); it++)
        {
            if (yesfind == false)
            {
               find(*it, d);
            }
        }
    }
}

代码显然用了递归，变量yesfind的作用是为了在已经找到元素的情况下，避免接着执行for循环,猛一看代码没问题，但是实际执行发现，每次返回的都是根节点,单步debug发现，在递归返回的时候，因为parent每次压栈的值不一样，所以出栈的值也会不变，最后出栈的是根节点，所以每次即便找到节点，return的也不是这个节点的地址，最终都会变成root的地址，所以我们需要报讯这个return的节点地址，因此代码修改如下：

Node *find(Node *parent, int d)
{
    static bool yesfind = false;
    if (parent == nullptr)
        return nullptr;
    if (parent->data == d)
    {
        yesfind = true;
        return parent;
    }
    else
    {
        for (auto it = parent->children.begin(); it != parent->children.end(); it++)
        {
            if (yesfind == false)
            {
                Node *t = find(*it, d);
                if (t)
                    return t;
            }
        }
    }
    if (yesfind == false)
        return nullptr;
}

可以看出，我们修改了两部分：
1.修改for循环，可以保存节点地址
2.结尾添加判断yesfind,防止在没有找到节点的情况下，由于最后根节点出栈而返回根节点的地址.

内容总结

以上是互联网集市为您收集整理的二叉树递归查找遇到的问题。全部内容，希望文章能够帮你解决二叉树递归查找遇到的问题。所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---