C++实现二叉树的代码 |21xrx.com

C++实现二叉树的代码

2023-06-27 02:01:16 深夜i -- --

C++ 二叉树实现代码

C++ 是一种快速和高效的编程语言，广泛用于各种应用程序的开发。二叉树是一种非常重要的数据结构，非常适合用于快速搜索和排序数据。在 C++ 中实现二叉树的代码非常简单，下文将介绍实现二叉树的代码。

在 C++ 中实现二叉树，需要定义一个节点类，该类包含一个数据成员和两个指向左右子节点的指针。定义好节点类之后，再定义一个二叉树类，该类包含一个指向根节点的指针和各种方法用于操作树。

下面是一个示例代码，其中定义了节点类和二叉树类，其中包括插入、搜索、删除等方法。


#include<iostream>
using namespace std;
class Node {
 public:
  int data;
  Node* left_child;
  Node* right_child;
  Node(int data)
    this->data = data;
    left_child = nullptr;
    right_child = nullptr;
  
};
Node* insert(Node* root, int data) {
  if(root == nullptr) {
    return new Node(data);
  }
  if(data < root->data) {
    root->left_child = insert(root->left_child, data);
  }
  else {
    root->right_child = insert(root->right_child, data);
  }
  return root;
}
bool search(Node* root, int data) {
  if(root == nullptr)
    return false;
  
  if(data == root->data)
    return true;
  
  if(data < root->data) {
    return search(root->left_child, data);
  }
  return search(root->right_child, data);
}
Node* remove(Node* root, int data) {
  if(root == nullptr)
    return nullptr;
  
  if(data < root->data) {
    root->left_child = remove(root->left_child, data);
    return root;
  }
  if(data > root->data) {
    root->right_child = remove(root->right_child, data);
    return root;
  }
  if(root->left_child == nullptr && root->right_child == nullptr)
    delete root;
    return nullptr;
  
  if(root->left_child == nullptr) {
    Node* temp = root->right_child;
    delete root;
    return temp;
  }
  if(root->right_child == nullptr) {
    Node* temp = root->left_child;
    delete root;
    return temp;
  }
  Node* successor = root->right_child;
  while(successor->left_child != nullptr)
    successor = successor->left_child;
  
  root->data = successor->data;
  root->right_child = remove(root->right_child, successor->data);
  return root;
}
class BinaryTree {
 public:
  Node* root;
  BinaryTree()
    root = nullptr;
  
  void insert(int data) {
    root = ::insert(root, data);
  }
  bool search(int data) {
    return ::search(root, data);
  }
  void remove(int data) {
    root = ::remove(root, data);
  }
};
int main() {
  BinaryTree tree;
  tree.insert(10);
  tree.insert(8);
  tree.insert(12);
  tree.insert(9);
  tree.insert(7);
  cout << "9 in tree: " << tree.search(9) << endl;
  cout << "11 in tree: " << tree.search(11) << endl;
  tree.remove(8);
  cout << "8 removed from tree" << endl;
  cout << "9 in tree: " << tree.search(9) << endl;
  cout << "8 in tree: " << tree.search(8) << endl;
  return 0;
}

通过这个例子可以看到，实现一个二叉树非常简单，只需要定义一个节点类和一个二叉树类，为它们分别编写操作方法即可。当然，在实现二叉树的时候也需要注意一些细节问题，例如插入重复值时需要进行处理，删除节点时需要考虑多种情况等。

如果你对实现二叉树的代码还不是很熟悉，可以多尝试一些例子，不断深入学习和理解操作二叉树的算法和思想，相信你一定能够在 C++ 中实现出自己的完美二叉树。

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

下一篇: VC++6.0无法运行的解决方法

评论区

()

相似文章