63_二叉树中的结点插入操作

关键词：插入新结点、插入新结点

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