二叉树遍历（递归版）-蒲公英云

二叉树遍历（递归版）

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

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

求二叉树的高度
先序遍历二叉树
中序遍历二叉树
后序遍历二叉树
层序遍历二叉树

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

PS：

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

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

如图所示，根据上面的遍历顺序，我们可以得到以下遍历结果：
先序遍历： 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;
}