二叉搜索樹，如何將節點連接到根？

Question

#include "stdafx.h" 
#include <iostream> 
using namespace std; 

struct node 
{ 
    int element; 
    node *left; 
    node *right; 
    int height=-1; 
}; 


struct BST 
{ 
    bool isSameRoot=true; 
    int hight=0; 
    node* root=NULL ; 
    void addElement(int n); 
    void insert(node* Node,int number); 
    void preorder(node* p); 

}; 

void BST::addElement(int n) 
{ 
    insert(root, n); 
    cout << "Adding" << endl; 
} 


void BST::insert(node* p,int n) 
{ 
    if (p == NULL) 
    { 
     p = new node; 
     p->element = n; 
     p->left = NULL; 
     p->right = NULL; 

     if (isSameRoot)// To skip one of the iterations; 
     { 
      hight++; 
     } 
     isSameRoot = !isSameRoot; 
     p->height = hight; 
     cout << "Element is Added:: " << n<<endl; 
     cout << "HEIGHT==: " <<p->height<<endl ; 
    } 
    else 
    { 
     if (n<p->element) 
     { 
      insert(p->left, n); 
     } 
     else if (n>p->element) 
     { 
      insert(p->right, n); 
     } 
    } 
} 

void preorder(node* p) 
{ 
    while (p != NULL) 
    { 
     cout << p->element << endl; 
     preorder(p->left); 
     preorder(p->right); 
    } 
} 

int main() 
{ 
    BST* tree=new BST ; 

    tree->addElement(8); 
    tree->addElement(9); 
    tree->addElement(45); 
    tree->addElement(25); 
    tree->addElement(97); 
    tree->addElement(78); 

    preorder(tree->root);//Here is the disease; 

    return 0; 
} 

我的問題可能非常基本但很重要;

很顯然，在BST中我們應該將每個節點連接到根節點;

你可以看看我的代碼，並告訴我如何解決這個問題;

直到preorder()方法，一切正常/看起來不錯;

我只是沒有使用單根節點;

這是我的問題; 我該如何將節點連接到根節點;

Answer 1

如果你的目標是增量生成一個BST，然後用遍歷轉儲它的內容，你甚至不需要將節點連接到他們的父母或根，也不需要跟蹤高度或'hight'[原文如此]的節點。

你的問題是你根本沒有建立你的樹。在您插入NULL節點時，您只能設置一個臨時指針指向新節點。 C++通過值傳遞參數，而不是引用，所以你認爲你在BST中設置的'p'只是BST根的臨時副本，並且在BST :: insert調用結束時它會丟失（並泄漏） 。

這就是說，這裏是一些其他方面的建議：

• 您可以在插入（...）調用傳遞（遞歸遞增）身高指數，而不是將其存儲在節點。
• 在BST :: addElement（int n）而不是BST :: insert（...）調用中執行插入的NULL檢查/節點創建，因爲null情況應該只發生在第一次插入到樹上，無論如何，這隻能發生在最初的addElement上。
• isSameRoot變量看起來像一個不必要的破解。

編輯：我覺得無聊。這裏是你的作業答案，請給予好評，並接受我的回答，我可以用懸賞一些信譽爲我自己的問題...

struct node { 
    int element; 
    node *left; 
    node *right; 
    node(int n = 0) : element(n), left(NULL), right(NULL) { } 
}; 

struct BST{ 
    node *root = NULL;  
    void addElement(int n); 
    void insert(node &Node, int number); 
    void preorder(node *p); 
}; 

void BST::addElement(int n) { 
    if (!root) { root = new node(n); } 
    else  { insert(*root, n); } 
} 

void BST::insert(node &p, int n) { 
    if (n < p.element) { 
    if (!p.left) { p.left = new node(n); } 
    else   { insert(*(p.left), n); } 
    } 
    else if (n > p.element) { 
    if (!p.right) { p.right = new node(n); } 
    else   { insert(*(p.right), n); } 
    } 
} 

void preorder(node *p) { 
    if (!p) { return; } 

    cout << p->element << endl; 
    preorder(p->left); 
    preorder(p->right); 
} 

Answer 2

你正在做（p！= NULL） - 卡在無限循環中。如果（p！= null）。