バイナリツリーの親ノード関数を見つける

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

私は今この検索機能を持っています。私は実際にそこからそれを得た。だから、これをノードの親を検索するように変換しようとしています。パラメータはルートノードと親が必要なノードになります。それも可能ですか？ 私はコードを投稿するためのヒントが必要です。この機能を作成する目的は、ほぼ完全に機能する葉ノードの削除機能があるためです。唯一の問題は、削除後にすべてのノードを印刷すると、おそらく削除されたノードが表示されることです。親ノードがまだメインノードにリンクされているからです。ここに私の削除リーフノード機能です：私は誰かに意味を作ってるんだ願ってい

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ファイル：あなたのBinaryTreeの実装に依存

#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

。あなたは彼の親に、各ノード内の参照を保存しない場合

編集を削除するときに私の知る限り見るように、あなたはそれに直接アクセスすることはできません

あなたがして、あなたのBinaryTreeクラスを変更することができます。

あなた .cppで次に

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

：

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