21xrx.com
2024-11-22 02:20:41 Friday
登录
文章检索 我的文章 写文章
C++二叉树代码
2023-07-07 07:44:34 深夜i     --     --
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++二叉树的实现代码。在实际开发中,我们可以根据需要对其进行改进和扩展,以满足具体业务需求。

  
  

评论区

{{item['qq_nickname']}}
()
回复
回复