使用C++建立一棵二叉树 |21xrx.com

使用C++建立一棵二叉树

2023-07-05 03:39:28 深夜i -- --

C++ 二叉树建立

二叉树是一种常见的数据结构，在计算机科学中有广泛的应用。使用C++编程语言，可以非常方便地建立一棵二叉树。

在C++中，可以使用结构体定义二叉树的基本数据结构。结构体包含一个整数值和两个指针，分别指向左子树和右子树。可以使用递归的方式，通过不断地建立左子树和右子树，逐步构建整棵二叉树。

下面是一个例子，其中我们定义了一个BinaryTreeNode结构体，以及一个BinaryTree类，用于创建和操作二叉树。


#include <iostream>
using namespace std;
struct BinaryTreeNode {
  int data;
  BinaryTreeNode* left;
  BinaryTreeNode* right;
};
class BinaryTree {
private:
  BinaryTreeNode* root; // 根节点
public:
  BinaryTree() root = NULL;
  // 插入节点
  void Insert(int value) {
    BinaryTreeNode* newNode = new BinaryTreeNode;
    newNode->data = value;
    newNode->left = NULL;
    newNode->right = NULL;
    if (root == NULL)
      root = newNode;
      return;
    
    BinaryTreeNode* temp = root;
    while (true) {
      if (value < temp->data) {
        if (temp->left == NULL)
          temp->left = newNode;
          break;
        
        else
          temp = temp->left;
      }
      else {
        if (temp->right == NULL)
          temp->right = newNode;
          break;
        
        else
          temp = temp->right;
      }
    }
  }
  // 前序遍历
  void PreOrder(BinaryTreeNode* node) {
    if (node == NULL)
      return;
    cout << node->data << " ";
    PreOrder(node->left);
    PreOrder(node->right);
  }
  // 中序遍历
  void InOrder(BinaryTreeNode* node) {
    if (node == NULL)
      return;
    InOrder(node->left);
    cout << node->data << " ";
    InOrder(node->right);
  }
  // 后序遍历
  void PostOrder(BinaryTreeNode* node) {
    if (node == NULL)
      return;
    PostOrder(node->left);
    PostOrder(node->right);
    cout << node->data << " ";
  }
};
int main() {
  BinaryTree tree;
  tree.Insert(10);
  tree.Insert(5);
  tree.Insert(20);
  tree.Insert(13);
  tree.Insert(7);
  cout << "PreOrder traversal: ";
  tree.PreOrder(tree.root);
  cout << endl;
  cout << "InOrder traversal: ";
  tree.InOrder(tree.root);
  cout << endl;
  cout << "PostOrder traversal: ";
  tree.PostOrder(tree.root);
  cout << endl;
  return 0;
}

在上面的代码中，我们定义了一个BinaryTree类和一个BinaryTreeNode结构体。BinaryTree类包含了插入节点和遍历二叉树的方法。BinaryTreeNode结构体则包含了每个节点的数据和指向左右子树的指针。

在程序中，我们创建了一棵二叉树，并插入了一些节点。然后进行了前序、中序和后序遍历，以展示不同遍历方式的输出结果。

使用C++建立一棵二叉树非常简单，只需要定义一个结构体来存储每个节点的数据，并通过递归的方式建立左右子树即可。二叉树作为一种常见的数据结构，可以用于解决许多计算机科学问题。

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

下一篇: C++中是否支持多重继承？

评论区

()

相似文章