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

Rossy Yan

修改于 2024-12-26 10:27:10

2620

文章被收录于专栏：C++C++【Educoder实训】头歌实践教学平台

任务描述

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

相关知识

为了完成本关任务，你需要掌握：

创建二叉树
销毁二叉树
查找结点
求二叉树的高度
输出二叉树

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

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

创建二叉树

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

// 创建二叉树函数（简单示例，手动构建）
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;
}

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

销毁二叉树

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

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

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

查找结点

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

// 在二叉树中查找指定值的节点函数
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);
}

在上述函数中：

首先判断根节点是否为空，为空则表示没找到目标节点，返回 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;
}

在这个函数里：

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

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

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

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

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

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;
}

测试说明

平台会对你编写的代码进行测试：
测试输入： 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;
}