程序填空题：二叉搜索树的非递归插入操作

为a数组中的元素实现一个二叉搜索树，并用InOrder()函数输出序列。

c++

#include<iostream>
#include<stdlib.h>
using namespace std;

template<class K,class V>
struct BSTNode
{
K _key;
V _value;
BSTNode* _left;
BSTNode* _right;

BSTNode(const K& key, const V& value)
: _key(key)
, _value(value)
, _left(NULL)
, _right(NULL)
{}
};
template<class K, class V>
class BSTree
{
typedef BSTNode<K, V> Node;
public:
BSTree()
:_root(NULL)
{}
//非递归插入
bool Insert(const K & key, const V & value)
{
if (_root == NULL)
{
_root = new Node(key, @@[value](3));
return true;
}
Node *parent = NULL;
Node *cur = _root;
while (cur)
{
if (@@[key](3) > cur->_key)
{
parent = cur;
cur = cur->_right;
}
else if (key < cur->_key)
{
parent = cur;
cur = @@[cur->_left](3);
}
else
{
return false;
}
}
cur = new Node(key, value);
if (parent->_key > key)
{
parent->_left = cur;
}
else
{
parent->_right = cur;
}
return true;
}


void InOrder()
{
_InOrder(_root);
cout << endl;
}
protected:

void _InOrder(Node* root)
{
if (root == NULL)
{
return;
}
_InOrder(root->_left);
cout << root->_key << " ";
_InOrder(root->_right);
}
private:
BSTNode<K, V>* _root;
};




int main()
{
int a[10] = { 5, 2, 4, 8, 7, 1, 9, 0, 6, 3 };
BSTree<int, int> bstree;
for (int i = 0; i < 10; i++)
{
bstree.Insert(a[i], a[i]);
}
bstree.InOrder();

return 0;
}







答案：
第1空：value

第2空：key

第3空：cur->_left