SCAU 8607 实现二叉排序树的各种算法(1)

旧城等待， 2023-10-06 09:06 4阅读 0赞

### 8607 实现二叉排序树的各种算法(1) ###

时间限制:1000MS 代码长度限制:10KB  
提交次数:2573 通过次数:1472

题型: 编程题 语言: G++;GCC  
Description 用函数实现如下二叉排序树算法： （1） 插入新结点 （2） 前序、中序、后序遍历二叉树 （3） 中序遍历的非递归算法 （4） 层次遍历二叉树 （5） 在二叉树中查找给定关键字(函数返回值为成功1,失败0)

输入格式  
第一行：准备建树的结点个数n  
第二行：输入n个整数，用空格分隔  
第三行：输入待查找的关键字  
第四行：输入待查找的关键字  
第五行：输入待插入的关键字

输出格式  
第一行：二叉树的先序遍历序列  
第二行：二叉树的中序遍历序列  
第三行：二叉树的后序遍历序列  
第四行：查找结果  
第五行：查找结果  
第六行~第八行：插入新结点后的二叉树的先、中、序遍历序列  
第九行：插入新结点后的二叉树的中序遍历序列(非递归算法)  
第十行：插入新结点后的二叉树的层次遍历序列

输入样例  
7  
40 20 60 18 50 56 90  
18  
35  
30

输出样例  
40 20 18 60 50 56 90  
18 20 40 50 56 60 90  
18 20 56 50 90 60 40  
1  
0  
40 20 18 30 60 50 56 90  
18 20 30 40 50 56 60 90  
18 30 20 56 50 90 60 40  
18 20 30 40 50 56 60 90  
40 20 60 18 30 50 90 56

注意下题目给的是二叉排序树

#include <iostream>
    #include <queue>
    using namespace std;
    typedef struct node
    {
        
        int date;
        struct node *lchild,*rchild;
    }BitNode,*OrderBiTree;
    OrderBiTree Create_OrderBiTree(OrderBiTree T,int elem)//建立二叉排序树
    {
        
        if(T == NULL)//节点为空
        {
        
            T = new node();//重新初始化T
            T->date = elem;
        }
        else if(elem < T->date)//比根节点小放左边
            T->lchild = Create_OrderBiTree(T->lchild,elem);
        else if(elem > T->date)//比根节点大放右边
            T->rchild = Create_OrderBiTree(T->rchild,elem);
        return T;
    }
    
    void preorder(OrderBiTree T)//先序遍历
    {
        
        if(T)
        {
        
            printf("%d ",T->date);
            preorder(T->lchild);
            preorder(T->rchild);
        }
    }
    void inorder(OrderBiTree T)//中序遍历
    {
        
        if(T)
        {
        
            inorder(T->lchild);
            printf("%d ",T->date);
            inorder(T->rchild);
        }
    }
    void postorder(OrderBiTree T)//后序遍历
    {
        
        if(T)
        {
        
            postorder(T->lchild);
            postorder(T->rchild);
            printf("%d ",T->date);
        }
    }
    
    bool find(OrderBiTree T, int key)
    {
        
        if(T) {
        
            if (key > T->date) {
        
                return find(T->rchild, key);
            }
            else if (key < T->date) {
        
                return find(T->lchild, key);
            }
            else if (key == T->date) {
        
                return true;
    
            }
        }
            return false;
    }
    void level(OrderBiTree T)
    {
        
        queue<OrderBiTree>q;
        q.push(T);
        while(!q.empty())
        {
        
            OrderBiTree t;
            t=q.front();
            if(t->lchild!=NULL)q.push(t->lchild);
            if(t->rchild!=NULL)q.push(t->rchild);
            cout<<t->date<<" ";
            q.pop();
        }
    
    }
    
    int main()
    {
        
        OrderBiTree  T = NULL;
        int n;
        cin>>n;
        int num[n];
        for(int i=0;i<n;i++)
            cin>>num[i];
        for(int i=0;i<n;i++)
            T = Create_OrderBiTree(T,num[i]);
        preorder(T);
        cout<<endl;
        inorder(T);
        cout<<endl;
        postorder(T);
        cout<<endl;
        int a;
        cin>>a;
        cout<<find(T,a)<<endl;
        cin>>a;
        cout<<find(T,a)<<endl;
        cin>>a;
        T = Create_OrderBiTree(T,a);
        preorder(T);
        cout<<endl;
        inorder(T);
        cout<<endl;
        postorder(T);
        cout<<endl;
        inorder(T);
        cout<<endl;
        level(T);
    
    }