C++数据结构：二叉树 |21xrx.com

C++数据结构：二叉树

2023-07-05 07:36:50 深夜i -- --

C++编程数据结构二叉树树结构遍历算法

二叉树是一种常用的数据结构，由于其具有简单易懂的特点，被很多程序员广泛使用。它的定义非常简单，每个节点都至多有两个子节点，并且一个节点可以作为另一个节点的左节点或右节点。

在C++中，我们可以使用指针来实现二叉树。每个节点都包含一个数据项和两个指针，其可以指向另外两个子节点。在编写代码时我们可以使用递归的方式来访问和遍历这个结构。以下是一个二叉树节点的示例：


struct TreeNode {
  int data;
  TreeNode* left;
  TreeNode* right;
  TreeNode(int val) : data(val), left(NULL), right(NULL) {}
};

在这个例子中，我们定义了一个名为TreeNode的结构体，其包含一个整数类型的数据项，和两个指向另一个TreeNode节点的指针：左指针和右指针。此外，我们还定义了一个构造函数，用于初始化新节点时设置数据项和两个指针的值。

接下来我们将演示如何使用二叉树来实现一个简单的命令行程序，该程序读取用户输入并构建一棵二叉树。下面是程序的主要功能：

1. 用户可以输入任意数量的整数。

2. 程序将这些整数插入二叉树中。

3. 插入完成后，程序将输出树中所有节点的值。

以下是实现这些功能的C++代码：


#include<iostream>
using namespace std;
struct TreeNode {
  int data;
  TreeNode* left;
  TreeNode* right;
  TreeNode(int val) : data(val), left(NULL), right(NULL) {}
};
void insert(TreeNode*& root, int val) {
  if(root == NULL) {
    root = new TreeNode(val);
    return;
  }
  if(val < root->data) {
    insert(root->left, val);
  } else if(val > root->data) {
    insert(root->right, val);
  }
}
void print(TreeNode* root) {
  if(root == NULL)
    return;
  
  print(root->left);
  cout << root->data << " ";
  print(root->right);
}
int main() {
  TreeNode* root = NULL;
  int input;
  cout << "请输入整数（输入'0'结束）:" << endl;
  cin >> input;
  while(input != 0) {
    insert(root, input);
    cin >> input;
  }
  cout << "二叉树中的所有节点:" << endl;
  print(root);
  cout << endl;
  return 0;
}

在这个程序中，我们首先定义了一个名为TreeNode的结构体，和一个名为root的二叉树指针。我们接下来定义了两个函数：insert和print。

函数insert用于将一个新的整数值插入到二叉树中。如果当前树为空，则分配一个新的节点节点并返回。如果该节点存在，我们比较待插入的值和节点的值，并递归向左或向右子树中插入值。每次插入操作都要更新root节点，因为在C++中我们使用了指针的引用（即使用指针的地址）。

函数print用于按中序遍历的方式遍历整个二叉树，并输出每个节点的数据。中序遍历的顺序是左节点、根节点和右节点。在完成插入操作后，我们调用print函数遍历整个树，输出所有节点的值。

在使用复杂的数据结构时，非常重要的一点是确保代码正确性，并解决任何可能出现的问题。在上面的例子中，我们没有处理错误输入，也没有检查内存分配是否成功。在实际编程中，我们需要添加更多的代码来确保程序安全、正确和健壮。

上一篇: idea打包java可执行jar包

下一篇: C++ 读取图片教程

评论区

()

相似文章