二叉树的相关操作

 定义二叉树：

//定义二叉树
typedef struct BiTNode
{
    int data;
    struct BiTNode *lchild,*rchild;
} BiTNode,*BiTree;

按先序遍历顺序创建二叉树：

void CreateBiTree(BiTree &T)
{
    int n;
    cin>>n;
    if(n==0) T=NULL;
    else
    {
        T=new BiTNode;
        T->data=n;
        CreateBiTree(T->lchild);
        CreateBiTree(T->rchild);
    }
}

 递归遍历二叉树：

//先序遍历
void PreOrderTraverse(BiTree T)
{
    if(T)
    {
        cout<data<lchild);
        PreOrderTraverse(T->rchild);
    }
}

//中序遍历
void InOderTraverse(BiTree T)
{
    if(T)
    {
        InOderTraverse(T->lchild);
        cout<data;
        InOderTraverse(T->rchild);
    }
}

//后序遍历
void PostOrderTraverse(BiTree T)
{
    if(T)
    {
        PostOrderTraverse(T->lchild);
        PostOrderTraverse(T->rchild);
        cout<data;
    }
}

非递归遍历二叉树： 

//先序遍历
void PreOderTraverse(BiTree T)
{
    stack S;
    BiTree p=T;
    S.push(p); //把根节点入栈
    BiTree q=new BiTNode; //申请一个节点空间，用来存放栈顶元素
    while(!S.empty())
    {
        q=S.top();
        cout<data<rchild!=NULL) //右孩子先入栈
        {
            S.push(q->rchild);
        }
        if(q->lchild!=NULL)
        {
            S.push(q->lchild);
        }
    }
}

//中序遍历
void InOderTraverse(BiTree T)
{
    stack S;
    BiTree p=T;
    BiTree q=new BiTNode; //申请一个节点空间，用来存放栈顶元素
    while(p||!S.empty())
    {
        if(p)
        {
            S.push(p);
            p=p->lchild;
        }
        else
        {
            q=S.top();
            cout<data<rchild;

        }
    }
}

//后序遍历
void PostOrderTraverse(BiTree T)
{
    stack S;
    BiTree curNode; //当前访问节点
    curNode=T;
    BiTree visitedNode; //记录出栈的节点
    visitedNode=T;
    while(curNode||!S.empty())
    {
        while(curNode)
        {
            S.push(curNode);
            curNode=curNode->lchild;
        }
        curNode=S.top(); //取栈顶节点
        if(curNode->rchild&&curNode->rchild!=visitedNode) //如果栈顶结点有右孩子并且没有被访问过
        {
            curNode=curNode->rchild;
        }
        else //右孩子已经被访问或者没有右孩子
        {
            cout<data< 
层次遍历二叉树： 
 
//层次遍历
void LevelOderTraverse(BiTree T)
{
    queue Q; //层次遍历用到队列
    BiTree p;
    p=T;
    Q.push(p); //先把根节点入队
    BiTree q=new BiTNode;
    while(p||!Q.empty())
    {
        q=Q.front(); //取队头元素
        cout<data<lchild!=NULL)
        {
            Q.push(q->lchild);
        }
        if(q->rchild!=NULL)
        {
            Q.push(q->rchild);
        }
    }
}
 
复制二叉树： 
 
//复制
void CopyBiTree(BiTree T,BiTree &newT)
{
    if(T==NULL) //节点为空
    {
        newT=NULL; //复制的节点也为空
        return; //返回上一层递归
    }
    else
    {
        newT=new BiTNode;
        newT->data=T->data;
        CopyBiTree(T->lchild,newT->lchild);
        CopyBiTree(T->rchild,newT->rchild);
    }
}
 
计算二叉树的深度：
 
//计算二叉树的深度
int Depth(BiTree T)
{
    if(T==NULL) return 0;
    else
    {
        int m=Depth(T->lchild);
        int n=Depth(T->rchild);
        if(m>n) return m+1;
        else return n+1;
    }
}
 
int main()
{
    BiTree T;
    CreateBiTree(T);
    cout< 
计算二叉树节点数: 
 
int nodeCount(BiTree T)
{
    if(T==NULL) return 0;
    else
    {
        return nodeCount(T->lchild)+nodeCount(T->rchild)+1; //左子树+右子树+根
    }
}
 
 计算二叉树叶子节点数：
 
//计算二叉树叶子节点数
int leafCount(BiTree T)
{
    if(T==NULL)
        return 0;
    else if(T->lchild==NULL&&T->rchild==NULL)
        return 1;
    else
        return leafCount(T->lchild)+leafCount(T->rchild);
}
 
 在二叉树中查找给定关键字(函数返回值为成功1,失败0)：
 
//在二叉树中查找给定关键字(函数返回值为成功1,失败0)
int findNode(BiTree T,int x)
{
    if(T==NULL)
        return 0;
    else
    {
        if(T->data==x)
            return 1;
        else
        {
            return max(findNode(T->lchild,x),findNode(T->rchild,x));
        }

    }
}
 
int main()
{
    BiTree T;
    CreateBiTree(T);
    if(findNode(T,6))
    {
        cout<<"YES"< 
在二叉排序树中查找给定关键字(函数返回值为成功1,失败0):
 
int findNode(BiTree T,int x)
{
    if(T==NULL)
        return 0;
    else
    {
         if(T->data==x)
            return 1;
        else if(T->data>x)
            return findNode(T->lchild,x);
        else if(T->datarchild,x);
    }
}
 
交换各结点的左右子树:
 
//交换各结点的左右子树
void exchangeBiTree(BiTree &T)
{
    BiTree p;
    if(T)
    {
        p=T->lchild;
        T->lchild=T->rchild;
        T->rchild=p;
        exchangeBiTree(T->lchild);
        exchangeBiTree(T->rchild);
    }
}
 
插入新节点：
 
//插入新结点
BiTree InsertBiTree(BiTree &T,BiTree node)
{
    if(T==NULL)
        T=node;
    else
    {
        if(node->datadata)
            T->lchild=InsertBiTree(T->lchild,node);
        else if(node->data>T->data)
            T->rchild=InsertBiTree(T->rchild,node);
    }
    return T;
}
 
 
 
测试数据：8 4 2 0 0 0 10 0 12 0 0 
 
 
int main()
{
    BiTree T,p;
    CreateBiTree(T);
    PreOderTraverse(T);
    p=new BiTNode;
    p->lchild=NULL;
    p->rchild=NULL;
    p->data=6;
    InsertBiTree(T,p);
    PreOderTraverse(T);
    return 0;
}
 
删除某结点：
 
//删除某结点
BiTree deleteNode(BiTree &T,int key)
{
    if(!T) //如果树为空
    {
        return NULL;
    }
    if(T->datarchild=deleteNode(T->rchild,key);
    }
    else if(T->data>key) //在左子树找
    {
        T->lchild=deleteNode(T->lchild,key);
    }
    else if(T->data==key) //找到key节点
    {
        if(!T->lchild&&!T->rchild) //如果key是叶子节点
        {
            return NULL; //直接删除
        }
        else if(T->lchild&&!T->rchild) //如果key有左孩子，把key换成key的左孩子
        {
            return T->lchild;
        }
        else if(!T->lchild&&T->rchild) //如果key有右孩子，把key换成key的右孩子
        {
            return T->rchild;
        }
        else //如果key的左右孩子都存在
        {
            BiTree tmp=T->rchild;
            while(tmp&&tmp->lchild)
            {
                tmp=tmp->lchild; //找到key右子树的最小节点tmp
            }
            BiTree p; //交换key和tmp的值，把key的值换到了右子树上
            p->data=T->data;
            T->data=tmp->data;
            tmp->data=p->data;
            T->rchild=deleteNode(T->rchild,key); //通过不断交换，把key变成叶子节点直接删除
        }
    }
    return T;
}
 
int main()
{
    BiTree T,p;
    CreateBiTree(T);
    PreOderTraverse(T);
    deleteNode(T,8);
    PreOderTraverse(T);
    return 0;
}