C ++
 Computer >> コンピューター >  >> プログラミング >> C ++

C ++で値kのリーフノードを削除しますか?


まず、データとその左右のノードの子を含むツリーノードを表す構造体を定義しましょう。これが最初に作成されるノードの場合はルートノード、それ以外の場合は子ノードです。

struct Node {
   int data;
   struct Node *leftChild, *rightChild;
};

次に、int値を取得してノードのデータメンバーに割り当てるnewNode(int data)関数を作成します。この関数は、作成された構造体ノードへのポインターを返します。また、新しく作成されたノードの左右の子はnullに設定されます。

struct Node* newNode(int data) {
   struct Node* newNode = new Node;
   newNode->data = data;
   newNode->leftChild = newNode->rightChild = NULL;
   return (newNode);
}

次に、ルートノードと削除するノードのデータ値を取得するdeleteNode(Node * root、int k)関数を作成します。指定されたノードが親ノードである場合、その左右の子も削除されます。この関数は、指定されたノードを削除した後、変更されたルートノードを返します。

Node* deleteLeafNode(Node* root, int k) {
   if (root == NULL)
      return nullptr;
   root->leftChild = deleteLeafNode(root->leftChild, k);
   root->rightChild = deleteLeafNode(root->rightChild, k);
   if (root->data == k && root->leftChild == NULL &&
      root->rightChild == NULL)
      return nullptr;
   return root;
}

最後に、削除後にツリーを支払うために、inorder関数でツリーをトラバースする関数inorder(Node * root)があります。

void inorder(Node* root){
   if (root != NULL){
      inorder(root->leftChild);
      inorder(root->rightChild);
      cout << root->data << " ";
   }
}

値kを持つリーフノードを削除する次の実装を見てみましょう。

#include <iostream>
using namespace std;
struct Node {
   int data;
   struct Node *leftChild, *rightChild;
};
struct Node* newNode(int data){
   struct Node* newNode = new Node;
   newNode->data = data;
   newNode->leftChild = newNode->rightChild = NULL;
   return (newNode);
}
Node* deleteLeafNode(Node* root, int k){
   if (root == NULL)
      return nullptr;
   root->leftChild = deleteLeafNode(root->leftChild, k);
   root->rightChild = deleteLeafNode(root->rightChild, k);
   if (root->data == k && root->leftChild == NULL &&
   root->rightChild == NULL)
      return nullptr;
   return root;
}
void inorder(Node* root){
   if (root != NULL){
      inorder(root->leftChild);
      inorder(root->rightChild);
      cout << root->data << " ";
   }
}
int main(void){
   struct Node* root = newNode(6);
   root->leftChild = newNode(7);
   root->rightChild = newNode(7);
   root->leftChild->leftChild = newNode(5);
   root->leftChild->rightChild = newNode(3);
   root->rightChild->rightChild = newNode(7);
   deleteLeafNode(root, 7);
   cout << "Inorder traversal after deleting given leaf node: ";
   inorder(root);
   return 0;
}

出力

上記のコードは次の出力を生成します-

Inorder traversal after deleting given leaf node: 5 3 7 6

  1. C++の二分探索木で最小値のノードを見つけます

    1つの二分探索木があるとします。二分探索木で最小要素を見つける必要があります。したがって、BSTが以下のような場合- 最小要素は1になります。 左のサブツリーは常に小さい要素を保持していることがわかっています。したがって、左がnullになるまで左のサブツリーを何度もトラバースすると、最小の要素を見つけることができます。 例 #include<iostream> using namespace std; class node{    public:       node *left;      

  2. Xとの絶対差がC++で最大値を与えるノードを見つけます

    ツリーがあり、すべてのノードの重みと整数xがあるとします。 | weight [i]--x|となるようなノードiを見つける必要があります。最小です。グラフが以下のようで、x =15 出力は3になります。ノードごとに次のようになります ノード1、| 5 – 15 | =10 ノード2、| 10 – 15 | =5 ノード3、| 11 – 15 | =4 ノード4、| 8 – 15 | =7 ノード5、| 6 – 15 | =9 アイデアは単純です。ツリーでDFSを実行し、ノードの追跡を行います。ノードのxとの重み付き絶対差が最小値を示します 例 #include