C++二叉树：头文件编写 |21xrx.com

C++二叉树：头文件编写

2023-07-13 12:31:19 深夜i -- --

C++ 二叉树头文件编写

在C++中，二叉树是一种常用的数据结构。它通过节点和指针进行定义，每个节点最多有两个子节点，并且每个节点都可以有一些关联的数据。在本文中，我们将介绍如何编写一个二叉树的头文件，方便我们在程序中使用二叉树。

首先，我们需要定义一个节点类。该类应该包含一个左子节点和一个右子节点，并且应该包含存储节点关联数据的属性。以下是一个示例：


class BinaryTreeNode {
public:
  int data;
  BinaryTreeNode* left;
  BinaryTreeNode* right;
};

接下来，我们需要定义一个二叉树类。该类应该包含一个指向根节点的指针，并且应该具有插入、删除和查找节点的方法。以下是一个示例：


class BinaryTree {
public:
  BinaryTreeNode* root;
  // 插入节点
  void insert(int data);
  // 删除节点
  void remove(int data);
  // 查找节点
  bool find(int data);
};

最后，我们需要定义插入、删除和查找方法的实现。以下是一个示例：


void BinaryTree::insert(int data) {
  BinaryTreeNode* newNode = new BinaryTreeNode();
  newNode->data = data;
  newNode->left = NULL;
  newNode->right = NULL;
  if (root == NULL)
    root = newNode;
    return;
  
  BinaryTreeNode* current = root;
  while (true) {
    if (data < current->data) {
      if (current->left == NULL)
        current->left = newNode;
        return;
      
      current = current->left;
    }
    else {
      if (current->right == NULL)
        current->right = newNode;
        return;
      
      current = current->right;
    }
  }
}
void BinaryTree::remove(int data) {
  BinaryTreeNode* parent = NULL;
  BinaryTreeNode* current = root;
  bool isLeftChild = false;
  if (current == NULL)
    return;
  
  while (current->data != data) {
    parent = current;
    if (data < current->data)
      isLeftChild = true;
      current = current->left;
    
    else
      isLeftChild = false;
      current = current->right;
    
    if (current == NULL)
      return;
    
  }
  if (current->left == NULL && current->right == NULL) {
    if (current == root)
      root = NULL;
    
    else if (isLeftChild)
      parent->left = NULL;
    
    else
      parent->right = NULL;
    
    delete current;
  }
  else if (current->right == NULL) {
    if (current == root)
      root = current->left;
    
    else if (isLeftChild)
      parent->left = current->left;
    
    else
      parent->right = current->left;
    
    delete current;
  }
  else if (current->left == NULL) {
    if (current == root)
      root = current->right;
    
    else if (isLeftChild)
      parent->left = current->right;
    
    else
      parent->right = current->right;
    
    delete current;
  }
  else {
    BinaryTreeNode* successor = getSuccessor(current);
    if (current == root)
      root = successor;
    
    else if (isLeftChild)
      parent->left = successor;
    
    else
      parent->right = successor;
    
    successor->left = current->left;
    delete current;
  }
}
BinaryTreeNode* BinaryTree::getSuccessor(BinaryTreeNode* deleleNode) {
  BinaryTreeNode* successsor = NULL;
  BinaryTreeNode* successsorParent = NULL;
  BinaryTreeNode* current = deleleNode->right;
  while (current != NULL)
    successsorParent = successsor;
    successsor = current;
    current = current->left;
  
  if (successsor != deleleNode->right)
    successsorParent->left = successsor->right;
    successsor->right = deleleNode->right;
  
  return successsor;
}
bool BinaryTree::find(int data) {
  BinaryTreeNode* current = root;
  while (current != NULL) {
    if (current->data == data)
      return true;
    
    else if (data < current->data)
      current = current->left;
    
    else
      current = current->right;
    
  }
  return false;
}

在本文中，我们了解了如何编写一个C++二叉树的头文件，包括节点和二叉树类的定义以及插入、删除和查找方法的实现。通过使用这个头文件，我们可以轻松地在程序中使用二叉树来管理数据。

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

下一篇: 为何C++中字符串常量能够赋值给string类型变量？

评论区

()

相似文章