迭代插入到二叉樹

Question

我在StackOverflow中遇到了一些線程，但沒有一個能清除我的疑惑。

所以問題很簡單。我需要迭代地將元素插入到二叉樹中。這是我的代碼。

BST newNode(int x) 
{ 
    BSTNodePtr node = (BSTNodePtr) malloc(sizeof(struct TreeNode)); 
    node->Element = x; 
    node->Left = NULL; 
    node->Right = NULL; 

    return node; 

} 

BST Insert(int x, BST T) 
{ 
    BST temp_node = T; 
    while(T != NULL) { 
     if (x < T->Element) 
      T = T->Left; 
     else if (x >= T->Element) 
      T = T->Right; 
    } 

    T = newNode(x); 

    return temp_node; 

} 

然而，當我發現這棵樹，我總是得到0高度代碼的高度

int Height(BST T) 
{ 
    if (T == NULL) 
     return 0; 

    return 1+(max(Height(T->Left), Height(T->Right))); 
} 

當我做插入遞歸這工作完全正常（使用函數具有完全相同的簽名）

我錯過了什麼？

Answer 1

解決不了這個問題。然而，這個代碼似乎工作。

BST Insert(int x, BST T) 
    { 
     BST temp=T; 
     BST node=(BST)malloc(sizeof(struct TreeNode)); 
     node->Element=x; 
     node->Left=NULL; 
     node->Right=NULL; 
     if (T==NULL) 
     { 
      T=node; 
      return(T); 
      //printf("%d\n",T->Element); 
     } 
     else 
     { 
      while(1) 
      { 
       if (temp->Element>=node->Element && temp->Left==NULL) 
       { 
        temp->Left=node; 
        break; 
       } 
       else if (temp->Element>=node->Element && temp->Left!=NULL) 
       { 

        temp=temp->Left; 
       } 
       else if (temp->Element<node->Element && temp->Right==NULL) 
       { 
        temp->Right=node; 
        break; 
       } 
       else 
       { 
        temp=temp->Right; 
       } 
      } 
       return(T); 
     }    
    } 

Answer 2

你的插入功能有問題。正如我可以假設，最初你的樹是空的。所以第一次插入節點時，第二個參數是NULL，對吧？然後這個函數總是返回NULL，因爲你總是傳遞一個NULL值。

Answer 3

這裏：

BST Insert(int x, BST T) 
{ 
    BST temp_node = T; 
    while(T != NULL) { 
     if (x < T->Element) 
      T = T->Left; 
     else if (x >= T->Element) 
      T = T->Right; 
    } 

    T = newNode(x); 

    return temp_node; 

} 

您瀏覽樹，直到你打T == NULL。然後創建一個節點並將其指針指向T。然後你返回原始值T。你根本不修改你的樹。它中沒有任何節點指向新創建的節點。 T只是一個局部變量。

Answer 4

這裏是我實施上述問題：

bst* newNode(int x) 
{ 
    bst* T = new bst; 
    T->value = x; 
    T->left_child = T->right_child = NULL; 
    return T; 
} 

bst* bst_insert_iter(bst* T,int val) 
{ 
    if (T == NULL) 
     T = newNode(val); 

    else 
    { 

    bst *temp_node = T; 

    bool flag = true; 

    while(flag) 
    { 
     if (val <= temp_node->value) 
     { 
      if (temp_node->left_child == NULL) 
      { 
       temp_node->left_child=newNode(val); 
       flag = false; 
      } 
      else 
       temp_node = temp_node->left_child; 
     } 

     else 
     { 
      if (temp_node->right_child == NULL) 
      { 
       temp_node->right_child=newNode(val); 
       flag = false; 
      } 
      else 
       temp_node = temp_node->right_child; 
     } 
    } 

    } 
    return T; 
} 

Answer 5

template <class T> 
class TreeNode{ 
private: 
    T data; 
    TreeNode<T>* right,*left; 
public: 
void setData(T d){ 
    this->data =d; 
} 
T getData(){ 
    return this->data; 
} 
void setRight(TreeNode<T>* r){ 
    this->right =r; 
} 
TreeNode<T>* getRight(){ 
    return this->right; 
} 
void setLeft(TreeNode<T>* r){ 
    this->left =r; 
} 
TreeNode<T>* getLeft(){ 
    return this->left; 
} 
static TreeNode<T>* newNode(T data){ 
    TreeNode<T>* n = new TreeNode<T>(); 
    n->setData(data); 
    n->setRight(NULL); 
    n->setLeft(NULL); 
    return n; 
} 
}; 



template <class T> 
class BinaryTree{ 
private: 
     TreeNode<T>* root; 
public: 
    void insert(T data){ 
     TreeNode<T>* n = TreeNode<T>::newNode(data); 

     if(root==NULL) 
      root = n; 
     else{ 
     TreeNode<T>* t = root; 
     while(t!=NULL){ 

      if(n->getData() >= t->getData()){ 
       if(t->getRight()==NULL){ 
        t->setRight(n); //newnode attached as right child in tree 
        t = NULL; 
       } 
       else 
        t = t->getRight(); 
      } 
      else{ 
       if(t->getLeft()==NULL){ 
        t->setLeft(n); //newnode attached as left child in tree 
        t=NULL; 
       } 
       else 
        t = t->getLeft(); 
      } 
     } 

     } 

    } 

    void preorder(){ 
     TreeNode<T>* t = root; 
     preorderUtil(t); 
    } 

    void preorderUtil(TreeNode<T>* node){ 
     if(node==NULL) 
      return; 
     preorderUtil(node->getLeft()); 
     cout<<node->getData()<<" "; 
     preorderUtil(node->getRight()); 
    } 
}; 

所做的更改不會反映在樹。我按照這種方式迭代插入數據，並且工作正常。重點是在您的二進制樹內創建一個節點，以便將新創建的節點指向它，使其連接到樹。

Answer 6

這是我的版本，它似乎工作。

struct tree{ 
tree *left; 
tree *right; 
int key; 
}; 
void insertBst(int k,tree *t) 
{ 
    tree *newK = new tree[sizeof(tree)]; 
    newK->key = k; 
    newK->left = NULL; 
    newK->right = NULL; 
    if((t)->key == NULL) 
    { 
     t=newK; 
     return; 
    } 
    else{ 
     bool found = false; 
     tree *root = t; 
     tree *parent = NULL; 
     while(root != NULL) 
     { 
     parent = root; 
      if(root->key < newK->key) 
      { 
       root=root->right; 
      } 
      else if(root->key > newK->key) 
      { 
       root=root->left; 
      } 
      else{ 
      //Here we have duplicates!! so do nothing 
      root = root; 
      } 
     } 
     if(parent->key > newK->key) parent->left = newK; 
     else parent->right = newK; 
    } 

}