找到二叉樹的父節點函數

Question

是否可以編寫一個函數來返回二叉樹的給定節點的父節點？

BinaryTree *search_val(BinaryTree *bt, int val) 
{ 
    //temp pointer 
    BinaryTree* temp = NULL; 
    if(!bt->isEmpty()) 
    { 
     //check if root is equal to value and return root if true 
     if(bt->getData() == val) 
     { 
      return bt; 
     } 
     else 
     { 
      //search left side 
      temp = search_val(bt->left(), val); 
      //if not found in left, search right 
      if (temp == NULL) 
      { 
       temp = search_val(bt->right(), val); 
      } 
      return temp; 
     } 
     return NULL; 
    } 
    return NULL; 
} 

我剛纔有這個搜索功能。我真的從這裏得到它。所以我試圖將其轉換爲搜索節點的父節點。參數將是根節點和我們想要的父節點。這甚至有可能嗎？ 我只需要一些提示開始，然後我會發布我的代碼。創建這個函數的目的是因爲我有一個幾乎完美的刪除葉節點函數....唯一的問題是，當我刪除後打印所有節點時，所謂的刪除節點仍然出現。我確定這是因爲父節點仍然以main方式鏈接到它。這裏是我刪除葉節點功能：

void delete_leaf_node(BinaryTree *bt, int val) 
{ 
    BinaryTree *temp; 
    temp = search_val(bt, val); 
    //If node does not exist in the tree, inform the user 
    if(temp == NULL) 
    { 
     cout << "\n " << val << " was not found in the tree" << endl; 
    } 
    //Check if node is a leaf 
    else if(temp->isLeaf()) 
    { 
     delete temp; 
     cout << "\n Leaf " << temp->getData() << " deleted" << endl; 
    } 
    //Inform user that node is not a leaf 
    else 
     cout << "\n " << temp->getData() << " is not a Leaf" << endl; 
    //Display using In Order Traversal to see that the node was actually deleted  
    cout << "\n In Order Traversal after deleting: " << endl << "\n "; 
    inOrderTraverse(bt); 
    cout << endl; 
} 

我希望我做意義上的人......對不起，我試圖縮短的問題，但不能。

BinaryTree.h文件：

using namespace std; 

//BinaryTree class 
class BinaryTree{ 
    public: 
     BinaryTree(); 
     bool isEmpty(); 
     bool isLeaf(); 
     int getData(); 
     void insert(const int &DATA); 
     BinaryTree *left(); 
     BinaryTree *right(); 
     void makeLeft(BinaryTree *bt); 
     void makeRight(BinaryTree *bt); 
    private: 
     bool nullTree; 
     int treeData; 
     BinaryTree *leftTree; 
     BinaryTree *rightTree; 
}; 

BinaryTree.cpp文件：

#include <iostream> 
#include "BinaryTree.h" 

using namespace std; 

//constructor 
BinaryTree::BinaryTree() 
{ 
    nullTree = true; 
    leftTree = NULL; 
    rightTree = NULL; 
} 

/* 
    is_empty function for BinaryTree class. Does not take any parameters. 
    Returns true if tree is empty and false otherwise. 
*/ 
bool BinaryTree::isEmpty() 
{ 
    return nullTree; 
} 

/* 
    is_leaf function for BinaryTree class. Does not take any parameters. 
    Returns true if node has no children and false otherwise. 
*/ 
bool BinaryTree::isLeaf() 
{ 
    return ((this->leftTree->treeData == 0) && (this->rightTree->treeData == 0)); 
} 

/* 
    getData function for BinaryTree class. Does not take any parameters. 
    Returns treeData value. 
*/ 
int BinaryTree::getData() 
{ 
    if(!isEmpty()); 
    return treeData; 
} 

/* 
    insert function for BinaryTree class. Takes one parameter, passed by 
    reference. Returns true if node has no children and false otherwise. 
*/ 
void BinaryTree::insert(const int &DATA) 
{ 
    //create empty children and insert DATA 
    treeData = DATA; 
    if(nullTree) 
    { 
     nullTree = false; 
     leftTree = new BinaryTree; 
     rightTree = new BinaryTree; 
    } 
} 

/* 
    left function for BinaryTree class. It points to the left node. 
    Does not take any parameters. Returns left node. 
*/ 
BinaryTree *BinaryTree::left() 
{ 
    if(!isEmpty()); 
    return leftTree; 
} 

/* 
    right function for BinaryTree class. It points to the right node. 
    Does not take any parameters. Returns right node. 
*/ 
BinaryTree *BinaryTree::right() 
{ 
    if(!isEmpty()); 
    return rightTree; 
} 

/* 
    makeLeft function for BinaryTree class. Takes a pointer to a tree node as a parameter. 
    makes the parameter the left child of a node. Does not return any value 
*/ 
void BinaryTree::makeLeft(BinaryTree *bt) 
{ 
    if(!isEmpty()); 
    leftTree = bt; 
} 

/* 
    makeRight function for BinaryTree class. Takes a pointer to a tree node as a parameter. 
    makes the parameter the right child of a node. Does not return any value 
*/ 
void BinaryTree::makeRight(BinaryTree *bt) 
{ 
    if (!isEmpty()); 
    rightTree = bt; 
} 

感謝

Answer 1

這取決於你的二叉樹的實現。據我看到的，如果你沒有在每個節點內引用保存到自己的父母，你不能直接刪除

編輯時訪問它

您可以修改您的二叉樹類：

class BinaryTree{ 
    public: 
     BinaryTree(); 
     bool isEmpty(); 
     bool isLeaf(); 
     int getData(); 
     void insert(const int &DATA); 
     BinaryTree *left(); 
     BinaryTree *right(); 
     void makeLeft(BinaryTree *bt); 
     void makeRight(BinaryTree *bt); 

     void setParent(BinaryTree *parent); 
     BinaryTree* getParent(); 
    private: 
     bool nullTree; 
     int treeData; 
     BinaryTree *leftTree; 
     BinaryTree *rightTree; 

     BinaryTree* parent; 
}; 

在

那麼你.cpp：

BinaryTree::BinaryTree() 
{ 
    nullTree = true; 
    leftTree = NULL; 
    rightTree = NULL; 
    parent = NULL; 
} 

void BinaryTree::setParent(BinaryTree *parent){ 
    this->parent = parent; 
} 

BinaryTree* BinaryTree::getParent(){ 
    return parent; 
} 

你刪除功能如下所示：

void delete_leaf_node(BinaryTree *bt, int val) 
{ 
    BinaryTree *temp; 
    temp = search_val(bt, val); 
    //If node does not exist in the tree, inform the user 
    if(temp == NULL) 
    { 
     cout << "\n " << val << " was not found in the tree" << endl; 
    } 
    //Check if node is a leaf 
    else if(temp->isLeaf()) 
    { 
     // You must distinguish which child you are 
     BinaryTree* parent = temp->getParent(); 
     BinaryTree* leftChild = parent->left; 
     BinaryTree* rightChild = parent->right; 
     if(leftChild == temp){ 
      parent->left = null; 
     } 
     if(rightChild == temp){ 
      parent->right = null; 
     } 
     delete temp; 
     cout << "\n Leaf " << temp->getData() << " deleted" << endl; 
    } 
    //Inform user that node is not a leaf 
    else 
     cout << "\n " << temp->getData() << " is not a Leaf" << endl; 
    //Display using In Order Traversal to see that the node was actually deleted  
    cout << "\n In Order Traversal after deleting: " << endl << "\n "; 
    inOrderTraverse(bt); 
    cout << endl; 
}