首页 文章

为了穿过左螺纹BST，顺序进入无限循环

提问于
浏览 次
0

我有一个左线程BST，我想要遍历并打印一行中每个节点的一些数据 . 我使用下面的方法，但它卡在第一个和第二个显示的节点之间 . 让我们看看代码：

void InOrder(thnode *root) {
thnode *p = root;
if (p->left)
    InOrder(p->left);
cout << p->info << ",";
if (p->left) cout << p->left->info << ",";
else cout << "null,";
if (p->lthread)cout << "T" << endl;
else cout << "F" << endl;
if (p->right)
    InOrder(p->right);
}

输出：

-1,null,T  
0,-1,F  
-1,null,T  
0,-1,F  
.  
.  
.

这是一个程序，其中获取一个字符串并一个接一个地添加节点，并从字符串从左到右添加节点 . 示例输入：
8,3,5,2,9,0,-1,12,1,7,23,14 主要方法使用以下方法分析输入和添加节点：

void MakeThreadedBST(int x) {
thnode *p, *q;
p = new thnode;
p->info = x;
p->left = p->right = NULL;
p->lthread = true;
if (Root == NULL) Root = p;
else {
    q = Root;
    while (1) {
        if (p->info < q->info) {
            if (q->lthread) {
                p->left = q->left;
                q->left = p;
                q->lthread = false;
                break;
            } else
                q = q->left;
        } else {
            if (!q->right) {
                q->right = p;
                p->left = q;
                break;
            } else
                q = q->right;
        }
    }
}
}

并且在添加所有节点后，我调用了 InOrder 方法，但它只是在树的顺序遍历中打印了两个第一个节点，如前所述 .

c++ data-structures binary-search-tree

2 回答

  • 2

    看看这段代码：

    q->right = p;
            p->left = q;

    每当您将节点 p 作为现有节点 q 的右子节点时，将 p->left 设置为指向其父节点 q ，而不是其左子树（仅为空） . 所以你最终得到一个循环：从 q 向右移动到达 p ，然后从 p 向左移动，再次到达 q . 所以你的树不是一棵树，当你试着像它一样走路时，你最终会被困在那个周期中 .

    当然，这可能不是您代码中唯一的错误，但它是导致您询问的错误的错误 .

    回复于
  • 0

    我修改了Inorder遍历方法，将 if(p->left) 编辑为 if (!p->lthread) 并修复成功:)

    void InOrder(thnode *root) {
thnode *p = root;
if (!p->lthread)
    InOrder(p->left);
cout << p->info << ",";
if (p->left) cout << p->left->info << ",";
else cout << "null,";
if (p->lthread)cout << "T" << endl;
else cout << "F" << endl;
if (p->right)
    InOrder(p->right);
}
    回复于

相关问题