二叉树的递归遍历

lixiangrong
2024-01-29 / 0 评论 / 41 阅读 / 正在检测是否收录...

二叉树的递归遍历

#include <stdio.h>
#include <stdlib.h>

// 7.4.2 二叉树的递归遍历
typedef char dataType; // 结点值的类型
typedef struct treeNode
{
    dataType data; // 结点数据域
    struct treeNode *lChild, *rChild; // 左、右孩子指针
}node, *binaryTree;

// 1.按照前序遍历的顺序建立给定的二叉树
binaryTree createTree()
{
    char c;
    binaryTree t;
    if((c = getchar()) == '#')
        t = NULL;
    else
    {
        t = (node *) malloc(sizeof(node));
        t->data = c;
        t->lChild = createTree();
        t->rChild = createTree();
    }
    return t;
}

// 2. 前序遍历
void preOrder(binaryTree t)
{
    if(t)
    {
        printf("%c ",t->data);
        preOrder(t->lChild);
        preOrder(t->rChild);
    }
}

// 3. 中序遍历
void inOrder(binaryTree t)
{
    if(t)
    {
        inOrder(t->lChild);
        printf("%c ",t->data);
        inOrder(t->rChild);
    }
}

// 4. 后序遍历
void postOrder(binaryTree t)
{
    if(t)
    {
        postOrder(t->lChild);
        postOrder(t->rChild);
        printf("%c ",t->data);
    }
}

int main()
{
    binaryTree tree; // 声明二叉树
    printf("请输入结点,创建一颗二叉树,#表示空结点:\n");
    tree = createTree(); // ABD#E##FG###C##
    printf("前序遍历\n");
    preOrder(tree);
    printf("\n中序遍历\n");
    inOrder(tree);
    printf("\n后序遍历\n");
    postOrder(tree);
    return 0;
}
0

评论 (0)

取消