【C++数据结构——树】二叉树的性质（头歌实践教学平台习题）【合集】

目录😋

本关任务

相关知识

根据二叉树的括号表示串，创建二叉树

   1. 定义二叉树节点结构体

   2. 实现构建二叉树的函数

   3. 使用示例

计算二叉树的结点个数、叶子结点个数、某结点的层次和二叉树的宽度  

   1. 计算二叉树节点个数

   2. 计算二叉树叶子节点个数

   3. 计算某节点的层次

   4. 计算二叉树的宽度

测试说明

通关代码

测试结果

本关任务

编写一个程序验证二叉树的性质。

相关知识

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

1. 根据二叉树的括号表示串，创建二叉树b。
2. 计算二叉树的结点个数、叶子结点个数、某结点的层次和二叉树的宽度。

根据二叉树的括号表示串，创建二叉树

   1. 定义二叉树节点结构体

首先，需要定义二叉树节点的结构体，它包含节点的值、左子节点指针和右子节点指针:

#include <iostream>
#include <string>

using namespace std;

// 二叉树节点结构体定义
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* left() const { return left; }
    void setLeft(TreeNode* node) { left = node; }
    TreeNode* right;
    TreeNode* right() const { return right; }
    void setRight(TreeNode* node) { right = node; }
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

   2. 实现构建二叉树的函数

下面的函数 buildTree 用于根据给定的括号表示串来构建二叉树，思路是通过解析字符串，递归地构建各个节点及其子树

class Solution {
public:
    TreeNode* buildTree(string s) {
        if (s.empty()) return nullptr;
        int idx = 1;  // 跳过最外层括号，从下一个字符开始
        int val = 0;
        bool isNegative = false;
        // 解析出根节点的值
        if (s[idx] == '-') {
            isNegative = true;
            idx++;
        }
        while (idx < s.size() && isdigit(s[idx])) {
            val = val * 10 + (s[idx] - '0');
            idx++;
        }
        if (isNegative) val = -val;
        TreeNode* root = new TreeNode(val);

        int count = 0;  // 用于记录括号的匹配情况
        string leftSubtree = "";
        // 寻找左子树对应的括号表示部分
        for (int i = idx; i < s.size(); ++i) {
            if (s[i] == '(') count++;
            else if (s[i] == ')') count--;
            leftSubtree += s[i];
            if (count == 0 && leftSubtree!= "") break;
        }
        root->left = buildTree(leftSubtree);

        string rightSubtree = "";
        // 提取右子树对应的括号表示部分
        for (int i = leftSubtree.size() + idx + 1; i < s.size() - 1; ++i) {
            rightSubtree += s[i];
        }
        root->right = buildTree(rightSubtree);

        return root;
    }
};

​​上述代码中：

• 首先判断输入的字符串是否为空，如果为空则直接返回 nullptr，表示构建空二叉树。
• 接着解析出根节点的值：跳过最外层括号后，处理可能存在的负号，然后按顺序读取数字字符并转换为对应的整数值，创建根节点对象。
• 之后通过遍历字符串来确定左子树对应的括号表示部分：使用一个计数器 count 来跟踪括号的匹配情况（遇到 ( 就加 1，遇到 ) 就减 1），当 count 再次变为 0 时，表示找到了左子树对应的完整括号表示，然后递归调用 buildTree 函数来构建左子树，并将其赋值给根节点的左子节点指针。
• 最后，类似地提取右子树对应的括号表示部分，并递归构建右子树，将其赋值给根节点的右子节点指针，最终返回构建好的二叉树的根节点。

   3. 使用示例

以下是一个简单的使用示例，展示如何调用 buildTree 函数来构建二叉树并进行简单验证

int main() {
    Solution solution;
    string s = "(1(2)(3))";
    TreeNode* root = solution.buildTree(s);
    // 可以在这里添加代码进一步验证构建好的二叉树，比如简单打印节点值等
    cout << "根节点的值为: " << root->val << endl;
    return 0;
}

在实际应用中，你可以根据具体需求进一步扩展功能，比如添加更多的错误处理逻辑，在构建过程中如果输入字符串不符合二叉树括号表示规范（如括号不匹配、节点值格式错误等）进行相应的报错提示；或者实现二叉树的遍历函数（如前序遍历、中序遍历、后序遍历等）来更全面地查看构建好的二叉树的结构情况等。

计算二叉树的结点个数、叶子结点个数、某结点的层次和二叉树的宽度  

以下是使用 C++ 语言实现计算二叉树的节点个数、叶子节点个数、某节点的层次以及二叉

树的宽度的代码示例及详细解释。这里假设已经定义好了二叉树的节点结构体，如下所示：

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

   1. 计算二叉树节点个数

可以通过递归的方式来计算二叉树的节点个数，思路是节点个数等于 1（根节点）加上左子树节点个数加上右子树节点个数。

// 计算二叉树节点个数的函数
int countNodes(TreeNode* root) {
    if (root == NULL) return 0;
    return 1 + countNodes(root->left) + countNodes(root->right);
}

在上述函数中：

• 首先判断根节点是否为空，如果为空，说明二叉树为空树，节点个数为 0，直接返回 0。
• 否则，递归地计算左子树和右子树的节点个数，并加上 1（代表根节点）后返回，以此来得到整棵二叉树的节点个数。

   2. 计算二叉树叶子节点个数

叶子节点是指没有子节点（左子节点和右子节点都为 NULL）的节点，同样可以使用递归方式来统计。

// 计算二叉树叶子节点个数的函数
int countLeafNodes(TreeNode* root) {
    if (root == NULL) return 0;
    if (root->left == NULL && root->right == NULL) return 1;
    return countLeafNodes(root->left) + countLeafNodes(root->right);
}

在这个函数里：

• 先判断根节点是否为空，为空则返回 0，因为空树没有叶子节点。
• 接着判断根节点是否为叶子节点（即左、右子节点都为空），若是则返回 1。
• 如果根节点不是叶子节点，就递归地分别统计左子树和右子树中的叶子节点个数，然后相加返回，得到整棵树的叶子节点个数。

   3. 计算某节点的层次

可以通过从根节点开始进行层次遍历（例如使用队列来辅助实现广度优先搜索）来确定某节点所在的层次，根节点层次为 1，每向下一层层次数加 1。

#include <queue>

// 计算某节点在二叉树中的层次的函数
int getLevel(TreeNode* root, TreeNode* target) {
    if (root == NULL) return 0;
    std::queue<TreeNode*> q;
    q.push(root);
    int level = 1;
    while (!q.empty()) {
        int size = q.size();
        for (int i = 0; i < size; i++) {
            TreeNode* node = q.front();
            q.pop();
            if (node == target) return level;
            if (node->left!= NULL) q.push(node->left);
            if (node->right!= NULL) q.push(node->right);
        }
        level++;
    }
    return 0;  // 没找到目标节点则返回0
}

在上述函数中：

• 首先判断根节点是否为空，如果为空则直接返回 0，因为不存在层次一说。
• 然后创建一个队列用于层次遍历，将根节点入队，并初始化层次数为 1。
• 在循环中，每次取出队列中当前层的所有节点（通过 size 控制循环次数），检查是否为目标节点，如果是则返回当前层次数。对于当前层的每个节点，将其左、右子节点（如果存在）入队，以便后续遍历下一层，每处理完一层层次数加 1。
• 如果遍历完整个树都没找到目标节点，则返回 0。

   4. 计算二叉树的宽度

二叉树的宽度可以理解为各层节点数最多的那一层的节点个数，通过层次遍历并记录每层的节点个数来找到最大宽度。

// 计算二叉树宽度的函数
int getWidth(TreeNode* root) {
    if (root == NULL) return 0;
    std::queue<TreeNode*> q;
    q.push(root);
    int maxWidth = 0;
    while (!q.empty()) {
        int size = q.size();
        maxWidth = std::max(maxWidth, size);
        for (int i = 0; i < size; i++) {
            TreeNode* node = q.front();
            q.pop();
            if (node->left!= NULL) q.push(node->left);
            if (node->right!= NULL) q.push(node->right);
        }
    }
    return maxWidth;
}

在这个函数中：

• 同样先判断根节点是否为空，为空则返回 0，因为空树宽度为 0。
• 接着使用队列进行层次遍历，每次循环开始时记录当前层的节点个数 size，并更新最大宽度 maxWidth（取当前最大宽度和当前层节点个数中的较大值）。
• 然后将当前层的每个节点的左、右子节点（如果存在）入队，以便遍历下一层。
• 遍历完整个二叉树后，返回最大宽度值，即二叉树各层中节点数最多的那一层的节点个数。

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

int main() {
    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);

    std::cout << "节点个数: " << countNodes(root) << std::endl;
    std::cout << "叶子节点个数: " << countLeafNodes(root) << std::endl;
    TreeNode* target = root->left->right;  // 以节点值为5的节点为例
    std::cout << "节点5所在层次: " << getLevel(root, target) << std::endl;
    std::cout << "二叉树宽度: " << getWidth(root) << std::endl;

    return 0;
}

测试说明

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

测试输入：
A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))
K

预期输出：
输出二叉树b:A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))
二叉树b的结点个数:14
二叉树b的叶子结点个数:6
二叉树b中值为K结点的层次:5
二叉树b的宽度:4

开始你的任务吧，祝你成功！

通关代码

#include <iostream>
#include <queue>
#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, 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 = new 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);
    delete 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 ? p->lchild : NULL; }

BTNode *RchildNode(BTNode *p) { return p ? p->rchild : NULL; }

int BTHeight(BTNode *b) {
  if (b == NULL)
    return 0;
  int lchildh = BTHeight(b->lchild);
  int rchildh = BTHeight(b->rchild);
  return (lchildh > rchildh) ? (lchildh + 1) : (rchildh + 1);
}

int CountNodes(BTNode *b) {
  if (b == NULL)
    return 0;
  return 1 + CountNodes(b->lchild) + CountNodes(b->rchild);
}

int CountLeafNodes(BTNode *b) {
  if (b == NULL)
    return 0;
  if (b->lchild == NULL && b->rchild == NULL)
    return 1;
  return CountLeafNodes(b->lchild) + CountLeafNodes(b->rchild);
}

int FindLevel(BTNode *b, ElemType x, int level) {
  if (b == NULL)
    return 0;
  if (b->data == x)
    return level;
  int leftLevel = FindLevel(b->lchild, x, level + 1);
  if (leftLevel)
    return leftLevel;
  return FindLevel(b->rchild, x, level + 1);
}

int TreeWidth(BTNode *root) {
  if (!root)
    return 0;

  int maxWidth = 0;
  queue<BTNode *> q;
  q.push(root);

  while (!q.empty()) {
    int count = q.size();
    maxWidth = max(maxWidth, count);

    for (int i = 0; i < count; i++) {
      BTNode *node = q.front();
      q.pop();
      if (node->lchild)
        q.push(node->lchild);
      if (node->rchild)
        q.push(node->rchild);
    }
  }
  return maxWidth;
}

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;
  char str[Maxsize];
  char c;

  cin.getline(str, Maxsize);
  cin >> c;

  CreateBTree(b, str);

测试结果

​编辑

​