二叉树插入删除查找递归及非递归的实现

二叉树建树、插入、删除、查找最大最小值、查找特定值的递归及非递归实现。

<mark>注意：一定要先建二叉树，必须要有一个开辟了内存空间的节点作为头结点（并且赋了值）！！！</mark>

#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>
using namespace std;
typedef long long ll;
#define maxn 1000005
#define mod 7654321
#define NIL -1

typedef struct Tree
{
    int data;
    Tree *lChild,*rChild;
}*TREE;

//查找递归及非递归实现
TREE Find(TREE T,int X)
{
    //递归
    if(T == NULL)
        return NULL;
    if(X > T->data)
        Find(T->rChild,X);
    else if(X<T->data)
        Find(T->lChild,X);
    else
        return T;

    //非递归
// while(T)
// {
// if(X>T->data)
// T=T->rChild;
// else if(X<T->data)
// T=T->lChild;
// else
// return T;
// }
// return NULL;
}

//查找最小值递归及非递归实现
TREE FindMin(TREE T)
{
    //递归
    if(T == NULL)
        return NULL;
    else if(T->lChild == NULL)
        return T;
    else
        return FindMin(T->lChild);

    //非递归
// if(T)
// {
// while(T->lChild)
// {
// T=T->lChild;
// }
// }
// return T;
}

//查找最大值递归及非递归实现
TREE FindMax(TREE T)
{
    //递归
    if(T == NULL)
        return NULL;
    else if(T->rChild == NULL)
        return T;
    else
        return FindMax(T->rChild);

    //非递归
// if(T)
// {
// while(T->rChild)
// {
// T=T->rChild;
// }
// }
// return T;
}

//建二叉树实现
TREE CreatTree(TREE T)
{
    T = (TREE)malloc((sizeof(Tree)));
    T->data = -1;
    T->lChild = T->rChild = NULL;
    return T;
}

//插入递归及非递归实现实现
TREE Insert(TREE T,int x)
{
    if(T==NULL)
    {
        T = (TREE)malloc(sizeof(Tree));
        T->data = x;
        T->lChild = T->rChild = NULL;
    }
    else
    {
        if(x > T->data)//下面的等于号起到连接插入元素与其父亲的作用
            T->rChild = Insert(T->rChild,x);
        else if(x < T->data)
            T->lChild = Insert(T->lChild,x);
        //若该插入元素已经存在，则直接返回
    }
    return T;

/* 非递归方式插入 TREE parent; TREE head = T; TREE p = (TREE)malloc(sizeof(Tree)); p->data = x; p->lChild = p->rChild = NULL; //查找需要添加的父结点，这个父结点是度为0的结点； while(head) { parent = head; if(x < head->data) head = head->lChild; else head = head->rChild; } //判断添加到左子树还是右子树； if(x < parent->data) parent->lchild = p; else parent->rchild = p; */
}

//删除
TREE Delete(TREE T,int X)
{
    TREE Tmp;

    if(!T)
        printf("要删除的元素未找到");
    else
    {
        if( X < T->data )
            T->lChild = Delete(T->lChild,X);
        else if( X > T->data )
            T->rChild = Delete(T->rChild,X);
        else
        {   // 找到要删除节点
            // 如果被删除结点有左右两个子结点
            if(T->lChild&&T->rChild)
            {
                //从右子树中找最小的元素填充删除结点
                Tmp = FindMin(T->rChild);
                T->data = Tmp->data;//填充进去
                //从右子树中删除由于填充少了的最小元素
                T->rChild = Delete(T->rChild,T->data);
            }
            else
            {   //被删除结点有一个或无子结点
                Tmp = T;
                if(!T->lChild)  //左儿子空右儿子不空
                    T = T->rChild;
                else            //右儿子空左儿子不空
                    T = T->lChild;
                //或者左右儿子都空，也会进入第一个if，直接指向NULL
                free( Tmp );
            }
        }
    }
    return T;
}

//中序遍历
void inTraverse(TREE T)
{
    if(T == NULL)
        return;
    else
    {
        inTraverse(T->lChild);
        cout<<" "<<T->data;
        inTraverse(T->rChild);
    }
}

int main()
{
    TREE T,tem;

    T = CreatTree(T);

    for(int i=0;i<10;i++)
        Insert(T,i);

    tem = FindMax(T);
    if(tem)
        cout<<tem->data<<endl;

    tem = FindMin(T);

    if(tem)
        cout<<tem->data<<endl;

    Insert(T,99);

    Delete(T,5);

    inTraverse(T);

    return 0;
}