二叉树查找时输入导致崩溃该如何解决？

当左右儿子结点非空时可以正常输入
但是一旦进行到输入‘-’也就是左右儿子有空结点的时候就会崩溃
是递归出错了吗？

#include <iostream>

using namespace std;

struct tree
{
    char data;
    int num;
    tree* lchild;
    tree* rchild;
};

bool Isomorphic(tree* t1, tree* t2);
void CreateTree(tree* p, char a, char b, char c);
tree* seek(tree* p, int i);

int main()
{
    tree* root1 = new tree;
    tree* root2 = new tree;
    root1->num = 0;
    root2->num = 0;
    int m, n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        char a, b, c;
        cin >> a >> b >> c;
        CreateTree(seek(root1, i), a, b, c);
    }
    cin >> m;
    for (int i = 0; i < m; i++) {
        char a, b, c;
        cin >> a >> b >> c;
        CreateTree(seek(root2, i), a, b, c);
    }
    if (Isomorphic(root1, root2))
        cout << "YES" << endl;
    else
        cout << "NO" << endl;
    delete root1;
    delete root2;
    return 0;
}

bool Isomorphic(tree* t1, tree* t2)
{
    if (t1 == nullptr && t2 == nullptr)
        return true;
    if (t1 == nullptr || t2 == nullptr)
        return false;
    if (t1->data != t2->data)
        return false;
    if (t1->lchild == nullptr && t2->lchild == nullptr)
        return Isomorphic(t1->rchild, t2->rchild);
    if (t1->lchild != nullptr && t2->lchild != nullptr && t1->lchild->data == t2->lchild->data)
        return Isomorphic(t1->lchild, t2->lchild) && Isomorphic(t1->rchild, t2->rchild);
    else
        return Isomorphic(t1->lchild, t2->rchild) && Isomorphic(t1->rchild, t2->lchild);
}

void CreateTree(tree* p, char a, char b, char c)
{
    p->data = a;
    p->lchild = nullptr;
    p->rchild = nullptr;
    if (b != '-') {
        p->lchild = new tree;
        p->lchild->num = b - '0';
    }
    if (c != '-') {
        p->rchild = new tree;
        p->rchild->num = c - '0';
    }
}

tree* seek(tree* p, int i)
{
    tree* tmp;
    if (p == nullptr)
        return nullptr;
    if (p->num == i)
        return p;
    tmp = seek(p->lchild, i);
    if (tmp != nullptr)
        return tmp;
    else
        return seek(p->rchild, i);
}

这是一个递归实现的二叉树构造和同构判断的程序。出现崩溃的原因很有可能是递归调用栈溢出。
当输入包含很多层的空左右子节点时,如 A - - B - - C - -,递归函数会一直调用自己来构造这棵深度很大的树,最终导致栈溢出崩溃。
要解决这个问题,有两种方法:

1. 限制递归调用的最大深度。在递归函数中增加一个深度参数,每调用一次递归函数深度+1,如果超过某个阈值就直接返回,避免过深递归。
2. 采用非递归方式实现,使用栈代替递归调用栈。不断将左右子节点推入栈中,直到栈为空。这可以有效控制调用栈的深度,避免溢出。以下是方法2的实现:

bool Isomorphic(tree* t1, tree* t2) 
{ 
    stack<tree*> s1, s2;
    s1.push(t1);
    s2.push(t2);
    while (!s1.empty() && !s2.empty()) {
        tree* p1 = s1.top(); s1.pop();
        tree* p2 = s2.top(); s2.pop();
        if (p1 == nullptr && p2 == nullptr) continue;
        if (p1 == nullptr || p2 == nullptr) return false;
        if (p1->data != p2->data) return false;
        
        s1.push(p1->lchild);
        s2.push(p2->lchild);
        s1.push(p1->rchild);
        s2.push(p2->rchild);
    }
    return s1.empty() && s2.empty();
}

这种 non-recursive 的实现方式通过栈来控制函数调用,避免了过深递归导致的栈溢出问题。

不知道你这个问题是否已经解决, 如果还没有解决的话:

• 帮你找了个相似的问题, 你可以看下: https://ask.csdn.net/questions/7796464
• 这篇博客也不错, 你可以看下输出二叉树中从每个叶子结点到根结点的路径
• 除此之外, 这篇博客: 红黑树 都可以这么细？面试官还能怎么说.中的 头节点指向的左右节点： 部分也许能够解决你的问题, 你可以仔细阅读以下内容或者直接跳转源博客中阅读:
  

  如图：header头节点指向最左最右的节点；
  

• 您还可以看一下 Abel小智老师的嵌入式开发系统学习路线 从基础到项目 精品教程 工程师必备课程 物联网课程中的 课程介绍小节, 巩固相关知识点
  
• 以下回答来自chatgpt:

  问题分析：

  根据参考资料，这个问题跟二叉树查找算法没有太大关系，而是针对一个链表分类的问题。对于输入'-'导致的程序崩溃问题，需要定位具体的代码和错误提示才能进行修复。

  解决方案：

  1.定位错误代码和错误提示：根据具体的错误提示，查看代码中相应的位置，定位问题出现的地方。

  2.增加异常处理机制：对于输入'-'的情况，可以通过增加异常处理机制来避免程序崩溃。例如，在读取输入时，判断输入是否为'-'，如果是则跳过不处理。具体代码如下：

  if (scanf("%d", &node->value) != 1) {
    scanf("%*c");  // 跳过'-'的输入
    node->left = NULL;
    node->right = NULL;
  } else {
    node->left = create_node();
    node->right = create_node();
    read_node(node->left);
    read_node(node->right);
  }
  

  3.调试递归实现：如果问题确实是递归实现导致的，可以添加调试信息来帮助定位问题。例如，输出递归函数参数的值，查看是否有异常情况出现。

  4.参考他人的代码：如果以上方法均不能解决问题，可以参考其他人的代码，看看是否有思路可以借鉴。

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