手写实现搜索二叉树：

• 树的节点定义：

class TreeNode
{
@H_502_9@public:
    TreeNode(@H_502_9@int v) :value(v){};

    TreeNode* left_son = NULL;
    TreeNode* right_son = NULL;
    TreeNode* p = NULL;         //一定保存双亲的指针
    @H_502_9@int @H_502_9@value = 0;
};

• 节点插入：

bool TreeInsert(TreeNode@H_301_32@*& pRoot,int value)
{
    TreeNode@H_301_32@* pNew @H_301_32@= new TreeNode(value);//待插入的节点
    TreeNode@H_301_32@* pParent @H_301_32@= NULL;//父节点
    TreeNode@H_301_32@* pCur @H_301_32@= pRoot;//子节点
    @H_502_9@while (pCur @H_301_32@!= NULL)
    {
        pParent @H_301_32@= pCur;
        @H_502_9@if (pCur@H_301_32@->value @H_301_32@< value)
        {
            pCur @H_301_32@= pCur@H_301_32@->right_son;
        }
        @H_502_9@else @H_502_9@if (pCur@H_301_32@->value@H_301_32@>value)
        {
            pCur @H_301_32@= pCur@H_301_32@->left_son;
        }
        @H_502_9@else
        {
            @H_502_9@return false;
        }
    }
    @H_502_9@if (pParent @H_301_32@== NULL)//空树
    {
        pRoot @H_301_32@= pNew;
    }
    @H_502_9@else @H_502_9@if ( pParent@H_301_32@->value@H_301_32@<value )//插右边
    {
        pParent@H_301_32@->right_son @H_301_32@= pNew;
        pNew@H_301_32@->p @H_301_32@= pParent;
    }
    @H_502_9@else//插左边
    {
        pParent@H_301_32@->left_son @H_301_32@= pNew;
        pNew@H_301_32@->p @H_301_32@= pParent;
    }
    @H_502_9@return true;
}

• 最大值，最小值函数

TreeNode@H_301_32@* TreeMax(TreeNode@H_301_32@* pRoot)
{
    @H_502_9@while (pRoot@H_301_32@!=NULL@H_301_32@&&pRoot@H_301_32@->right_son@H_301_32@!=NULL)
    {
        pRoot @H_301_32@= pRoot@H_301_32@->right_son;
    }
    @H_502_9@return pRoot;
}

TreeNode@H_301_32@* TreeMin(TreeNode@H_301_32@* pRoot)
{
    @H_502_9@while (pRoot@H_301_32@!=NULL@H_301_32@&&pRoot@H_301_32@->left_son@H_301_32@!=NULL)
    {
        pRoot @H_301_32@= pRoot@H_301_32@->left_son;
    }
    @H_502_9@return pRoot;
}

• 前驱、后继函数

TreeNode@H_301_32@* Successor(TreeNode@H_301_32@* pRoot)
{
    /* 寻找节点的后继节点 方法一：中序遍历，后继即 该节点输出的后一个节点 方法二：若当前节点有右孩子，则后继为右孩子子树的最小节点 若当前节点无右孩子，则后继为其最底层的祖先，条件是该结点位于此祖先的左子树 */
    @H_502_9@if (pRoot@H_301_32@==NULL)
    {
        @H_502_9@return pRoot;
    }
    @H_502_9@if (pRoot@H_301_32@->right_son @H_301_32@!= NULL)// 当前节点有右孩子
    {
        @H_502_9@return TreeMin(pRoot@H_301_32@->right_son);
    }

    TreeNode@H_301_32@* pChild @H_301_32@= pRoot;
    TreeNode@H_301_32@* pParent @H_301_32@= pChild@H_301_32@->p;

    @H_502_9@while (pParent @H_301_32@!= NULL@H_301_32@&&pParent@H_301_32@->right_son @H_301_32@== pChild)//当前节点无右孩子，寻找满足要求的最底层祖先
    {
        pChild @H_301_32@= pParent;
        pParent @H_301_32@= pParent@H_301_32@->p;
    }
    @H_502_9@return pParent;
}

TreeNode@H_301_32@* Processor(TreeNode@H_301_32@* pRoot)
{
    /* 寻找节点的前驱节点 若当前节点有左孩子，则前驱为左孩子子树的最大节点 若当前节点无左孩子，则后继为其最底层的祖先，条件是该结点位于此祖先的右子树 */
    @H_502_9@if (pRoot @H_301_32@== NULL)
    {
        @H_502_9@return pRoot;
    }
    @H_502_9@if (pRoot@H_301_32@->left_son @H_301_32@!= NULL)//有左孩子
    {
        @H_502_9@return TreeMax(pRoot@H_301_32@->left_son);
    }

    TreeNode@H_301_32@* pChild @H_301_32@= pRoot;
    TreeNode@H_301_32@* pParent @H_301_32@= pChild@H_301_32@->p;

    @H_502_9@while (pParent @H_301_32@!= NULL@H_301_32@&&pParent@H_301_32@->left_son @H_301_32@== pChild)//无左孩子，寻找满足要求的最底层祖先
    {
        pChild @H_301_32@= pParent;
        pParent @H_301_32@= pParent@H_301_32@->p;
    }
    @H_502_9@return pParent;
}

• 替换函数，使用一棵树接管另一棵树的双亲

bool TransPlant(TreeNode @H_301_32@*& pRoot,TreeNode@H_301_32@* pOld,TreeNode@H_301_32@* pNew)
{
    /* 使用一棵树接管另一棵树的双亲 */
    @H_502_9@if (pRoot @H_301_32@== NULL@H_301_32@||pOld @H_301_32@== NULL)//旧子树为空
    {
        @H_502_9@return false;
    }

    //调整父节点的指针
    @H_502_9@if (pOld@H_301_32@->p @H_301_32@== NULL)//父节点为空:替换了根节点
    {
        pRoot @H_301_32@= pNew;
    }
    @H_502_9@else
    {
        @H_502_9@if (pOld @H_301_32@== pOld@H_301_32@->p@H_301_32@->left_son)
        {
            pOld@H_301_32@->p@H_301_32@->left_son @H_301_32@= pNew;
        }
        @H_502_9@else
        {
            pOld@H_301_32@->p@H_301_32@->right_son @H_301_32@= pNew;
        }
    }
    //调整指向父节点的指针
    @H_502_9@if (pNew @H_301_32@!= NULL)//新子树不为空
    {
        pNew@H_301_32@->p @H_301_32@= pOld@H_301_32@->p;
    }
    @H_502_9@return true;
}

• 删除节点

void TreeDelete(TreeNode@H_301_32@*& pRoot,TreeNode@H_301_32@* pDelete)
{
    /* 删除指定节点 */
    @H_502_9@if (pRoot @H_301_32@== NULL @H_301_32@|| pDelete @H_301_32@== NULL)
        @H_502_9@return;

    @H_502_9@if (pDelete@H_301_32@->left_son @H_301_32@== NULL)//没有孩子或者只有一个孩子，直接将孩子提上来
    {
        TransPlant(pRoot,pDelete,pDelete@H_301_32@->right_son);
    }
    @H_502_9@else @H_502_9@if (pDelete@H_301_32@->right_son @H_301_32@== NULL)
    {
        TransPlant(pRoot,pDelete@H_301_32@->left_son);
    }
    @H_502_9@else//同时有两个孩子时
    {
        TreeNode@H_301_32@* successor @H_301_32@= TreeMin(pDelete@H_301_32@->right_son);//寻找后继,后继一定没有左孩子节点

        @H_502_9@if (successor@H_301_32@->p @H_301_32@!= pDelete)//后继不是被删除节点的右孩子节点
        {
            TransPlant(pRoot,successor,successor@H_301_32@->right_son);//删除后继节点
            successor@H_301_32@->right_son @H_301_32@= pDelete@H_301_32@->right_son;//将后继提到被删除节点右孩子位置上:接管被删除节点的右孩子
            successor@H_301_32@->right_son@H_301_32@->p @H_301_32@= successor;
        }

        TransPlant(pRoot,successor);//后继接管被删节点的双亲
        successor@H_301_32@->left_son @H_301_32@= pDelete@H_301_32@->left_son;//后继接管被删节点的左孩子
        successor@H_301_32@->left_son@H_301_32@->p @H_301_32@= successor;
    }
}

• 中序打印函数
• 测试主函数

void TreePrint(TreeNode@H_301_32@* pRoot)
{
    @H_502_9@if (pRoot @H_301_32@== NULL)
    {
        @H_502_9@return;
    }
    TreePrint(pRoot@H_301_32@->left_son);
    cout @H_301_32@<< pRoot@H_301_32@->value @H_301_32@<< " ";
    TreePrint(pRoot@H_301_32@->right_son);
}

int main()
{
    TreeNode@H_301_32@* pRoot(NULL);
    TreeInsert(pRoot,4);
    TreeInsert(pRoot,1);
    TreeInsert(pRoot,9);
    TreeInsert(pRoot,2);
    TreeInsert(pRoot,8);
    TreeInsert(pRoot,3);
    TreeInsert(pRoot,6);

    TreePrint(pRoot);
    cout @H_301_32@<< endl;
    TreeDelete(pRoot,pRoot);
    TreePrint(pRoot);

    @H_502_9@return 0;

}