如果在二叉树中插入一个已经在二叉树中存在的元素该怎么处理

Question

我好像百度没有遇到这样的情况，比如二叉树里有一个45，我再插入45该怎么处理？不知道这个问题是不是太二，望大神赐教

Answer 1

如果你指的是BST的话，遇到重复的元素时，不用管它（或者抛出异常、返回错误等）。许多算法书上都假设没有重复的key值，因为要实现有重复的是非常繁琐的。

插入实现

/*当BST中不存在关键字等于e.key的数据元素时，插入e并返回TRUE，否则返回FALSE*/
Status InsertBST(BiTree *T, ElemType e)
{  
      if(!T)  
      {        
            s = new BiTNode;
            s->data = e; s->lchild = s->rchild = NULL;
            T=s;    //被插节点*s为新的根结点
       }
      else if(e.key == p->data.key)
          return false;//关键字等于e.key的数据元素，返回错误
      if (e.key < p->data.key)
          InsertBST(p->lchild, e);    //插入左子树
      else 
          InsertBST(p->rchild, e);    //插入右子树
      return true;
 }

当然，你也可以允许重复元的插入，如果定义left <= root < right，并拥有下面的树：

      3
    /   \
  2       4

插入3会得到：

      3
    /   \
  2       4
    \
     3

注意重复的元素不在相邻的层次上，并且树的深度会变得很大，判断重复元是否存在将会变得很困难。一个比较好的选择是通过在节点记录中保留一个附加的域来指示重复元的个数，先前的例子将会变成：

      3(1)
    /     \
  2(1)     4(1)

插入3之后：

     3(2)
    /     \
  2(1)     4(1)

这种方法只需要一些额外的空间，但是查找，删除和插入等操作会变得比较方便。

Refer：
Binary search tree

Are duplicate keys allowed in the definition of binary search trees

Answer 2

你问的太模糊了，能否画出原有树结构和你期望的结果。

Answer 3

要看你的树的目的，在我的记忆中，树的每个节点都是唯一的，在插入重复的节点的时候，我觉得是丢弃。