C++实现树 - 04 二叉树的构建(数组)

简介: 通过前面两讲的学习,大家可能对二叉树有了比较深的感悟,但可能会发现一个小问题,我们在构建二叉树的时候都是一个个插入的,非常的不方便。那么这节课我们就来看看,如何通过输入一个数组来快速构建起一个二叉树。这里会介绍通过顺序数组、前序数组和后序数组如何构建二叉树。
写在前面:
通过前面两讲的学习,大家可能对二叉树有了比较深的感悟,但可能会发现一个小问题,我们在构建二叉树的时候都是一个个插入的,非常的不方便。那么这节课我们就来看看,如何通过输入一个数组来快速构建起一个二叉树。这里会介绍通过顺序数组、前序数组和后序数组如何构建二叉树。

完全二叉树的构建

在前面的学习中,我们知道了完全二叉树有一个非常 nice 的性质,它每个结点的左孩子在数组中的位置等于 2x ,右孩子等于 2x+1 。通过这个性质,我们可以快速的构建起一个二叉树。
在这里插入图片描述

#include <bits/stdc++.h>
using namespace std;

struct Node {
    int data;
    Node *left_node;
    Node *right_node;
};

int n;    //表示数组长度

//递归法构建二叉树
Node *creatTree(vector<int> nums, int index) {
    //判断是否为空
    if (nums[index] == '#')
        return NULL;

    //创建新结点
    Node *root = new Node;
    root->data = nums[index];

    //设置左右指针
    if (index * 2 <= n)
        root->left_node = creatTree(nums, index * 2);    //找到左孩子
    else
        root->left_node = NULL;
    if (index * 2 + 1 <= n)
        root->right_node = creatTree(nums, index * 2 + 1);    //找到右孩子
    else
        root->right_node = NULL;

    return root;
}

//非递归构建二叉树(利用栈)—— 前序遍历
void stackCreatTree(vector<int> nums) {
    int n = nums.size();
    stack<int> s;
    int index;    //记录遍历到第几个元素
    s.push(1);    //推入根结点,开始遍历
    while (!s.empty()) {
        index = s.top();
        s.pop();
        cout << nums[index] << " ";
        //先推入右孩子
        if (index * 2 + 1 < n && nums[index * 2 + 1] != '#')
            s.push(index * 2 + 1);
        //再推入左孩子,因为是栈结构,先进后出,而且前序遍历需要优先访问所有左子树,故只有一直放在栈顶才能先访问
        if (index * 2 < n && nums[index * 2] != '#')
            s.push(index * 2);
    }
    cout << endl;
}

//前序遍历
void PreOrderTraverse(Node *root) {
    if (root) {
        cout << root->data << " ";
        PreOrderTraverse(root->left_node);
        PreOrderTraverse(root->right_node);
    }
}

int main() {
    vector<int> nums = { '#', 1, 2, 3, 4, 5, '#', 6, '#', '#', 7, 8 };    //'#'指向空,并且从下标1开始存数据
    n = nums.size();
    Node *root = creatTree(nums, 1);
    PreOrderTraverse(root);
    cout << endl;
    stackCreatTree(nums);
    return 0;
}

根据前序和后序数组构建二叉树

除了给定一个顺序存储的数组外,还可能会给定前序遍历的结果,让你构建出二叉树。这里的操作和上面比较类似,但区别是我们获取结点的左右孩子的方式变了,上面我们是根据完全二叉树的性质。
(1)这里我们可以根据前序遍历的性质,也就是遍历结果遵循 根结点 | 左子树 | 右子树 的结果。所以,我们直接可以用一个全局变量下标来记录我们遍历的位置,从头往后遍历,每次都加 1 ,这样就可以连起来了。
(2)同样,后序遍历结果是遵循 左子树 | 右子树 | 根结点 的结果。所以,我们可以从最后一个元素开始往前遍历,每次都减 1 ,同样可以构建出来。
在这里插入图片描述
这里我们不用去判断下标是否超过数组长度,因为给定的数组是一定满足要求的即左子树右子树是否为空直接看'#'就可以。

#include <bits/stdc++.h>
using namespace std;

struct Node {
    int data;
    Node *left_node;
    Node *right_node;
};

int n;    //表示数组长度
int index;    //表示遍历到的下标

//前序数组创建二叉树

Node *prevCreatTree(vector<int> nums) {
    //判断是否为空
    if (nums[index] == '#') {
        index++;
        return NULL;
    }

    //创建结点
    Node *root = new Node;
    root->data = nums[index++];
    root->left_node = prevCreatTree(nums);
    root->right_node = prevCreatTree(nums);

    return root;
}

//后序数组创建二叉树
int cnt;
Node *backCreatTree(vector<int> nums) {
    if (nums[cnt] == '#') {
        cnt--;
        return NULL;
    }
    Node *root = new Node;
    root->data = nums[cnt--];
    root->right_node = backCreatTree(nums);
    root->left_node = backCreatTree(nums);
    return root;
}

//中序遍历
void InOrderTraverse(Node *root) {
    if (root) {
        InOrderTraverse(root->left_node);
        cout << root->data << " ";
        InOrderTraverse(root->right_node);
    }
}


int main() {
    //'#'指向空
    vector<int> nums1 = { 1, 2, 3, '#', '#', 4, '#', '#', 5, '#', '#' };
    vector<int> nums2 = {'#', '#', 3, '#', '#', 4, 2, '#', '#', 5, 1};
    index = 0;    //初始化下标
    Node *prev_root = prevCreatTree(nums1);
    InOrderTraverse(prev_root);
    cout << endl;
    cnt = nums2.size() - 1;
    Node *back_root = backCreatTree(nums2);
    InOrderTraverse(back_root);
    return 0;
}

如果大家有什么问题的话,欢迎在下方评论区进行讨论哦~

目录
相关文章
|
29天前
|
存储 C++
【C++数据结构——树】哈夫曼树(头歌实践教学平台习题) 【合集】
【数据结构——树】哈夫曼树(头歌实践教学平台习题)【合集】目录 任务描述 相关知识 测试说明 我的通关代码: 测试结果:任务描述 本关任务:编写一个程序构建哈夫曼树和生成哈夫曼编码。 相关知识 为了完成本关任务,你需要掌握: 1.如何构建哈夫曼树, 2.如何生成哈夫曼编码。 测试说明 平台会对你编写的代码进行测试: 测试输入: 1192677541518462450242195190181174157138124123 (用户分别输入所列单词的频度) 预
58 14
【C++数据结构——树】哈夫曼树(头歌实践教学平台习题) 【合集】
|
29天前
|
Java C++
【C++数据结构——树】二叉树的基本运算(头歌实践教学平台习题)【合集】
本关任务:编写一个程序实现二叉树的基本运算。​ 相关知识 创建二叉树 销毁二叉树 查找结点 求二叉树的高度 输出二叉树 //二叉树节点结构体定义 structTreeNode{ intval; TreeNode*left; TreeNode*right; TreeNode(intx):val(x),left(NULL),right(NULL){} }; 创建二叉树 //创建二叉树函数(简单示例,手动构建) TreeNode*create
45 12
|
29天前
|
C++
【C++数据结构——树】二叉树的性质(头歌实践教学平台习题)【合集】
本文档介绍了如何根据二叉树的括号表示串创建二叉树,并计算其结点个数、叶子结点个数、某结点的层次和二叉树的宽度。主要内容包括: 1. **定义二叉树节点结构体**:定义了包含节点值、左子节点指针和右子节点指针的结构体。 2. **实现构建二叉树的函数**:通过解析括号表示串,递归地构建二叉树的各个节点及其子树。 3. **使用示例**:展示了如何调用 `buildTree` 函数构建二叉树并进行简单验证。 4. **计算二叉树属性**: - 计算二叉树节点个数。 - 计算二叉树叶子节点个数。 - 计算某节点的层次。 - 计算二叉树的宽度。 最后,提供了测试说明及通关代
41 10
|
29天前
|
存储 算法 搜索推荐
【C++面向对象——群体类和群体数据的组织】实现含排序功能的数组类(头歌实践教学平台习题)【合集】
1. **相关排序和查找算法的原理**:介绍直接插入排序、直接选择排序、冒泡排序和顺序查找的基本原理及其实现代码。 2. **C++ 类与成员函数的定义**:讲解如何定义`Array`类,包括类的声明和实现,以及成员函数的定义与调用。 3. **数组作为类的成员变量的处理**:探讨内存管理和正确访问数组元素的方法,确保在类中正确使用动态分配的数组。 4. **函数参数传递与返回值处理**:解释排序和查找函数的参数传递方式及返回值处理,确保函数功能正确实现。 通过掌握这些知识,可以顺利地将排序和查找算法封装到`Array`类中,并进行测试验证。编程要求是在右侧编辑器补充代码以实现三种排序算法
38 5
|
29天前
|
存储 算法 测试技术
【C++数据结构——树】二叉树的遍历算法(头歌教学实验平台习题) 【合集】
本任务旨在实现二叉树的遍历,包括先序、中序、后序和层次遍历。首先介绍了二叉树的基本概念与结构定义,并通过C++代码示例展示了如何定义二叉树节点及构建二叉树。接着详细讲解了四种遍历方法的递归实现逻辑,以及层次遍历中队列的应用。最后提供了测试用例和预期输出,确保代码正确性。通过这些内容,帮助读者理解并掌握二叉树遍历的核心思想与实现技巧。
47 2
|
2月前
|
机器学习/深度学习 人工智能 自然语言处理
C++构建 GAN 模型:生成器与判别器平衡训练的关键秘籍
生成对抗网络(GAN)是AI领域的明星,尤其在C++中构建时,平衡生成器与判别器的训练尤为关键。本文探讨了GAN的基本架构、训练原理及平衡训练的重要性,提出了包括合理初始化、精心设计损失函数、动态调整学习率、引入正则化技术和监测训练过程在内的五大策略,旨在确保GAN模型在C++环境下的高效、稳定训练,以生成高质量的结果,推动AI技术的发展。
87 10
|
3月前
|
存储 C++
【C++】AVL树
AVL树是一种自平衡二叉搜索树,由Georgy Adelson-Velsky和Evgenii Landis提出。它通过确保任意节点的两子树高度差不超过1来维持平衡,支持高效插入、删除和查找操作,时间复杂度为O(log n)。AVL树通过四种旋转操作(左旋、右旋、左-右旋、右-左旋)来恢复树的平衡状态,适用于需要频繁进行数据操作的场景。
82 2
|
5月前
|
C++ Windows
HTML+JavaScript构建C++类代码一键转换MASM32代码平台
HTML+JavaScript构建C++类代码一键转换MASM32代码平台
|
5月前
|
C++
HTML+JavaScript构建一个将C/C++定义的ANSI字符串转换为MASM32定义的DWUniCode字符串的工具
HTML+JavaScript构建一个将C/C++定义的ANSI字符串转换为MASM32定义的DWUniCode字符串的工具
|
29天前
|
C++ 芯片
【C++面向对象——类与对象】Computer类(头歌实践教学平台习题)【合集】
声明一个简单的Computer类,含有数据成员芯片(cpu)、内存(ram)、光驱(cdrom)等等,以及两个公有成员函数run、stop。只能在类的内部访问。这是一种数据隐藏的机制,用于保护类的数据不被外部随意修改。根据提示,在右侧编辑器补充代码,平台会对你编写的代码进行测试。成员可以在派生类(继承该类的子类)中访问。成员,在类的外部不能直接访问。可以在类的外部直接访问。为了完成本关任务,你需要掌握。
66 19