在二叉樹中插入4或5個數字，但在輸出中只得到3個數字

這是學校處理遞歸和二叉樹實驗的一部分。如果我去插入4或5個數字並輸出結果，我只返回3個數字。下面是插入代碼：在二叉樹中插入4或5個數字，但在輸出中只得到3個數字

Node *insert(Node *t, int key) { 
    Node *insertParent; 
    Node *result=NULL; 

    if (t!=NULL) { 
     result=search(t,key,insertParent); 
    } else { 
     t=new Node; 
     t->data=key; 
     t->leftchild=NULL; 
     t->rightchild=NULL; 
     return t; 
    } 

    if (result==NULL) { 
     if (insertParent->data>key) { 
      insertParent->leftchild=new Node; 
      insertParent->leftchild->data=key; 
      insertParent->leftchild->leftchild=NULL; 
      insertParent->leftchild->rightchild=NULL; 
      return insertParent->leftchild; 
     } else if (insertParent->data<key) { 
      insertParent->rightchild=new Node; 
      insertParent->rightchild->data=key; 
      insertParent->rightchild->leftchild=NULL; 
      insertParent->rightchild->rightchild=NULL; 
      return insertParent->rightchild; 
     } 
    } else 
     return NULL; 
}

但我相信麻煩的是搜索功能中，特別通過引用父節點指針：

Node* search(Node *t, int key, Node *&parent) { 
    if (t!=NULL) { 
     parent=t; 
     if (t->data==key) 
      return t; 
     else if (t->data>key) 
      return search(t->leftchild,key,t); 
     else 
      return search(t->rightchild,key,t); 
    } else 
     return NULL; 
}

我有輸出樹的功能，並有檢查了一棵樹我手動建成並正常工作：

void inorder(Node *t) 
{ 
    if (t!=NULL) { 
     if (t->leftchild!=NULL) 
      inorder(t->leftchild); 

     cout << t->data << ", "; 

     if (t->rightchild!=NULL) 
      inorder(t->rightchild);      
    } 
}

不找只是尋找一個區域，我應該看一個答案。

來源

2011-11-29 aaron burns

所以我發現我的問題是與搜索功能。它確實與引用父節點變量有關。我不得不使用四個else/ifelse語句來遞歸或不遞歸地決定走哪條路。

Node* search(Node *t, int key, Node *&parent) { 
    if (t!=NULL) { 
     if (t->data==key) { 
      parent=NULL; 
      return t; 
     } else if (t->data>key && t->leftchild!=NULL) { 
      return search(t->leftchild,key,parent); // think this needs returned 
     } else if (t->data>key && t->leftchild==NULL) { 
      parent=t; 
      return NULL; 
     } else if (t->data<key && t->rightchild!=NULL) { 
      return search(t->rightchild,key,parent); //think this needs returned 
     } else if (t->data<key && t->rightchild==NULL) { 
      parent=t; 
      return NULL; 
     } 
    } else { 
     parent=NULL; 
     return NULL; 
    } 
}

這種變化的搜索功能在必要插入功能的變化：

Node *insert(Node *t, int key) { 
    Node *insertParent=NULL; 
    Node *result=NULL; 

    if (t!=NULL) { 
     result=search(t,key,insertParent); 
    } else { 
     t=new Node; 
     t->data=key; 
     t->leftchild=NULL; 
     t->rightchild=NULL; 
     return t; 
    } 

    if (insertParent==NULL && result!=NULL) { 
     return NULL; 
    } else if (insertParent!=NULL && result==NULL) { 
     //key not found need to add 
     if (insertParent->data>key) { 
      insertParent->leftchild=new Node; 
      insertParent->leftchild->data=key; 
      insertParent->leftchild->leftchild=NULL; 
      insertParent->leftchild->rightchild=NULL; 
      return insertParent->leftchild; 
     } else { 
      insertParent->rightchild=new Node; 
      insertParent->rightchild->data=key; 
      insertParent->rightchild->leftchild=NULL; 
      insertParent->rightchild->rightchild=NULL; 
      return insertParent->rightchild; 
     } 
    } 
}

感謝所有誰幫助...

（另外：我回答我自己的問題。這是我應該做的還是應該編輯我的文章？會認爲人們寧願看到整個過程，不要讓我刪除舊的非工作代碼...）

來源

2011-11-29 21:22:57

您應該編輯原始問題以使問題更清楚，但答案應該是獲得校驗標記的答案。如果你要回答你自己的問題，不僅要考慮「這裏是工作代碼」，而且就像你是一個試圖從閱讀討論中學習的人。由於你是新人，我已經做了一些編輯，以幫助提供一些想法與你的原創：http://stackoverflow.com/revisions/8306096/1 – HostileFork

我更新了你的答案，以顯示我在說什麼。請注意，如果你打算分享你的'inorder'打印功能，那麼你可能會提出這個問題，因爲它不是在回答過程中學到的「新東西」......所以我把它移到了題。您可以看到，在將短代碼示例與描述性文本交織在一起而不是粘貼長滾動的代碼框時，將會更加輕鬆。另外StackOverflow就像維基百科一樣，將修訂版的歷史記錄保存到問答環節中，所以事情不會丟失：http://stackoverflow.com/revisions/8317919/1 – HostileFork

您的懷疑是正確的。跟蹤深度搜索多個節點後，如何更新頂級「父」參數。

來源

2011-11-29 05:35:02 AShelly

Node* search(Node *t, int key, Node *&parent) 
{ 
    if(t!=NULL) 
    { 
    parent=t; 
    if (t->data==key) 
     return t; 

    else if (t->data>key) 
     return search(t->leftchild, key, parent); // use 「parent」 because you want to assign parent to this variable 

    else 
     return search(t->rightchild,key, parent); 
    } 
    else  return NULL; 

}

來源

2011-11-29 05:38:35 jianyi

「不尋找答案只是尋找一個區域，我應該看看。」 - 好的工作不回答。 – AShelly

@AShelly仍然不問問題在哪裏？您想要將「insertParent」分配給插入點。對？所以，你應該在遞歸二分搜索期間保留它，否則你得到錯誤的父指針。您應該看看的區域是C++的「參考」概念。 – jianyi

將父母放入t中並不能解決問題 –

在二叉樹中插入4或5個數字，但在輸出中只得到3個數字

回答

相關問題