要素をBinaryTreeに再帰的に挿入する

Question

次のメソッドを再帰的に書き込んで、ノードをバイナリツリーに挿入しようとしました。戦略は、基本的にNULLの左または右ポインタにノードを挿入することでした。主な機能

InsertElementInBinaryTree(&root , new BinaryTreeNode{8, NULL,NULL});

問題は、私はエラーが再帰であると考えているように、この呼び出しは常に、セグメンテーションフォールトエラーを返すことで、以下のように

typedef struct BinaryTreeNode { 
int data; 
BinaryTreeNode * left; 
BinaryTreeNode * right; 
} BinaryTreeNode; 

void InsertElementInBinaryTree(BinaryTreeNode *root, BinaryTreeNode *element) { 
    if(root) { 
     if(root -> left == NULL) root -> left = element; 
     else if(root -> right == NULL) root -> right = element; 
     InsertElementInBinaryTree(root -> left, element); 
     InsertElementInBinaryTree(root -> right, element); 
    } 
} 

メソッドが呼ばれているのですか？

Answer 1

あなたはいくつかの条件が欠けている：

 if (root->data > element->data) { 
     if (root->left == NULL) { 
      root->left = element; 
     } else { 
      InsertElementInBinaryTree(root->left, element); 
     } 
    } else { 
     if (root->right == NULL) { 
      root->right = element; 
     } else { 
     InsertElementInBinaryTree(root->right, element); 
      } 
    } 

Answer 2

を使用すると、任意の現在のノードのために、バイナリツリーを実装しようとしている場合は、左の部分木からのすべてのノードが現在のノードでdata、すべてのよりdata低くする必要があります右側のサブツリーからのdataが大きくなるはずです。

void InsertElementInBinaryTree(BinaryTreeNode *&root, BinaryTreeNode *element) { 
    if(root == NULL) { root = element; return;} 
    if(root -> data > element -> data) 
     InsertElementInBinaryTree(root->left, element); 
    else 
     InsertElementInBinaryTree(root->right, element); 
} 

そこで実際dataelement値がに挿入されます位置を定義します。また、rootポインタを変更するために、BinaryTreeNode *&rootを参照として渡しています。

使用法：

// declare root 
BinaryTreeNode* root; 
// insertion, no & operator before root 
InsertElementInBinaryTree(root, new BinaryTreeNode{8, NULL,NULL}); 

Answer 3

機能は次のよう

void InsertElementInBinaryTree(BinaryTreeNode * &root, int data) 
{ 
    if (root == nullptr) 
    { 
     root = new BinaryTreeNode { data, nullptr, nullptr }; 
    } 
    else if (data < root->data) 
    { 
     InsertElementInBinaryTree(root->left, data); 
    } 
    else 
    { 
     InsertElementInBinaryTree(root->right, data); 
    } 
} 

を見て、

InsertElementInBinaryTree(root , 8); 

とオブジェクトrootが

01のように最初に定義する必要があるように呼ばれることができます