【数据结构】使用先序递归过程构建并打印二叉树

创作时间:

作者:

@小白创作中心

【数据结构】使用先序递归过程构建并打印二叉树

引用

CSDN

https://blog.csdn.net/yuzexuan666/article/details/138261711

二叉树是一种重要的数据结构，在计算机科学中有着广泛的应用。本文将介绍如何使用先序递归过程构建二叉树，并使用凹入法打印二叉树。

一、基础知识

1.1 什么是二叉树

二叉树是一种树形数据结构，其中每个节点最多有两个子节点，通常称为左子节点和右子节点。二叉树可以是空树，也可以由一个根节点加上两棵分别称为左子树和右子树的二叉树组成。

1.2 先序遍历

先序遍历是二叉树的一种遍历方式，其遍历顺序为：根节点 -> 左子树 -> 右子树。在先序遍历中，根节点总是第一个被访问。

二、题目要求

使用先序递归过程建立二叉树（存储结构：二叉链表），并用凹入法打印。输入数据按照先序遍历所得序列输入，当某节点左子树或右子树为空时，输入“ * ”号。如输入ABCDE** 得到的二叉树为：

三、实现效果

先序序列：ABCDE**

先序序列：ABCDEFGHIJK

四、代码实现

4.1 先序构建二叉树

BTNODE* CreateBiTree(void)
{
    char ch;
    scanf_s("%c", &ch);
    if (ch == '*') // 如果读入的是 '*'，表示该节点为空
        return NULL;
    BTNODE* T = (BTNODE*)malloc(sizeof(BTNODE));
    T->data = ch; // 将读入的字符赋值给当前节点的数据域
    T->lc = CreateBiTree(); // 递归创建左子树
    T->rc = CreateBiTree(); // 递归创建右子树
    return T;
}

这段代码实现了通过先序遍历序列构建二叉树的功能。首先读取一个字符，如果读入的是“*”，则表示该节点为空，返回NULL。否则，创建一个新的节点，将读入的字符赋值给该节点的数据域，然后递归地创建左子树和右子树。

4.2 凹入法打印二叉树

void PrintTabTab(BTNODE* T, int depth)
{
    if (T)
    {
        for (int i = 0; i < depth; i++)
            printf("__"); // 根据深度打印相应数量的缩进
        printf("%c\n", T->data); // 打印当前节点的数据
        PrintTabTab(T->lc, depth + 1); // 递归打印左子树，深度加1
        PrintTabTab(T->rc, depth + 1); // 递归打印右子树，深度加1
    }
}

这段代码实现了使用凹入法打印二叉树的功能。通过递归的方式，根据节点的深度打印相应数量的缩进，然后打印节点的数据。这样可以直观地展示二叉树的结构。