二叉树遍历

╰+攻爆jí腚メ 2022-06-04 05:35 299阅读 0赞

#include<iostream> 
    #include<queue> 
    using namespace std;  
    
    //二叉树结点 
    typedef struct BiTNode
    {  
        //数据 
        char data;  
        //左右孩子指针 
        struct BiTNode *lchild,*rchild;  
    }BiTNode,*BiTree;  
    
    //按先序序列创建二叉树 
    int CreateBiTree(BiTree &T)
    {  
        char data;  
        //按先序次序输入二叉树中结点的值（一个字符），‘#’表示空树 
        cin>>data;  
        if(data == '#')
        {  
            T = NULL;  
        }  
        else
        {  
            T = (BiTree)malloc(sizeof(BiTNode));  
            //生成根结点 
            T->data = data;  
            //构造左子树 
            CreateBiTree(T->lchild);  
            //构造右子树 
            CreateBiTree(T->rchild);  
        }  
        return 0;  
    }  
    //输出 
    void Visit(BiTree T)
    {  
        if(T->data != '#')
        {  
            printf("%c ",T->data);  
        }  
    }  
    //先序遍历 
    void PreOrder(BiTree T)
    {  
        if(T != NULL)
        {  
            //访问根节点 
            Visit(T);  
            //访问左子结点 
            PreOrder(T->lchild);  
            //访问右子结点 
            PreOrder(T->rchild);  
        }  
    }  
    //中序遍历 
    void InOrder(BiTree T)
    {    
        if(T != NULL)
        {    
            //访问左子结点 
            InOrder(T->lchild);    
            //访问根节点 
            Visit(T);    
            //访问右子结点 
            InOrder(T->rchild);    
        }    
    }    
    //后序遍历 
    void PostOrder(BiTree T)
    {  
        if(T != NULL)
        {  
            //访问左子结点 
            PostOrder(T->lchild);  
            //访问右子结点 
            PostOrder(T->rchild);  
            //访问根节点 
            Visit(T);  
        }  
    }  
    
    //层次遍历 
    void LevelOrder(BiTree T)
    {  
        BiTree p = T;  
        //队列 
        queue<BiTree> queue;  
        //根节点入队 
        queue.push(p);  
        //队列不空循环 
        while(!queue.empty())
        {  
            //对头元素出队 
            p = queue.front();  
            //访问p指向的结点 
            printf("%c ",p->data);  
            //退出队列 
            queue.pop();  
            //左子树不空，将左子树入队 
            if(p->lchild != NULL)
            {  
                queue.push(p->lchild);  
            }  
            //右子树不空，将右子树入队 
            if(p->rchild != NULL)
            {  
                queue.push(p->rchild);  
            }  
        }  
    }  
    int main()  //测试数据 abd###ce##f##
    {  
        BiTree T;  
        CreateBiTree(T);  
        printf("先序遍历：\n");  
        PreOrder(T);  
        printf("\n");  
    
        printf("中序遍历：\n");  
        InOrder(T);  
        printf("\n");  
    
        printf("后序遍历：\n");  
        PostOrder(T);  
        printf("\n");  
    
        printf("层次遍历：\n");  
        LevelOrder(T);  
        printf("\n");  
        return 0;  
    }