二叉树基本操作

时间：2022-10-30 17:31:19

创建一颗二叉树，需要掌握一些基本操作，如，创建树，前序遍历，中序遍历，后序遍历，利用非递归方式的前序遍历，中序遍历，后序遍历，利用非递归方式原理大致相同，利用栈的先进后出原理即可实现，层序遍历，是从左到右遍历，利用队列先进先出的原理即可实现，计算叶子节点，二叉树的深度，交换左右子树等基本操作。


创造一棵二叉树是所需要的头文件和结构体

#include<stdio.h>

#include<stdlib.h>
#include<stack>
#include<queue>
#include <iostream>
using namespace std;
typedef int ElementType;


typedef struct TreeNode{
    ElementType Element;
    struct TreeNode *left;
    struct TreeNode *right;
}TreeNode,*SearchTree;//定义结构体节点

1.建立一颗二叉树，及插入新的元素

二叉树的左结点的数小于根节点的数值得大小，当插入一个新的元素时，如果该节点部位空，则判断新元素的数值是否大于该结点的数值得大小，直到最后节点为空。

二叉树基本操作二叉树基本操作

2.利用递归对该二叉树进行前序遍历

前序遍历：根左右

判断该节点是否为空，不为空，就将该节点的值打印出来，然后将左子树的再次进行相同的遍历，遍历到最后，然后就可以进行最后一个节点的右子树的遍历，直到所有的栈全部结束，则遍历结束

二叉树基本操作3.非递归的前序遍历，用栈进行二叉树的先序遍历； 将二叉树的左结点全部打印出来，直到最后一个，然后再把最后一个节点来判断其是否有右节点，再次循环，直到最后，栈为空，退出循环，遍历结束，代码如下。 

二叉树基本操作
4.利用递归来进行中序遍历，中序遍历，所以是左根右
二叉树基本操作

5.非递归方式来进行中序遍历

将左节点存储到栈里面，直到最后一个最左的左结点，然后打印出该元素，检查该节点是否有右子树，有的话就再进行while循环，这时我们假设没有右子树，则从栈里拿出元素，进行打印，然后判断其有没有右子树，此时我们假设该右子树有一个元素，则将其放到栈里面，此时循环结束，然后再将其打印出来，便完成了对这个左子树的遍历，依次类推。这个过程就是利用了栈的后进先出的思想，将右子树的元素放进去，能够先打印出来

二叉树基本操作

6.使用递归完成后续遍历，后续遍历：左右根。

二叉树基本操作
7.层序遍历

二叉树基本操作
   

}//查找元素

7.计算叶子节点数，利用递归，直到最后的左右节点均为空时，则叶子结点数目加一，依次类推，得出叶子节点数

二叉树基本操作

8.计算二叉树的深度：利用递归，直到左子树为空时，这个左子树的递归便结束，然后便可二叉树的左子树深度加一，总而言之，二叉树的深度是从下而上进行计算的

二叉树基本操作

}//计算该树的深度


int Swap(SearchTree T)
{
    TreeNode *tmp;
    stack<TreeNode *>p1;
    if(T==NULL)
        return 0;
    while(1)
    {
       tmp=T->left;
       T->left=T->right;
       T->right=tmp;//先将左右子树进行交换
       if(T->right!=NULL)//先进行左子树的交换，此时的右子树是本来的左子树；
       {
          p1.push(T->right);//将右子树放到栈里面
       }
       if(T->left!=NULL)
       {
            T=T->left;
       }
       else
       {
          if(!p1.empty())
          {
            T=p1.top();
            p1.pop();
          }
             else
             break;


          }
    }
}//利用栈进行二叉树左右子树的交换
int main()
{
    SearchTree T=NULL;//创造一棵树
    int e=0,m,n,i,depth,counts;
    cin>>n;
    for(i=0;i<n;i++)
    {
        cin>>e;
        Create_Insert(T,e);
    }//输入n个节点
    PreOrderTraverse(T);//对该二叉树的前序遍历
    printf("\n");
    InOrderTraverse(T);//对该二叉树的中序遍历
     printf("\n");
    PostOrderTraverse(T);//对该二叉树的后序遍历
     printf("\n");
    cin>>m;
    n=Search(T,m);//查找该二叉树里面有无m这个元素
    cout<<n<<endl;
    cin>>m;
    n=Search(T,m);//查找该二叉树里面有无m这个元素
    cout<<n<<endl;
    cin>>e;
    Create_Insert(T,e);//插入元素e;
    PreOrderTraverse(T);//对插入新元素的二叉树的前序遍历
    printf("\n");
    InOrderTraverse(T);//对插入新元素的二叉树的中序遍历
    printf("\n");
    PostOrderTraverse(T);//对插入新元素的二叉树的后序遍历
    printf("\n");
    InOrderTraverse2(T);//对插入新元素的二叉树的中序遍历（非递归方式）
    printf("\n");
    leveltraversal(T);//对插入新元素的二叉树的层序遍历
    printf("\n");
    Swap(T);//交换左右子树
    PreOrderTraverse(T);//交换左右子树后的二叉树的前序遍历
    printf("\n");
    InOrderTraverse(T);//交换左右子树后的二叉树的中序遍历
    printf("\n");
    PostOrderTraverse(T);//交换左右子树后的二叉树的后序遍历
    printf("\n");
    Swap(T);//对该子树再次进行左右子树交换
    PreOrderTraverse(T);//再次交换左右子树后的二叉树的前序遍历
    printf("\n");
    InOrderTraverse(T);//再次交换左右子树后的二叉树的中序遍历
    printf("\n");
    PostOrderTraverse(T);//再次交换左右子树后的二叉树的后序遍历
    printf("\n");
    n=Depth(T,depth);//二叉树的深度
    cout<<n<<endl;
    n=Leavecount(T,counts);//二叉树的叶子节点数
    cout<<n<<endl;


    return 0;

}

具体实现代码：#include<stdio.h>
#include<stdlib.h>
#include<stack>
#include<queue>
#include <iostream>
using namespace std;
typedef int ElementType;


typedef struct TreeNode{
    ElementType Element;
    struct TreeNode *left;
    struct TreeNode *right;
}TreeNode,*SearchTree;//定义结构体节点


SearchTree Create_Insert(SearchTree &T,ElementType e)
{
    //二叉排序树的插入过程
    if(!T)
    {
        //未找到值为e的结点，就新生成一个结点
        T = (TreeNode*)malloc(sizeof(TreeNode));
        T->Element = e;
        T->left = NULL;
        T->right = NULL;
    }


    else if(e<T->Element)     //在左子树中插入
         Create_Insert(T->left,e);
    else if(e>T->Element)     //在右子树中插入
        Create_Insert(T->right,e);


}
int PreOrderTraverse(SearchTree T)
{
    if(T!=NULL)
    {
        printf("%d ",T->Element);//将根节点打印出来；
        PreOrderTraverse(T->left);
        PreOrderTraverse(T->right);


    }//先序遍历；
}
int PreOrderTraverse2(SearchTree T)//非递归的前序遍历，用栈进行二叉树的先序遍历
{
    TreeNode *p1,*top;
    stack<TreeNode *>p;
    p1=T;
    while(p1||!p.empty())
    {
        while(p1)
        {
            printf("%d",T->Element);
            p.push(p1);
            p1=p1->left;
        }//循环，将整棵树的左结点进行打印出来
        top=p.top();
        p.pop();
        p1=top->right;//最后一个节点里面有没有右子树，有的话再次进行循环
    }




}
int InOrderTraverse(SearchTree T)
{
    if(T!=NULL)
    {
        InOrderTraverse(T->left);
        printf("%d ",T->Element);
        InOrderTraverse(T->right);
    }
}//运用递归进行中序遍历
int InOrderTraverse2(SearchTree T)
{
    TreeNode *p1,*top;
    stack<TreeNode *> p;
    p1=T;
    while(p1||!p.empty())
    {
        while(p1)
        {
            p.push(p1);
            p1=p1->left;
        }//将最左边的节点全部存储到栈里面
       top=p.top();
       printf("%d ",top->Element);
       p.pop();
       p1=top->right;
    }//非递归中序遍历
}//用栈进行中序遍历
int PostOrderTraverse(SearchTree T)
{
    if(T!=NULL)
    {
        PostOrderTraverse(T->left);
        PostOrderTraverse(T->right);
         printf("%d ",T->Element);
    }
}//后序遍历


int leveltraversal(SearchTree T)
{
    queue<TreeNode *> p;
    TreeNode *top;
    p.push(T);
    while(!p.empty())
    {
       top=p.front();
       p.pop();
       printf("%d ",top->Element);//按照队列先进先出进行输出；
       if(top->left!=NULL)//进入队列里面，都是从左到右入队
        p.push(top->left);
       if(top->right!=NULL)
        p.push(top->right);
    }


}//用队列进行层序遍历
int  Search(SearchTree T,int &e)
{


    if(T!=NULL)
    {
        if(T->Element>e)//e小于该根节点，便查找左子树
        {
            Search(T->left,e);
        }
        if(T->Element<e)//e大于该根节点，便查找右子树
        {
            Search(T->right,e);
        }
        if(T->Element==e)//e等于该根节点的值
        {
            e=1;
            return e;
        }
    }
    else
        e=0;
        return e;
}//查找元素
int Leavecount(SearchTree T,int &counts)
{
    if(T==NULL)//这颗树是空的
        return 0;
    counts=0;
    if(T->left==NULL||T->right==NULL)
    {
        counts++;//当该节点的左右节点均为空时；
    }
    else
    {
        counts=Leavecount(T->left,counts)+Leavecount(T->right,counts);
        //每颗子树上面都有左右节点，直到最后左右节点都为空
    }


      return counts;


}//计算该二叉树的叶子节点数
int Depth(SearchTree T,int &depth)
{
    depth=0;
    if(T!=NULL)
    {
        int ldepth=Depth(T->left,depth)+1;
        int rdepth=Depth(T->right,depth)+1;
        depth=(ldepth>rdepth)?ldepth:rdepth;
    }
    return depth;


}//计算该树的深度


int Swap(SearchTree T)
{
    TreeNode *tmp;
    stack<TreeNode *>p1;
    if(T==NULL)
        return 0;
    while(1)
    {
       tmp=T->left;
       T->left=T->right;
       T->right=tmp;//先将左右子树进行交换
       if(T->right!=NULL)//先进行左子树的交换，此时的右子树是本来的左子树；
       {
          p1.push(T->right);//将右子树放到栈里面
       }
       if(T->left!=NULL)
       {
            T=T->left;
       }
       else
       {
          if(!p1.empty())
          {
            T=p1.top();
            p1.pop();
          }
             else
             break;


          }
    }
}//利用栈进行二叉树左右子树的交换
int main()
{
    SearchTree T=NULL;//创造一棵树
    int e=0,m,n,i,depth,counts;
    cin>>n;
    for(i=0;i<n;i++)
    {
        cin>>e;
        Create_Insert(T,e);
    }//输入n个节点
    PreOrderTraverse(T);//对该二叉树的前序遍历
    printf("\n");
    InOrderTraverse(T);//对该二叉树的中序遍历
     printf("\n");
    PostOrderTraverse(T);//对该二叉树的后序遍历
     printf("\n");
    cin>>m;
    n=Search(T,m);//查找该二叉树里面有无m这个元素
    cout<<n<<endl;
    cin>>m;
    n=Search(T,m);//查找该二叉树里面有无m这个元素
    cout<<n<<endl;
    cin>>e;
    Create_Insert(T,e);//插入元素e;
    PreOrderTraverse(T);//对插入新元素的二叉树的前序遍历
    printf("\n");
    InOrderTraverse(T);//对插入新元素的二叉树的中序遍历
    printf("\n");
    PostOrderTraverse(T);//对插入新元素的二叉树的后序遍历
    printf("\n");
    InOrderTraverse2(T);//对插入新元素的二叉树的中序遍历（非递归方式）
    printf("\n");
    leveltraversal(T);//对插入新元素的二叉树的层序遍历
    printf("\n");
    Swap(T);//交换左右子树
    PreOrderTraverse(T);//交换左右子树后的二叉树的前序遍历
    printf("\n");
    InOrderTraverse(T);//交换左右子树后的二叉树的中序遍历
    printf("\n");
    PostOrderTraverse(T);//交换左右子树后的二叉树的后序遍历
    printf("\n");
    Swap(T);//对该子树再次进行左右子树交换
    PreOrderTraverse(T);//再次交换左右子树后的二叉树的前序遍历
    printf("\n");
    InOrderTraverse(T);//再次交换左右子树后的二叉树的中序遍历
    printf("\n");
    PostOrderTraverse(T);//再次交换左右子树后的二叉树的后序遍历
    printf("\n");
    n=Depth(T,depth);//二叉树的深度
    cout<<n<<endl;
    n=Leavecount(T,counts);//二叉树的叶子节点数
    cout<<n<<endl;


    return 0;
}

标签：

相关文章