二叉树遍历（递归版）

男娘i 2022-06-16 04:58 192阅读 0赞

问题描述：  
以一定的方式输入数据（本文是以先序遍历的方式输入），程序根据数据进行解析，创建二叉树，然后对二叉树进行操作，主要操作包括以下几种：

1.  求二叉树的高度
2.  先序遍历二叉树
3.  中序遍历二叉树
4.  后序遍历二叉树
5.  层序遍历二叉树

先序遍历： 根节点->左子树->右子树  
中序遍历： 左子树->根节点->右子树  
先序遍历： 左子树->右子树->根节点  
层序遍历： 第一层（根节点）->第二层->第三次->….

PS：  
1. 大家可以清楚的看到，先序，中序和后序是相对于根节点而言的  
2. 非递归版本可以查看我的另外一篇文章：  
[http://blog.csdn.net/yi\_ming\_he/article/details/71272568][http_blog.csdn.net_yi_ming_he_article_details_71272568]

以下面的例子进行说明：  
![这里写图片描述][SouthEast]

如图所示，根据上面的遍历顺序，我们可以得到以下遍历结果：  
先序遍历： a b d h e c f g  
中序遍历： h d b e a f c g  
后序遍历： h d e b f g c a  
层序遍历： a b c d e f g h

参考代码：

#include <stdio.h>
    #include <malloc.h>
    #include <queue>
    
    typedef struct BiTNode
    {
        char data;
        struct BiTNode* lchild;
        struct BiTNode* rchild;
    }BiTNode, *Bitree;
    
    void CreateBiTree(Bitree& T)
    {
        char ch;
        scanf_s("%c", &ch);
        //按照先序输入输入二叉树中的节点值，其中#表示空树
        if (ch == '#')
            T = NULL;
        else
        {
            T = (Bitree)malloc(sizeof(BiTNode));
            T->data = ch;
            CreateBiTree(T->lchild);
            CreateBiTree(T->rchild);
        }
    }
    
    void PreOrderTraverseByRecursion(Bitree T)
    {
        if (!T)
            return;
    
        printf("%c ", T->data);
        PreOrderTraverseByRecursion(T->lchild);
        PreOrderTraverseByRecursion(T->rchild);
    }
    
    void InOrderTraverseByRecursion(Bitree T)
    {
        if (!T)
            return;
    
        InOrderTraverseByRecursion(T->lchild);
        printf("%c ", T->data);
        InOrderTraverseByRecursion(T->rchild);
    }
    
    void PostOrderTraverseByRecursion(Bitree T)
    {
        if (!T)
            return;
    
        PostOrderTraverseByRecursion(T->lchild);
        PostOrderTraverseByRecursion(T->rchild);
        printf("%c ", T->data);
    }
    
    int GetBiTreeHeight(Bitree T)
    {
        if (!T)
            return 0;
    
        int nLeftHeight = GetBiTreeHeight(T->lchild);
        int nRightHeight = GetBiTreeHeight(T->rchild);
    
        return (nLeftHeight > nRightHeight ? nLeftHeight : nRightHeight) + 1;
    }
    
    void TraverseTreeByLevel(Bitree T, int nLevel)
    {
        if (!T || nLevel < 1)
            return;
    
        if (1 == nLevel)
        {
            printf("%c ", T->data);
            return;
        }
    
        TraverseTreeByLevel(T->lchild, nLevel - 1);
        TraverseTreeByLevel(T->rchild, nLevel - 1);
    }
    
    void LevelOrderTraverseByRecursion(Bitree T)
    {
        int nHeight = GetBiTreeHeight(T);
        for (int i = 1; i <= nHeight; i++)
            TraverseTreeByLevel(T, i);
    }
    
    int main()
    {
        Bitree T;
        CreateBiTree(T);
        printf("树的高度是: %d\n", GetBiTreeHeight(T));
    
        printf("先序遍历(递归)：\n");
        PreOrderTraverseByRecursion(T);
        printf("\n");
    
        printf("中序遍历(递归)：\n");
        InOrderTraverseByRecursion(T);
        printf("\n");
    
        printf("后序遍历(递归)：\n");
        PostOrderTraverseByRecursion(T);
        printf("\n");
    
        printf("层序遍历(递归)：\n");
        LevelOrderTraverseByRecursion(T);
        printf("\n");
    
        return 0;
    }

运行结果：  
![这里写图片描述][SouthEast 1]

[http_blog.csdn.net_yi_ming_he_article_details_71272568]: http://blog.csdn.net/yi_ming_he/article/details/71272568
[SouthEast]: /images/20220616/d217c13a832249c286033876e3eb3d4b.png
[SouthEast 1]: /images/20220616/d70ea295ad604c26af9d49d9c7aa8972.png