树——通用树结点的插入

1，通用树中的插入操作是以查找操作为基础的；

2，插入的方式：

1，插入新结点：

1，bool insert(TreeNode<T>* node)

2，插入数据元素：

1，bool insert(const T& value, TreeNode<T>* parent)

3，如何指定新结点在树中的位置？

1，问题分析：

1，树是非线性的，无法采用下标的形式定位数据元素；

2，每一个树结点都有唯一的前驱结点（父结点）；

3，因此，必须先找到前驱结点，才能完成新结点的插入；

4，新结点的插入：

1，插入操作不是递归实现的；

2，插入操作在查找操作帮助下是非常容易实现的；

3，要插入结点，只用关注父结点中的关于子结点部分（child 链表），至于插入结点的 parent 和 value 不是自己维护的范围，已经被插入者维护好了；

　　4，代码实现：

 1 　　 /* 实现从 Tree<T> 中继承而来的纯虚函数没有插入操作的时候，无法构建一棵树插入操作是构建树的唯一操作，非递归*/
 2     bool insert(TreeNode<T>* node)
 3     {
 4         bool ret = true;
 5 
 6         if( node != NULL )  // 不能插入空结点
 7         {
 8             if( this->m_root == NULL )  // 插入的树是空树
 9             {
10                 node->parent = NULL;  // 新结点是根结点，树中通过插入结点的父对象来唯一标识这个结点
11                 this->m_root = node;
12             }
13             else
14             {
15                 GTreeNode<T>* np = find(node->parent);  // 插入结点的父结点是不是在树中
16                 if( np != NULL )
17                 {
18                     GTreeNode<T>* n = dynamic_cast<GTreeNode<T>*>(node);
19 
20                     if( np->child.find(n) < 0 )  // 当前要插入的父结点没有需要插入的子结点，返回值小于 0
21                     {
22                         np->child.insert(n);  // 插入到父结点的子结点链表里面去
23                     }
24                 }
25                 else
26                 {
27                     THROW_EXCEPTION(InvalidOperationException, "Invalid parent tree node ...");
28                 }
29             }
30         }
31         else
32         {
33             THROW_EXCEPTION(InvalidParameterException, "Parameter node cannot be NULL ...");
34         }
35         return ret;
36 　　 }

5，数据元素插入：

1，只用维护插入结点的 parent 和 value 以及父结点的 parent 就可以了，至于自己的 child 链表，还是个空链表，不用管，而父结点的 child 是要维护的，用新结点插入方法维护；

　　2，代码实现：

 1 　　 bool insert(const T& value, TreeNode<T>* parent)
 2     {
 3         bool ret = true;
 4         GTreeNode<T>* node = GTreeNode<T>::NewNode();  // 使用工厂方法
 5 
 6         if( node != NULL )
 7         {
 8             node->value = value;
 9             node->parent = parent;
10 
11             insert(node);  // 本文 4.4 中 insert 函数复用
12         }
13         else
14         {
15             THROW_EXCEPTION(NoEnoughMemoryException, "No memory to create new tree node ...");
16         }
17 
18         return ret;
19 　　 }

6，插入新结点的操作中，新结点的 child 都不用管；

7，小结：

1，插入操作是构建树的唯一操作；

2，执行插入操作时必须指明结点间的父子关系；

3，插入操作必须正确处理指向父结点的指针；

4，插入数据元素时需要从堆空间中创建结点；