54_树中结点的插入操作

关键词：

0. 插入操作

• 插入新结点bool insert(TreeNode<T>* node)
• 插入数据元素bool insert(const T& value, TreeNode<T>* parent)

1. 问题：如何指定新结点在树中的位置？

• 树是非线性的，无法采用下标的形式定位数据元素
• 每一个树结点都有唯一的前驱结点（父结点）
• 因此，必须先找到前驱结点，才能完成新结点的插入
  新结点的插入
  插入新结点流程图

    bool insert(TreeNode<T>* node)
    {
        bool ret = true;

        if( node != NULL )
        {
            if( this->m_root == NULL )
            {
                node->parent = NULL;
                this->m_root = node;
            }
            else
            {
                GTreeNode<T>* np = find(node->parent);

                if( np != NULL )
                {
                    // 查找该结点node是否已经在树中
                    // 若已经在树中，则不需要插入node结点
                    // 查找方法为：在node的父结点np中的子链表中查找(这个方法高效)

                    GTreeNode<T>* n = dynamic_cast<GTreeNode<T>*>(node);

                    if( np->child.find(n) < 0 )  // 如果没有在链表中没有找到，则插入该链表中
                    {
                        np->child.insert(n);
                    }
                }
                else
                {
                    THROW_EXCEPTION(InvalidParameterExcetion, "Invalid parent tree node ...");
                }
            }
        }
        else
        {
            THROW_EXCEPTION(InvalidParameterExcetion, "Parameter node cannot be NULL ...");
        }

        return ret;
    }

    bool insert(const T& value, TreeNode<T>* parent)
    {
        bool ret = true;

        GTreeNode<T>* node = new GTreeNode<T>();

        if( node != NULL )
        {
            node->value = value;
            node->parent = parent;

            insert(node);
        }
        else
        {
            THROW_EXCEPTION(NoEnoughMemoryExcetion, "No memory to create new GTreeNode...");
        }

        return ret;
    }

2. 小结

• 插入操作时构建树的唯一操作
• 执行插入操作时必须指明结点间的父子关系
• 插入操作必须正确处理指向父结点的指针
• 插入数据元素时需要从堆空间中创建结点

声明：此文章仅是本人在学习狄泰学院《数据结构实战开发教程》所做的笔记，文章中包含狄泰软件资料内容，一切版权归狄泰软件所有！
实验环境：ubuntu10 + Qt Creator2.4.1 + Qt SDK 4.7.4