来源于《算法导论》第二版

 

1. 中序遍历

inorder-tree-walker(x)

{

    if x != NULL

    {

         inorder-tree-walker(x->left);

         print key[x];

         inorder-tree-walker(x->right);

    }

}

 

如果不用递归方法，可以用栈作为辅助数据结构

 

2.前序遍历

preorder-tree-walker(x)

{

    if x != NULL

    {

         print key[x];

         inorder-tree-walker(x->left);        

         inorder-tree-walker(x->right);

    }

}

 

3.后序遍历

preorder-tree-walker(x)

{

    if x != NULL

    {

         inorder-tree-walker(x->left);        

         inorder-tree-walker(x->right);

         print key[x];

    }

}

 

 

4.查找算法

递归方法

tree-search(x, key)

{

    if x==NULL || key == key[x]

    {

        return x;

    }

    if key < key[x]

    {

        return tree-search(x->left, key);

    }

    else

    {

        return tree-search(x->right, key);

    }

}

 

循环方法

iterative-tree-search(x, key)

{

   while x != NULL && key[x] != key

   {

      if( key < key[x] )

      {

         x = x->left;

      }

      else

      {

         x = x->right;

      }

   }

   return x;

}

 

5. 最小节点

tree-minimum(x)

{

  while NULL != x->left

  {

     x = x->left;

  }

  return x;

}

 

6.最大节点

tree-maximum(x)

{

    while NULL != x->right

    {

        x = x->right;

    }

    return x;

}

 

7.某一节点的后继

tree-successor(x)

{

   if NULL != x->right

   {

     return tree-minimun(x->right);

   }

   y = parent[x];

   while y != NULL && x == right[y]

   {

       x = y;

       y = parent[x];

   }

   return y;

}

 

8.某一节点的前趋

predecessor(x)

{

     if x->left != NULL

     {

        return tree-maximum(x->right);

     }

     y = parent[x];

     while y != NULL && x == y->left

     {

         x = y;

         y = parent[x];

     }

     return y;

}

 

9.插入

tree-insert(T, z)

{

    x = root(T);

    y = NULL;

    while( x != NULL )

    {

        y = x;

        if key[z] < key[x]

        {

            x = x->left;

        }

        else

        {

            x = x->right;

        }

     }

     parent[z] = y;

     if y == NULL

    {

        root[T] = z;

    }

    else

    {

        if( key[z] < key[y] )

        {

            y->left = z;

        }

        else

        {

            y->right = z;

        }

    }

}

 

10. 删除

tree-delete(T, z)

{

    //确定要删除的节点，为z自己或z的后继

    if z->left == NULL || z->right == NULL

    {

       y = z;//至多有一个节点，包括没有节点的情况

    }

    else

    {

       y = tree-successor(z);//有两个节点的情况

    }

    if y->left != NULL

    {

       x = y->left;

    }

    else

    {

       x = y-right;

    }

    if x != NULL //当x为null时，说明要删除的节点y没有子女，直接删除y节点就可以了

    {

       parent[x] = y->parent;

    }

    if y->parent == NULL //y为根节点

    {

        root[T] = x;//当根有子女时，把其中一个子女设为根节点；没有时，x为null，那根节点也为空

    }

    else

    {

        if y == y->parent->left

        {

            y-parent->left = x;

        }

        else

        {

           y->parent->right = x;

        }

    }

 

    if y != z //当删除的节点为z的后继节点时，复制数据

    {

       key[z] = key[y];

       copy other data of node;

    }

 

    return y;

}

 

删除的算法基于几点值得商榷：

1.最后key[z] = key[y]这句至少应该是要交换，因为return y之后，外面可能还要用节点z里的数据

  所以不能仅仅copy就完事

2.如果用c++实现，数据放的是很大object，copy效率低

3.这个伪代码有点难以理解

所以我觉得还是应该居于修改节点的指针来写代码比较好。

 

其他的几个算法都很好理解，其中遍历算法不能用递归方法的话，可能也比较难一点