關鍵詞：插入新結點、插入新結點

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. 小結

• 二叉樹的插入操作需要指明插入的位置
• 插入操作必須正確處理指向父結點的指針
• 插入操作元素時需要從堆空間中創(chuàng)建結點
• 當數據元素插入失敗時需要釋放結點空間

聲明：此文章僅是本人在學習狄泰學院《數據結構實戰(zhàn)開發(fā)教程》所做的筆記，文章中包含狄泰軟件資料內容，一切版權歸狄泰軟件所有！
實驗環(huán)境：ubuntu10 + Qt Creator2.4.1 + Qt SDK 4.7.4