AI 助理
备案控制台
开发者社区 数据库 文章 正文

数据结构 二叉树

2022-12-04 186
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 数据结构 二叉树

1. DS二叉树–二叉树构建与遍历


题目描述


给定一颗二叉树的逻辑结构如下图，（先序遍历的结果，空树用字符‘0’表示，例如AB0C00D00），建立该二叉树的二叉链式存储结构，并输出该二叉树的先序遍历、中序遍历和后序遍历结果


a8943e4fd22a41c8b99ea8a8703103dc.png


本题目的代码框架参考如下

6186bd91398f43a6b620fac45a0751a2.png

三种遍历的代码框架

46338e6c032b40b3884af80134cd7c94.png

主函数如下：

75b6e421ecbc40c082121f999b33606c.png


输入


第一行输入一个整数t，表示有t个二叉树


第二行起输入每个二叉树的先序遍历结果，空树用字符‘0’表示，连续输入t行


输出


输出每个二叉树的先序遍历、中序遍历和后序遍历结果


输入样例


2

AB0C00D00

AB00C00


输出样例


ABCD

BCAD

CBDA

ABC

BAC

BCA


参考代码

#include <iostream>
using namespace std;
class treenode
{
public:
    char data;
    treenode *left;
    treenode *right;
    treenode()
    {
        data = '0';
        left = NULL;
        right = NULL;
    }
};
class tree
{
public:
    void create(treenode *&p)
    {
        char word;
        cin >> word;
        if (word != '0')
        {
            p = new treenode();
            p->data = word;
            create(p->left);
            create(p->right);
        }
        else
        {
            p = NULL;
        }
    }
    void preorder(treenode *p)
    {
        if (p != NULL)
        {
            cout << p->data;
            preorder(p->left);
            preorder(p->right);
        }
    }
    void inorder(treenode *p)
    {
        if (p != NULL)
        {
            inorder(p->left);
            cout << p->data;
            inorder(p->right);
        }
    }
    void postorder(treenode *p)
    {
        if (p != NULL)
        {
            postorder(p->left);
            postorder(p->right);
            cout << p->data;
        }
    }
};
int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        tree p;
        treenode *root;
        p.create(root);
        p.preorder(root);
        cout << endl;
        p.inorder(root);
        cout << endl;
        p.postorder(root);
        cout << endl;
    }
}

2. DS二叉树–叶子数量


题目描述


计算一颗二叉树包含的叶子结点数量。


提示：叶子是指它的左右孩子为空。


建树方法采用“先序遍历+空树用0表示”的方法，即给定一颗二叉树的先序遍历的结果为AB0C00D00，其中空节点用字符‘0’表示。则该树的逻辑结构如下图。

11c1c3bd82ed47a599ea471731dc8757.png


输入

第一行输入一个整数t，表示有t个测试数据


第二行起输入二叉树先序遍历的结果，空树用字符‘0’表示，输入t行


输出


逐行输出每个二叉树的包含的叶子数量


输入样例


3

AB0C00D00

AB00C00

ABC00D00E00


输出样例


2

2

3


参考代码

#include <iostream>
using namespace std;
class treenode
{
public:
    char data;
    treenode *left;
    treenode *right;
    treenode()
    {
        data = '0';
        left = NULL;
        right = NULL;
    }
};
class tree
{
public:
    int count = 0;
    void create(treenode *&p)
    {
        char word;
        cin >> word;
        if (word != '0')
        {
            p = new treenode();
            p->data = word;
            create(p->left);
            create(p->right);
        }
        else
        {
            p = NULL;
        }
    }
    int preorder(treenode *p)
    {
        if (p != NULL)
        {
            if (p->left == NULL && p->right == NULL)
                count++;
            else
            {
                preorder(p->left);
                preorder(p->right);
            }
        }
        return count;
    }
    void inorder(treenode *p)
    {
        if (p != NULL)
        {
            inorder(p->left);
            cout << p->data;
            inorder(p->right);
        }
    }
    void postorder(treenode *p)
    {
        if (p != NULL)
        {
            postorder(p->left);
            postorder(p->right);
            cout << p->data;
        }
    }
};
int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        tree p;
        treenode *root;
        p.create(root);
        cout << p.preorder(root);
        cout << endl;
    }
}


3. DS二叉树——二叉树之父子结点


题目描述


给定一颗二叉树的逻辑结构如下图，（先序遍历的结果，空树用字符‘0’表示，例如AB0C00D00），建立该二叉树的二叉链式存储结构。


编写程序输出该树的所有叶子结点和它们的父亲结点

c97ab8f1df584b6f9b14655d8132bca9.png


输入


第一行输入一个整数t，表示有t个二叉树


第二行起，按照题目表示的输入方法，输入每个二叉树的先序遍历，连续输入t行


输出


第一行按先序遍历，输出第1个示例的叶子节点


第二行输出第1个示例中与叶子相对应的父亲节点


以此类推输出其它示例的结果


输入样例


3

AB0C00D00

AB00C00

ABCD0000EF000


输出样例


C D

B A

B C

A A

D F

C E


参考代码

#include <iostream>
#include <queue>
using namespace std;
class treenode
{
public:
    char data;
    treenode *left;
    treenode *right;
    treenode()
    {
        data = '0';
        left = NULL;
        right = NULL;
    }
};
class tree
{
public:
    queue<treenode *> leaves;
    queue<treenode *> pres;
    void create(treenode *&p)
    {
        char word;
        cin >> word;
        if (word != '0')
        {
            p = new treenode();
            p->data = word;
            create(p->left);
            create(p->right);
        }
        else
        {
            p = NULL;
        }
    }
    void preorder(treenode *p)
    {
        preordermethod(p, NULL);
        while (!leaves.empty())
        {
            cout << leaves.front()->data << " ";
            leaves.pop();
        }
        cout << endl;
        while (!pres.empty())
        {
            cout << pres.front()->data << " ";
            pres.pop();
        }
        cout << endl;
    }
    void preordermethod(treenode *leave, treenode *pre)
    {
        if (leave != NULL)
        {
            if (leave->left == NULL && leave->right == NULL)
            {
                leaves.push(leave);
                pres.push(pre);
            }
            else
            {
                preordermethod(leave->left, leave);
                preordermethod(leave->right, leave);
            }
        }
    }
    void inorder(treenode *p)
    {
        if (p != NULL)
        {
            inorder(p->left);
            cout << p->data;
            inorder(p->right);
        }
    }
    void postorder(treenode *p)
    {
        if (p != NULL)
        {
            postorder(p->left);
            postorder(p->right);
            cout << p->data;
        }
    }
};
int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        tree p;
        treenode *root;
        p.create(root);
        p.preorder(root);
    }
}


4. DS树–二叉树高度


题目描述


给出一棵二叉树，求它的高度。二叉树的创建采用前面实验的方法。


注意，二叉树的层数是从1开始


输入


第一行输入一个整数t，表示有t个二叉树


第二行起输入每个二叉树的先序遍历结果，空树用字符‘0’表示，连续输入t行


输出


每行输出一个二叉树的高度


输入样例


1

AB0C00D00


输出样例


3


参考代码

#include <iostream>
using namespace std;
class treenode
{
public:
    char data;
    treenode *left;
    treenode *right;
    treenode()
    {
        data = '0';
        left = NULL;
        right = NULL;
    }
};
class tree
{
public:
    int count = 0;
    void create(treenode *&p)
    {
        char word;
        cin >> word;
        if (word != '0')
        {
            p = new treenode();
            p->data = word;
            create(p->left);
            create(p->right);
        }
        else
        {
            p = NULL;
        }
    }
    int preorder(treenode *p, int num)
    {
        if (p != NULL)
        {
            if (p->left == NULL && p->right == NULL && num > count)
            {
                count = num;
            }
            else
            {
                preorder(p->left, num + 1);
                preorder(p->right, num + 1);
            }
        }
        return count;
    }
    void inorder(treenode *p)
    {
        if (p != NULL)
        {
            inorder(p->left);
            cout << p->data;
            inorder(p->right);
        }
    }
    void postorder(treenode *p)
    {
        if (p != NULL)
        {
            postorder(p->left);
            postorder(p->right);
            cout << p->data;
        }
    }
};
int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        tree p;
        treenode *root;
        p.create(root);
        cout << p.preorder(root, 1);
        cout << endl;
    }
}


5. DS二叉树——二叉树之数组存储


题目描述


二叉树可以采用数组的方法进行存储，把数组中的数据依次自上而下,自左至右存储到二叉树结点中，一般二叉树与完全二叉树对比，比完全二叉树缺少的结点就在数组中用0来表示。，如下图所示


从上图可以看出，右边的是一颗普通的二叉树，当它与左边的完全二叉树对比，发现它比完全二叉树少了第5号结点，所以在数组中用0表示，同样它还少了完全二叉树中的第10、11号结点，所以在数组中也用0表示。


结点存储的数据均为非负整数


输入


第一行输入一个整数t，表示有t个二叉树


第二行起，每行输入一个数组，先输入数组长度，再输入数组内数据，每个数据之间用空格隔开，输入的数据都是非负整数


连续输入t行


输出


每行输出一个示例的先序遍历结果，每个结点之间用空格隔开


输入样例


3

3 1 2 3

5 1 2 3 0 4

13 1 2 3 4 0 5 6 7 8 0 0 9 10


输出样例


1 2 3

1 2 4 3

1 2 4 7 8 3 5 9 10 6


参考代码

#include <iostream>
#include <queue>
using namespace std;
class treenode
{
public:
    int data;
    treenode *left;
    treenode *right;
};
class tree
{
public:
    void create(treenode *&p)
    {
        int word;
        cin >> word;
        if (word != 0)
        {
            p = new treenode();
            p->data = word;
            create(p->left);
            create(p->right);
        }
        else
        {
            p = NULL;
        }
    }
    void levelcreate(treenode *&p, int num)
    {
        queue<treenode *> l;
        int count = 0;
        int data;
        cin >> data;
        count++;
        if (data)
        {
            p = new treenode();
            p->data = data;
            l.push(p);
        }
        else
        {
            p = NULL;
        }
        while (!l.empty() && count < num)
        {
            treenode *node = l.front();
            cin >> data;
            int flag = 0;
            count++;
            if (data)
            {
                node->left = new treenode();
                node->left->data = data;
                l.push(node->left);
                flag = 1;
            }
            else
            {
                node->left = NULL;
            }
            cin >> data;
            count++;
            if (data)
            {
                node->right = new treenode();
                node->right->data = data;
                l.push(node->right);
                flag = 1;
            }
            else
            {
                node->right = NULL;
            }
            if (flag)
                l.pop();
        }
    }
    void preorder(treenode *p)
    {
        if (p != NULL)
        {
            cout << p->data << " ";
            preorder(p->left);
            preorder(p->right);
        }
    }
};
int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        tree p;
        treenode *root;
        int num;
        cin >> num;
        p.levelcreate(root, num);
        p.preorder(root);
        cout << endl;
    }
}


文章标签：
数据库管理
存储
关键词：
数据结构二叉树
wstqfqdpnmll4
目录
相关文章
RossyYan
|
9天前
|
Java C++
【C++数据结构——树】二叉树的基本运算（头歌实践教学平台习题）【合集】
本关任务：编写一个程序实现二叉树的基本运算。​ 相关知识 创建二叉树 销毁二叉树 查找结点 求二叉树的高度 输出二叉树 //二叉树节点结构体定义 structTreeNode{ intval; TreeNode*left; TreeNode*right; TreeNode(intx):val(x),left(NULL),right(NULL){} }; 创建二叉树 //创建二叉树函数（简单示例，手动构建） TreeNode*create
RossyYan
34 12
RossyYan
|
9天前
|
C++
【C++数据结构——树】二叉树的性质（头歌实践教学平台习题）【合集】
本文档介绍了如何根据二叉树的括号表示串创建二叉树，并计算其结点个数、叶子结点个数、某结点的层次和二叉树的宽度。主要内容包括： 1. **定义二叉树节点结构体**：定义了包含节点值、左子节点指针和右子节点指针的结构体。 2. **实现构建二叉树的函数**：通过解析括号表示串，递归地构建二叉树的各个节点及其子树。 3. **使用示例**：展示了如何调用 `buildTree` 函数构建二叉树并进行简单验证。 4. **计算二叉树属性**： - 计算二叉树节点个数。 - 计算二叉树叶子节点个数。 - 计算某节点的层次。 - 计算二叉树的宽度。 最后，提供了测试说明及通关代
RossyYan
33 10
RossyYan
|
9天前
|
存储 算法 测试技术
【C++数据结构——树】二叉树的遍历算法（头歌教学实验平台习题） 【合集】
本任务旨在实现二叉树的遍历，包括先序、中序、后序和层次遍历。首先介绍了二叉树的基本概念与结构定义，并通过C++代码示例展示了如何定义二叉树节点及构建二叉树。接着详细讲解了四种遍历方法的递归实现逻辑，以及层次遍历中队列的应用。最后提供了测试用例和预期输出，确保代码正确性。通过这些内容，帮助读者理解并掌握二叉树遍历的核心思想与实现技巧。
RossyYan
31 2
三三是该溜子
|
23天前
|
数据库
数据结构中二叉树，哈希表，顺序表，链表的比较补充
二叉搜索树，哈希表，顺序表，链表的特点的比较
三三是该溜子
34 0
数据结构中二叉树，哈希表，顺序表，链表的比较补充
XIAZHI
|
2月前
|
机器学习/深度学习 存储 算法
数据结构实验之二叉树实验基础
本实验旨在掌握二叉树的基本特性和遍历算法，包括先序、中序、后序的递归与非递归遍历方法。通过编程实践，加深对二叉树结构的理解，学习如何计算二叉树的深度、叶子节点数等属性。实验内容涉及创建二叉树、实现各种遍历算法及求解特定节点数量。
XIAZHI
111 4
ephemerals__
|
2月前
|
C语言
【数据结构】二叉树（c语言）（附源码）
本文介绍了如何使用链式结构实现二叉树的基本功能，包括前序、中序、后序和层序遍历，统计节点个数和树的高度，查找节点，判断是否为完全二叉树，以及销毁二叉树。通过手动创建一棵二叉树，详细讲解了每个功能的实现方法和代码示例，帮助读者深入理解递归和数据结构的应用。
ephemerals__
168 8
java冯坚持
|
3月前
|
存储 算法 关系型数据库
数据结构与算法学习二一：多路查找树、二叉树与B树、2-3树、B+树、B*树。（本章为了解基本知识即可，不做代码学习）
这篇文章主要介绍了多路查找树的基本概念，包括二叉树的局限性、多叉树的优化、B树及其变体（如2-3树、B+树、B*树）的特点和应用，旨在帮助读者理解这些数据结构在文件系统和数据库系统中的重要性和效率。
java冯坚持
39 0
数据结构与算法学习二一：多路查找树、二叉树与B树、2-3树、B+树、B*树。（本章为了解基本知识即可，不做代码学习）
java冯坚持
|
3月前
|
存储 算法 搜索推荐
数据结构与算法学习十七：顺序储存二叉树、线索化二叉树
这篇文章主要介绍了顺序存储二叉树和线索化二叉树的概念、特点、实现方式以及应用场景。
java冯坚持
50 0
数据结构与算法学习十七：顺序储存二叉树、线索化二叉树
GuGuStudy
|
3月前
|
Java
【用Java学习数据结构系列】震惊，二叉树原来是要这么学习的（二）
【用Java学习数据结构系列】震惊，二叉树原来是要这么学习的（二）
GuGuStudy
38 1
GuGuStudy
|
3月前
|
算法 Java C语言
【用Java学习数据结构系列】震惊，二叉树原来是要这么学习的（一）
【用Java学习数据结构系列】震惊，二叉树原来是要这么学习的（一）
GuGuStudy
32 1

热门文章

最新文章

  • 1
    【C++数据结构——栈与队列】顺序栈的基本运算（头歌实践教学平台习题）【合集】
  • 2
    局域网屏幕监控系统中的Python数据结构与算法实现
  • 3
    【C++数据结构——查找】二分查找（头歌实践教学平台习题）【合集】
  • 4
    Pandas数据结构：Series与DataFrame
  • 5
    探索局域网电脑监控软件：Python算法与数据结构的巧妙结合
  • 6
    【C++数据结构——树】哈夫曼树（头歌实践教学平台习题） 【合集】
  • 7
    【C++数据结构——图】最短路径（头歌教学实验平台习题） 【合集】
  • 8
    【C++数据结构——内排序】希尔排序（头歌实践教学平台习题）【合集】
  • 9
    【C++数据结构——查找】二叉排序树（头歌实践教学平台习题）【合集】
  • 10
    【C++数据结构——树】二叉树的性质（头歌实践教学平台习题）【合集】
  • 1
    Python 数据结构和算法实用指南（四）（4）
    306
  • 2
    Python 数据结构和算法实用指南（四）（3）
    48
  • 3
    Python 数据结构和算法实用指南（四）（2）
    32
  • 4
    Python 数据结构和算法实用指南（三）（3）
    34
  • 5
    Python 数据结构和算法实用指南（三）（1）
    42
  • 6
    Python 数据结构和算法实用指南（二）（4）
    41
  • 7
    Python 数据结构和算法实用指南（二）（3）
    45
  • 8
    Python 数据结构和算法实用指南（二）（2）
    28
  • 9
    Python 数据结构和算法实用指南（一）（2）
    42
  • 10
    【Python进阶（七）】——Series数据结构
    198

    • 相关课程

    更多
  • Go语言核心编程 - 数据结构和算法

    • 相关电子书

    更多
  • 如何使用Tair增强数据结构构建丰富在线实时场景
  • Apache Flink 流式应用中状态的数据结构定义升级
  • 低代码开发师（初级）实战教程
    • 下一篇
    DataWorks智能交互式数据开发与分析之旅