【C++数据结构——树】二叉树的基本运算(头歌实践教学平台习题)【合集】

简介: 本关任务:编写一个程序实现二叉树的基本运算。​相关知识创建二叉树销毁二叉树查找结点求二叉树的高度输出二叉树//二叉树节点结构体定义structTreeNode{intval;TreeNode*left;TreeNode*right;TreeNode(intx):val(x),left(NULL),right(NULL){}};创建二叉树//创建二叉树函数(简单示例,手动构建)TreeNode*create

目录😋

任务描述

相关知识

创建二叉树

销毁二叉树

查找结点

求二叉树的高度

输出二叉树

测试说明

我的通关代码:

测试结果:


任务描述

本关任务:编写一个程序实现二叉树的基本运算。

相关知识

为了完成本关任务,你需要掌握:

  1. 创建二叉树
  2. 销毁二叉树
  3. 查找结点
  4. 求二叉树的高度
  5. 输出二叉树

假设二叉树节点结构体定义如下:

 

// 二叉树节点结构体定义
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
image.gif
  • 创建二叉树

这里以手动构建一个简单二叉树为例,可以根据实际需求从文件、用户输入等方式获取数据来构建更复杂的二叉树。

 

// 创建二叉树函数(简单示例,手动构建)
TreeNode* createBinaryTree() {
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(5);
    root->right->left = new TreeNode(6);
    root->right->right = new TreeNode(7);
    return root;
}
image.gif

在上述函数中,通过动态分配内存创建二叉树的各个节点,并按照一定的结构关系(这里构建了一个简单的示例二叉树结构)将节点连接起来,最后返回根节点指针,代表创建好的二叉树。

  • 销毁二叉树

为了避免内存泄漏,在不再使用二叉树时,需要释放二叉树占用的内存空间,通过递归遍历二叉树,先释放子节点的内存,再释放根节点内存。

// 销毁二叉树函数(释放二叉树内存)
void destroyBinaryTree(TreeNode* root) {
    if (root == NULL) return;
    destroyBinaryTree(root->left);
    destroyBinaryTree(root->right);
    delete root;
}
image.gif

在这个函数里,首先判断根节点是否为空,如果为空则表示已经遍历完整个树或者本身就是空树,直接返回。然后递归地调用函数先销毁左子树,再销毁右子树,最后释放根节点的内存,确保整个二叉树占用的内存都被正确回收。

  • 查找结点

可以通过递归的方式在二叉树中查找指定值的节点,遍历二叉树的每个节点,比较节点值与目标值是否相等。

// 在二叉树中查找指定值的节点函数
TreeNode* findNode(TreeNode* root, int target) {
    if (root == NULL) return NULL;
    if (root->val == target) return root;
    TreeNode* leftResult = findNode(root->left, target);
    if (leftResult!= NULL) return leftResult;
    return findNode(root->right, target);
}
image.gif

在上述函数中:

  • 首先判断根节点是否为空,为空则表示没找到目标节点,返回 NULL
  • 接着比较根节点的值与目标值,如果相等则返回根节点指针。
  • 如果根节点值不等于目标值,就先递归地在左子树中查找,若在左子树中找到了(返回的指针不为 NULL),则直接返回找到的节点指针。
  • 若左子树中没找到,则继续递归在右子树中查找,并返回右子树查找的结果。
  • 求二叉树的高度

二叉树的高度定义为根节点到叶节点最长路径上的节点数,可以通过递归计算左子树高度和右子树高度,取较大值再加 1(根节点这一层)来得到整棵树的高度。

// 求二叉树高度的函数
int getHeight(TreeNode* root) {
    if (root == NULL) return 0;
    int leftHeight = getHeight(root->left);
    int rightHeight = getHeight(root->right);
    return std::max(leftHeight, rightHeight) + 1;
}
image.gif

在这个函数里:

  • 先判断根节点是否为空,为空则表示空树,高度为 0,直接返回 0。
  • 然后递归地计算左子树的高度和右子树的高度,通过 std::max 函数取两者中的较大值,再加上 1(代表根节点所在的这一层),得到整棵二叉树的高度并返回。
  • 输出二叉树

以下是使用中序遍历(可以根据需求选择前序、后序、层次遍历等其他遍历方式)的方式简单输出二叉树节点值的函数示例,方便查看二叉树结构。

 

// 输出二叉树(以中序遍历为例)的函数
void printBinaryTree(TreeNode* root) {
    if (root == NULL) return;
    printBinaryTree(root->left);
    std::cout << root->val << " ";
    printBinaryTree(root->right);
}
image.gif

在上述函数中,通过递归实现中序遍历,先递归遍历左子树,然后输出当前节点的值,最后递归遍历右子树,这样就按照中序遍历的顺序输出了二叉树的各个节点值,一定程度上展示了二叉树的结构情况。

以下是一个简单的使用示例,展示如何调用这些函数:

 

int main() {
    TreeNode* root = createBinaryTree();
    std::cout << "创建的二叉树(中序遍历输出): ";
    printBinaryTree(root);
    std::cout << std::endl;
    TreeNode* targetNode = findNode(root, 5);
    if (targetNode!= NULL) {
        std::cout << "找到节点值为5的节点" << std::endl;
    } else {
        std::cout << "未找到节点值为5的节点" << std::endl;
    }
    std::cout << "二叉树的高度: " << getHeight(root) << std::endl;
    destroyBinaryTree(root);
    return 0;
}
image.gif

测试说明

平台会对你编写的代码进行测试:

测试输入:

A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))

H


预期输出:

(1)创建二叉树

(2)输出二叉树:A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))

(3)H结点:左孩子为J 右孩子为K

(4)二叉树b的高度:7

(5)释放二叉树

测试输入:

A(B(D,E(G)),C(,F))

C

预期输出:

(1)创建二叉树

(2)输出二叉树:A(B(D,E(G)),C(,F))

(3)C结点:无左孩子 右孩子为F

(4)二叉树b的高度:4

(5)释放二叉树

开始你的任务吧,祝你成功!


通关代码

#include <iostream>
#include <string>
#define Maxsize 100
using namespace std;
typedef char ElemType;
typedef struct node {
    ElemType data;
    struct node *lchild;
    struct node *rchild;
} BTNode;
void CreateBTree(BTNode *&b, const char *str) {
    BTNode *St[Maxsize], *p;
    int top = -1, k, j = 0;
    char ch;
    b = NULL;
    ch = str[j];
    while (ch != '\0') {
        switch (ch) {
            case '(':
                top++;
                St[top] = p;
                k = 1;
                break;
            case ')':
                top--;
                break;
            case ',':
                k = 2;
                break;
            default:
                p = (BTNode *)malloc(sizeof(BTNode));
                p->data = ch;
                p->lchild = p->rchild = NULL;
                if (b == NULL)
                    b = p;
                else {
                    switch (k) {
                        case 1:
                            St[top]->lchild = p;
                            break;
                        case 2:
                            St[top]->rchild = p;
                            break;
                    }
                }
        }
        j++;
        ch = str[j];
    }
}
void DestroyBtree(BTNode *&b) {
    if (b != NULL) {
        DestroyBtree(b->lchild);
        DestroyBtree(b->rchild);
        free(b);
    }
}
BTNode *FindNode(BTNode *b, ElemType x) {
    BTNode *p;
    if (b == NULL) {
        return NULL;
    } else if (b->data == x) {
        return b;
    } else {
        p = FindNode(b->lchild, x);
        if (p != NULL) {
            return p;
        } else {
            return FindNode(b->rchild, x);
        }
    }
}
BTNode *LchildNode(BTNode *p) { return p->lchild; }
BTNode *RchildNode(BTNode *p) { return p->rchild; }
int BTHeight(BTNode *b) {
    int lchildh, rchildh;
    if (b == NULL)
        return 0;
    else {
        lchildh = BTHeight(b->lchild);
        rchildh = BTHeight(b->rchild);
        return (lchildh > rchildh) ? (lchildh + 1) : (rchildh + 1);
    }
}
void DispBTree(BTNode *b) {
    if (b != NULL) {
        cout << b->data;
        if (b->lchild != NULL || b->rchild != NULL) {
            cout << "(";
            DispBTree(b->lchild);
            if (b->rchild != NULL)
                cout << ",";
            DispBTree(b->rchild);
            cout << ")";
        }
    }
}
int main() {
    BTNode *b = NULL;
    string input;
    char searchValue;
    getline(cin, input);
    CreateBTree(b, input.c_str());
    cin >> searchValue;
    cout << "(1)创建二叉树" << endl;
    cout << "(2)输出二叉树:";
    DispBTree(b);
    cout << endl;
    cout << "(3)";
    BTNode *foundNode = FindNode(b, searchValue);
    if (foundNode != NULL) {
        cout << searchValue << "结点:";
        if (LchildNode(foundNode) != NULL) {
            cout << "左孩子为" << LchildNode(foundNode)->data;
        } else {
            cout << "无左孩子";
        }
        if (RchildNode(foundNode) != NULL) {
            cout << " 右孩子为" << RchildNode(foundNode)->data;
        } else {
            cout << " 无右孩子";
        }
        cout << endl;
    } else {
        cout << "未找到字符" << searchValue << " 的结点。" << endl;
    }
    cout << "(4)二叉树b的高度:" << BTHeight(b) << endl;
    DestroyBtree(b);
    cout << "(5)释放二叉树" << endl;
    return 0;
}

image.gif


测试结果

image.gif 编辑

image.gif 编辑

目录
相关文章
|
1月前
|
存储 C语言 C++
【C++数据结构——栈与队列】顺序栈的基本运算(头歌实践教学平台习题)【合集】
本关任务:编写一个程序实现顺序栈的基本运算。开始你的任务吧,祝你成功!​ 相关知识 初始化栈 销毁栈 判断栈是否为空 进栈 出栈 取栈顶元素 1.初始化栈 概念:初始化栈是为栈的使用做准备,包括分配内存空间(如果是动态分配)和设置栈的初始状态。栈有顺序栈和链式栈两种常见形式。对于顺序栈,通常需要定义一个数组来存储栈元素,并设置一个变量来记录栈顶位置;对于链式栈,需要定义节点结构,包含数据域和指针域,同时初始化栈顶指针。 示例(顺序栈): 以下是一个简单的顺序栈初始化示例,假设用C语言实现,栈中存储
142 77
|
1月前
|
C++ 芯片
【C++面向对象——类与对象】Computer类(头歌实践教学平台习题)【合集】
声明一个简单的Computer类,含有数据成员芯片(cpu)、内存(ram)、光驱(cdrom)等等,以及两个公有成员函数run、stop。只能在类的内部访问。这是一种数据隐藏的机制,用于保护类的数据不被外部随意修改。根据提示,在右侧编辑器补充代码,平台会对你编写的代码进行测试。成员可以在派生类(继承该类的子类)中访问。成员,在类的外部不能直接访问。可以在类的外部直接访问。为了完成本关任务,你需要掌握。
70 19
|
1月前
|
存储 人工智能 算法
【C++数据结构——图】最短路径(头歌教学实验平台习题) 【合集】
任务描述 本关任务:编写一个程序,利用Dijkstra算法,实现带权有向图的最短路径。 相关知识 为了完成本关任务,你需要掌握:Dijkst本关任务:编写一个程序,利用Dijkstra算法,实现带权有向图的最短路径。为了完成本关任务,你需要掌握:Dijkstra算法。带权有向图:该图对应的二维数组如下所示:Dijkstra算法:Dijkstra算法是指给定一个带权有向图G与源点v,求从v到G中其他顶点的最短路径。Dijkstra算法的具体步骤如下:(1)初始时,S只包含源点,即S={v},v的距离为0。
61 15
|
3天前
|
DataX
☀☀☀☀☀☀☀有关栈和队列应用的oj题讲解☼☼☼☼☼☼☼
### 简介 本文介绍了三种数据结构的实现方法:用两个队列实现栈、用两个栈实现队列以及设计循环队列。具体思路如下: 1. **用两个队列实现栈**: - 插入元素时,选择非空队列进行插入。 - 移除栈顶元素时,将非空队列中的元素依次转移到另一个队列,直到只剩下一个元素,然后弹出该元素。 - 判空条件为两个队列均为空。 2. **用两个栈实现队列**: - 插入元素时,选择非空栈进行插入。 - 移除队首元素时,将非空栈中的元素依次转移到另一个栈,再将这些元素重新放回原栈以保持顺序。 - 判空条件为两个栈均为空。
|
1月前
|
C++
【C++数据结构——栈和队列】括号配对(头歌实践教学平台习题)【合集】
【数据结构——栈和队列】括号配对(头歌实践教学平台习题)【合集】(1)遇到左括号:进栈Push()(2)遇到右括号:若栈顶元素为左括号,则出栈Pop();否则返回false。(3)当遍历表达式结束,且栈为空时,则返回true,否则返回false。本关任务:编写一个程序利用栈判断左、右圆括号是否配对。为了完成本关任务,你需要掌握:栈对括号的处理。(1)遇到左括号:进栈Push()开始你的任务吧,祝你成功!测试输入:(()))
38 7
|
1月前
|
存储 C++ 索引
【C++数据结构——栈与队列】环形队列的基本运算(头歌实践教学平台习题)【合集】
【数据结构——栈与队列】环形队列的基本运算(头歌实践教学平台习题)【合集】初始化队列、销毁队列、判断队列是否为空、进队列、出队列等。本关任务:编写一个程序实现环形队列的基本运算。(6)出队列序列:yzopq2*(5)依次进队列元素:opq2*(6)出队列序列:bcdef。(2)依次进队列元素:abc。(5)依次进队列元素:def。(2)依次进队列元素:xyz。开始你的任务吧,祝你成功!(4)出队一个元素a。(4)出队一个元素x。
44 13
【C++数据结构——栈与队列】环形队列的基本运算(头歌实践教学平台习题)【合集】
|
1月前
|
存储 C语言 C++
【C++数据结构——栈与队列】链栈的基本运算(头歌实践教学平台习题)【合集】
本关任务:编写一个程序实现链栈的基本运算。开始你的任务吧,祝你成功!​ 相关知识 初始化栈 销毁栈 判断栈是否为空 进栈 出栈 取栈顶元素 初始化栈 概念:初始化栈是为栈的使用做准备,包括分配内存空间(如果是动态分配)和设置栈的初始状态。栈有顺序栈和链式栈两种常见形式。对于顺序栈,通常需要定义一个数组来存储栈元素,并设置一个变量来记录栈顶位置;对于链式栈,需要定义节点结构,包含数据域和指针域,同时初始化栈顶指针。 示例(顺序栈): 以下是一个简单的顺序栈初始化示例,假设用C语言实现,栈中存储整数,最大
46 9
|
3月前
|
存储 缓存 算法
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式,强调了合理选择数据结构的重要性,并通过案例分析展示了其在实际项目中的应用,旨在帮助读者提升编程能力。
99 5
|
3月前
|
算法
数据结构之购物车系统(链表和栈)
本文介绍了基于链表和栈的购物车系统的设计与实现。该系统通过命令行界面提供商品管理、购物车查看、结算等功能,支持用户便捷地管理购物清单。核心代码定义了商品、购物车商品节点和购物车的数据结构,并实现了添加、删除商品、查看购物车内容及结算等操作。算法分析显示,系统在处理小规模购物车时表现良好,但在大规模购物车操作下可能存在性能瓶颈。
72 0
|
3月前
|
存储 算法
非递归实现后序遍历时,如何避免栈溢出?
后序遍历的递归实现和非递归实现各有优缺点,在实际应用中需要根据具体的问题需求、二叉树的特点以及性能和空间的限制等因素来选择合适的实现方式。
54 1