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

C++二叉树代码

2023-07-07 07:44:34 深夜i 179 0

C++ 二叉树代码

二叉树是一种常用的数据结构，在C++中也有相应的代码实现。下面我们来看看C++二叉树的代码实现。

C++二叉树的实现通常采用结构体来表示节点，结构体中包含当前节点的值、左右子节点的指针等信息。具体代码如下：

struct TreeNode {
  int val;
  TreeNode *left;
  TreeNode *right;
  TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

接下来，定义二叉树的主体部分，包括插入节点、删除节点、遍历等操作。具体代码如下：

class BinaryTree {
public:
  TreeNode* root;
  //插入节点
  void insert(int val) {
    TreeNode* node = new TreeNode(val);
    if (root == NULL)
      root = node;
      return;
    
    TreeNode* cur = root;
    while (cur != NULL) {
      if (val < cur->val) {
        if (cur->left == NULL)
          cur->left = node;
          break;
        
        cur = cur->left;
      } else {
        if (cur->right == NULL)
          cur->right = node;
          break;
        
        cur = cur->right;
      }
    }
  }
  //删除节点
  void deleteNode(int val) {
    root = deleteNodeUtil(root, val);
  }
  TreeNode* deleteNodeUtil(TreeNode* node, int val) {
    if (node == NULL)
      return NULL;
    
    if (val < node->val) {
      node->left = deleteNodeUtil(node->left, val);
    } else if (val > node->val) {
      node->right = deleteNodeUtil(node->right, val);
    } else {
      if (node->left == NULL) {
        TreeNode* temp = node->right;
        delete node;
        return temp;
      } else if (node->right == NULL) {
        TreeNode* temp = node->left;
        delete node;
        return temp;
      }
      TreeNode* minRight = findMinNode(node->right);
      node->val = minRight->val;
      node->right = deleteNodeUtil(node->right, minRight->val);
    }
    return node;
  }
  TreeNode* findMinNode(TreeNode* node) {
    while (node->left != NULL)
      node = node->left;
    
    return node;
  }
  //前序遍历
  void preorderTraversal(TreeNode* root) {
    if (root == NULL)
      return;
    
    cout << root->val << " ";
    preorderTraversal(root->left);
    preorderTraversal(root->right);
  }
  //中序遍历
  void inorderTraversal(TreeNode* root) {
    if (root == NULL)
      return;
    
    inorderTraversal(root->left);
    cout << root->val << " ";
    inorderTraversal(root->right);
  }
  //后序遍历
  void postorderTraversal(TreeNode* root) {
    if (root == NULL)
      return;
    
    postorderTraversal(root->left);
    postorderTraversal(root->right);
    cout << root->val << " ";
  }
};

上述代码中，insert()方法用于插入新节点，deleteNode()方法用于删除指定节点，preorderTraversal()、inorderTraversal()、postorderTraversal()方法分别实现了前序遍历、中序遍历和后序遍历操作。

使用上述代码实例化一个二叉树，并调用插入和删除等方法，可以完成对二叉树的操作。例子代码如下：


int main() {
  BinaryTree tree;
  tree.root = NULL;
  //插入数据
  tree.insert(4);
  tree.insert(2);
  tree.insert(7);
  tree.insert(6);
  tree.insert(5);
  cout << "前序遍历：";
  tree.preorderTraversal(tree.root);
  cout << endl;
  cout << "中序遍历：";
  tree.inorderTraversal(tree.root);
  cout << endl;
  cout << "后序遍历：";
  tree.postorderTraversal(tree.root);
  cout << endl;
  //删除数据
  tree.deleteNode(4);
  cout << "删除节点后中序遍历：";
  tree.inorderTraversal(tree.root);
  cout << endl;
  return 0;
}

以上就是C++二叉树的实现代码。在实际开发中，我们可以根据需要对其进行改进和扩展，以满足具体业务需求。

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

下一篇: 如何在c++中退出for循环？

评论区

相似文章