关键词：插入新结点、插入新结点
0. 问题
- 是否能够在二叉树的任意结点处插入子结点？
不能，当结点的左子树和右子树都插入了新元素后，该结点就不能插入新的子结点了。 - 是否需要指定新数据元素（新结点）的插入位置？
需要，插入的新结点可能是左子树，也可能是右子树，需要确切的指定。
1. 二叉树结点的位置枚举类型
enum BTNodePos
{
ANY,
LEFT,
RIGHT
};
2. 插入方式
插入新结点
bool insert(TreeNode<T>* node)：没有指定位置，即位置可为左结点也可为右结点
bool insert(TreeNode<T>* node, BTNodePos pos)：指定位置pos插入新结点node-
插入数据元素
bool insert(const T& value, TreeNode<T>* parent)
bool insert(const T& value, TreeNode<T>* parent, BTNodePos pos)
新结点的插入示意图
指定位置的结点插入
指定位置插入结点流程图
virtual bool insert(BTreeNode<T>* n, BTreeNode<T>* np, BTNodePos pos)
{
bool ret = true;
if( pos == ANY )
{
if( np->left == NULL )
{
np->left = n;
}
else if( np->right == NULL )
{
np->right = n;
}
else
{
ret = false;
}
}
else if( pos == LEFT )
{
if( np->left == NULL )
{
np->left = n;
}
else
{
ret = false;
}
}
else if( pos == RIGHT )
{
if( np->right == NULL )
{
np->right = n;
}
else
{
ret = false;
}
}
else
{
ret = false;
}
return ret;
}
bool insert(TreeNode<T>* node)
{
return insert(node, ANY);
}
virtual bool insert(TreeNode<T>* node, BTNodePos pos)
{
bool ret = true;
if( node != NULL )
{
if( root() == NULL )
{
this->m_root = node;
node->parent = NULL;
}
else
{
BTreeNode<T>* np = find(dynamic_cast<BTreeNode<T>*>(node->parent));
if( np != NULL )
{
ret = insert(dynamic_cast<BTreeNode<T>*>(node), np, pos);
}
else
{
THROW_EXCEPTION(InvalidParameterExcetion, "Invalid parent there node...");
}
}
}
else
{
THROW_EXCEPTION(InvalidParameterExcetion, "Parameter node can not be NULL...");
}
return ret;
}
插入数据元素
bool insert(const T& value, TreeNode<T>* parent)
{
return insert(value, parent, ANY);
}
virtual bool insert(const T& value, TreeNode<T>* parent, BTNodePos pos)
{
int ret = true;
BTreeNode<T>* node = BTreeNode<T>::NewNode();
if( node != NULL )
{
node->value = value;
node->parent = parent;
ret = insert(node, pos);
if( !ret )
{
delete node;
}
}
else
{
THROW_EXCEPTION(NoEnoughMemoryExcetion, "No memory to create a new BTreeNode...");
}
return ret;
}
3. 小结
- 二叉树的插入操作需要指明插入的位置
- 插入操作必须正确处理指向父结点的指针
- 插入操作元素时需要从堆空间中创建结点
- 当数据元素插入失败时需要释放结点空间
声明：此文章仅是本人在学习狄泰学院《数据结构实战开发教程》所做的笔记，文章中包含狄泰软件资料内容，一切版权归狄泰软件所有！
实验环境：ubuntu10 + Qt Creator2.4.1 + Qt SDK 4.7.4
