21xrx.com
2025-07-14 17:31:38 Monday
文章检索 我的文章 写文章
C++实现二叉树的代码
2023-07-08 02:50:14 深夜i     31     0
C++ 二叉树 代码实现

在计算机编程中，二叉树是一种常见的数据结构，其每个节点最多有两个子节点。在C++编程语言中，我们可以使用类的形式实现二叉树。

首先，我们需要定义一个节点类，该类包含节点的值以及指向其左子节点和右子节点的指针。

class Node{
public:
  int value;
  Node* left;
  Node* right;
  Node(int val)
    value = val;
    left = NULL;
    right = NULL;
  
};

接下来，我们需要定义一个二叉树类。该类包含一个指向树根节点的指针。

class BinaryTree{
public:
  Node* root;
  BinaryTree()
    root = NULL;
  
};

接下来，我们需要实现一些基本方法，如插入节点、删除节点、查找节点以及遍历二叉树。

### 插入节点

插入节点方法是向二叉树中添加一个新节点。我们从根节点开始，将新节点与现有节点进行比较，将其插入左子树或右子树。

void insertNode(Node **root, int value){
  if(*root == NULL)
    *root = new Node(value);
  else if(value <= (*root)->value)
    insertNode(&(*root)->left, value);
  else
    insertNode(&(*root)->right, value);
}

### 删除节点

删除节点方法将从二叉树中删除给定的节点。如果节点是叶节点，则可以直接删除。如果它具有一个子节点，则将其子节点提升为其位置。如果它具有两个子节点，则用它的右子树中的最小值替换它，并将替换节点删除。

void deleteNode(Node** root, int value){
  if(*root == NULL)
    return;
  if(value < (*root)->value)
    deleteNode(&(*root)->left, value);
  else if(value > (*root)->value)
    deleteNode(&(*root)->right, value);
  else{
    if((*root)->left == NULL || (*root)->right == NULL){
      Node* tmp = (*root)->left ? (*root)->left : (*root)->right;
      if(tmp == NULL){
        tmp = *root;
        *root = NULL;
      } else
        **root = *tmp;
      delete tmp;
    } else{
      Node* tmp = findMin((*root)->right);
      (*root)->value = tmp->value;
      deleteNode(&(*root)->right, tmp->value);
    }
  }
}

### 查找节点

查找节点方法返回具有给定值的节点的指针。我们从树根开始，将其与给定值进行比较，并根据需要遍历其左子树或右子树。

Node* findNode(Node* root, int value){
  if(root == NULL)
    return NULL;
  else if(root->value == value)
    return root;
  else if(value < root->value)
    return findNode(root->left, value);
  else
    return findNode(root->right, value);
}

### 遍历二叉树

遍历二叉树方法为我们提供了访问树节点集的方式。有三种主要遍历方式：先序遍历、中序遍历和后序遍历。先序遍历按照一个节点-左子树-右子树的顺序访问树节点。中序遍历按照左子树-一个节点-右子树的顺序访问树节点。后序遍历按照左子树-右子树-一个节点的顺序访问树节点。

//先序遍历
void preOrder(Node* root){
  if(root != NULL){
    cout<<root->value<<" ";
    preOrder(root->left);
    preOrder(root->right);
  }
}
//中序遍历
void inOrder(Node* root){
  if(root != NULL){
    inOrder(root->left);
    cout<<root->value<<" ";
    inOrder(root->right);
  }
}
// 后序遍历
void postOrder(Node* root){
  if(root != NULL){
    postOrder(root->left);
    postOrder(root->right);
    cout<<root->value<<" ";
  }
}

在C++中实现二叉树代码是一个有趣的编程挑战。通过使用类和指针，我们可以轻松地实现这种常见数据结构、实现各种插入和删除节点操作，以及遍历整个树来检索数据。

  
  

评论区