почему я получаю разные выходные данные, когда я в основном скопировал код? (удаление узла и замена на самый глубокий узел) - PullRequest
0 голосов
/ 09 мая 2019

Я пытаюсь удалить и заменить узел с самым глубоким узлом, но моя программа только удаляет узел.

Я изучил код, который я нашел в Интернете, и скопировал код, но я получаю другой вывод, чеморигинальная программа.

оригинальный вывод:

Inorder traversal before deletion : 7 11 12 10 15 9 8 
Inorder traversal after deletion : 7 8 12 10 15 9 

моя программа:

Inorder traversal before deletion : 7 11 12 10 15 9 8 
Inorder traversal after deletion : 7 12 10 15 9 8

Мне нужна помощь в понимании, почему это так?и как это исправить?.

оригинальная программа -> https://www.geeksforgeeks.org/deletion-binary-tree/

моя программа

#include<bits/stdc++.h>
using namespace std;

struct Node 
{
int key;
struct Node* left;
struct Node* right;
};

struct Node* newNode(int key)
{
struct Node* temp= new Node;
temp->key=key;
temp->left=temp->right=NULL;
return temp;
}

void inorder(struct Node* temp)
{
if(!temp)
return;

inorder(temp->left);
cout<<temp->key<<" ";
inorder(temp->right);
}

void deletDeepest(struct Node* root,struct Node* d_node)
{
queue <struct Node*>  q;
q.push(root);
struct Node* temp;
while(!q.empty())
{
temp = q.front();
q.pop();

if(temp==d_node)
{
temp=NULL;
delete(d_node);
return;
}
if(temp->right)
{
if(temp->right==d_node)
{
temp->right=NULL;
delete(d_node);
return;
}
else 
q.push(temp->right);
}
if(temp->left)
{
if(temp->left==d_node)
{
temp->left=NULL;
delete(d_node);
return;
}
else 
q.push(temp->left);
}

}
}

void deletion(struct Node* root, int key)
{
struct Node* temp;
struct Node* key_node=NULL;
queue <struct Node*> q;
q.push(root);
while(!q.empty())
{
temp=q.front();
q.pop();

if(temp->key==key)
key_node=temp;

if(temp->right)
q.push(temp->right);

if(temp->left)
q.push(temp->left);
}

int x = temp->key;
deletDeepest(root,temp);
key_node->key=x;
}

int main()
{
    struct Node* root = newNode(10); 
    root->left = newNode(11); 
    root->left->left = newNode(7); 
    root->left->right = newNode(12); 
    root->right = newNode(9); 
    root->right->left = newNode(15); 
    root->right->right = newNode(8); 

    cout << "Inorder traversal before deletion : "; 
    inorder(root); 

    int key = 11; 
    deletion(root, key); 

    cout << endl; 
    cout << "Inorder traversal after deletion : "; 
    inorder(root); 

    return 0;
}

1 Ответ

0 голосов
/ 09 мая 2019

Нетрадиционный порядок:

if(temp->right)
q.push(temp->right);

if(temp->left)
q.push(temp->left);
}

Глядя на оригинал, он также отличается от оригинала.

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...