21xrx.com
2025-07-07 11:18:02 Monday
文章检索 我的文章 写文章
C++实现二叉树的构建
2023-07-05 06:55:28 深夜i     15     0
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,表明中序遍历访问元素的顺序为从小到大的排序。在这个例子中,使用类和指针构建二叉树,实现了动态内存分配和针对数据的查找和插入。

  
  

评论区