В порядке обхода левого резьбового BST попадает в бесконечный цикл - PullRequest
Новая
       8

В порядке обхода левого резьбового BST попадает в бесконечный цикл

0 голосов
/ 11 мая 2018

У меня есть 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);
}

output: 

-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 метод, но он просто печатает два первых узла впрохождение дерева по порядку, как я упоминал ранее.

Ответы [ 2 ]

0 голосов
/ 11 мая 2018

Я исправил метод обхода 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);
}
0 голосов
/ 11 мая 2018

Посмотрите на этот код: 

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

Всякий раз, когда вы размещаете узел p в качестве правого дочернего элемента существующего узла q, вы устанавливаете p->left так, чтобы он указывал на его родительский элемент q, а не на его левое поддерево (которое просто равно нулю). Таким образом, вы получаете цикл: идите направо от q и вы достигнете p, затем идите налево от p и вы снова достигнете q. Таким образом, ваше дерево - это не дерево, и когда вы пытаетесь ходить по нему, как если бы оно было, вы в конечном итоге застряли, прогуливаясь вокруг этого цикла навсегда.

Конечно, это может быть не единственная ошибка в вашем коде, но это ошибка, которая вызывает ошибку, о которой вы спрашиваете.

...