C++实现二叉树的构建 |21xrx.com

C++实现二叉树的构建

2023-07-05 06:55:28 深夜i -- --

C++ 二叉树构建

在计算机科学中，二叉树是最常用的数据结构之一。它可以很好地用来存储和操作集合、映射和分类等相关数据。在C++中，可以使用类来实现二叉树的构建。

首先，定义一个二叉树节点的结构体，该结构体包含左子树指针、右子树指针以及数据成员：


struct Node {
  int data;
  Node* left;
  Node* right;
};

然后，定义一个二叉树类，该类包含二叉树的根节点以及各种二叉树操作：


class BinaryTree {
  private:
    Node* root;
  public:
    BinaryTree() : root(nullptr) {}
    Node* getRoot() const return root;
    void insert(int data);
    bool search(int data) const;
    void inOrderTraversal(Node* node) const;
};

在上面的定义中，insert()函数用于将数据插入到二叉树中，search()函数用于查找给定数据是否在二叉树中存在，inOrderTraversal()函数用于按中序遍历顺序访问节点。

下面是实现二叉树操作的方法：

1. 插入元素


void BinaryTree::insert(int data) {
  Node* newNode = new Node nullptr;
  if (root == nullptr)
    root = newNode;
    return;
  
  Node* current = root;
  while (true) {
    if (data < current->data) {
      if (current->left == nullptr)
        current->left = newNode;
        break;
      
      current = current->left;
    } else {
      if (current->right == nullptr)
        current->right = newNode;
        break;
      
      current = current->right;
    }
  }
}

该函数首先创建一个新节点，然后使用while循环找到该节点应该插入的位置。如果该节点小于当前节点的数据，则查找其左子树，否则查找其右子树。如果找到了一个空闲位置，就将新节点插入其中。

2. 查找元素


bool BinaryTree::search(int data) const {
  Node* current = root;
  while (current != nullptr) {
    if (current->data == data)
      return true;
     else if (data < current->data)
      current = current->left;
     else
      current = current->right;
    
  }
  return false;
}

该函数使用while循环来遍历二叉树。如果当前节点的数据与给定数据相等，则返回true。如果给定数据小于当前节点的数据，则查找其左子树，否则查找其右子树。如果遍历整个二叉树没有找到节点，则返回false。

3. 按中序遍历顺序访问元素


void BinaryTree::inOrderTraversal(Node* node) const {
  if (node == nullptr) return;
  inOrderTraversal(node->left);
  std::cout << node->data << " ";
  inOrderTraversal(node->right);
}

该函数使用递归调用来遍历左子树、访问当前节点和遍历右子树。一旦到达叶子节点，递归调用结束。

最后，使用以上定义可以实现二叉树的构建，例如：


BinaryTree bt;
bt.insert(5);
bt.insert(3);
bt.insert(7);
bt.insert(1);
bt.insert(4);
bt.insert(6);
bt.inOrderTraversal(bt.getRoot());

以上代码将会输出：1 3 4 5 6 7，表明中序遍历访问元素的顺序为从小到大的排序。在这个例子中，使用类和指针构建二叉树，实现了动态内存分配和针对数据的查找和插入。

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

下一篇: C++自动化部署k8s：让部署更简单高效

评论区

()

相似文章