时间戳

首页 > 解决方案 > 当我基本上复制代码时，为什么会得到不同的输出？（删除节点并用最深的节点替换）

c++ - 当我基本上复制代码时，为什么会得到不同的输出？（删除节点并用最深的节点替换）

问题描述

我正在尝试用最深的节点删除和替换一个节点，但我的程序只删除了该节点。

我研究了在互联网上找到的代码并复制了代码，但我得到的输出与原始程序不同。

原始输出：

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;
}

标签： c++binary-tree

解决方案

这是一个非传统的顺序：

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

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

看原作的顺序也与原作不同。

推荐阅读