我试图了解BST以及如何迭代地将元素插入其中.我的节点结构实现如下：
struct Node{
Node *left;
Node *right;
T data; //template class
};
我的插入实现看起来像这样：
template<typename T>
bool BST<T>::Insert(const T value)
{
Node *newNode = new Node;
newNode -> data = value;
newNode -> left = NULL;
newNode -> right = NULL;
if(root == NULL) {root = newNode;} //If the BST is empty
else
{//The BST is not empty
Node *ptr = root; //points to the current Node
Node *ptr_parent; //points to the parent Node
while(ptr != NULL)
{
if((ptr -> data) > value)
{
ptr_parent = ptr;
ptr = ptr -> left;
}
if((ptr -> data) < value)
{
ptr_parent = ptr;
ptr = ptr -> right;
}
}
}
ptr = newNode; //insert the newNode at the spot
if((ptr_parent -> data) < value)
ptr_parent -> right = newNode;
else
ptr_parent -> left = newNode;
return true;
}
将第一个节点添加到空树时插入工作,但每当我尝试添加更多节点时,我都会遇到分段错误.我知道有些帖子显示了如何在BST中实现插入,但大多数都显示了递归方法,而那些具有迭代示例的方法则不完整或过于具体.谢谢.
解决方法
我昨晚能够使我的原始代码工作,我在这里分享答案：
template<typename T>
bool BST<T>::Insert(const T value)
{
Node *ptr;
Node *ptr_parent;
if(root == NULL)
{//The BST is Empty...
Node *newNode = new Node;
newNode -> data = value;
newNode -> left = NULL;
newNode -> right = NULL;
root = newNode;
ptr = root;
} else { //traversing the tree to find the insertion point
ptr = root;
while(ptr != NULL)
{
if((ptr -> data) == value) {return false;} //to check for duplicates
if(value < (ptr -> data))
{
ptr_parent = ptr;
ptr = ptr -> left;
} else {
ptr_parent = ptr;
ptr = ptr -> right;
}
}
Node *newNode = new Node;
newNode -> data = value;
newNode -> left = NULL;
newNode -> right = NULL;
//checking for parent value to determine if
//the Node is a left or right child
if(value < (ptr_parent -> data))
ptr_parent -> left = newNode;
else
ptr_parent -> right = newNode;
}
++count;//to keep track of the Node count
return true;
}
为了我自己的缘故,我想在不使用双指针的情况下解决这个问题.
