「教程」C++实现二叉树的基本操作 |21xrx.com

「教程」C++实现二叉树的基本操作

2023-06-29 04:35:48 深夜i -- --

C++ 二叉树基本操作实现教程

二叉树是一种常见的数据结构，它由一个根节点和若干个子节点组成，每个节点最多有两个子节点，左子节点比右子节点小或等于它。在程序设计中，二叉树可以用来实现排序、搜索、编码等功能。本篇文章将介绍在C++中如何实现二叉树的常见操作。

1. 创建二叉树

在C++中，可以定义一个结构体来表示树的节点，它包含一个数据域和两个指针域，分别指向左子节点和右子节点。创建二叉树的基本思路是从根节点开始，每次按照大小关系插入一个新的节点，递归执行，直到所有节点插入完毕。

以下是一个简单的示例代码：


struct TreeNode {
  int val;
  TreeNode* left;
  TreeNode* right;
  TreeNode(int x):val(x),left(NULL),right(NULL){}
};
void insert(TreeNode*& root, int val) {
  if (root == NULL) {
    root = new TreeNode(val);
    return;
  }
  if (val <= root->val) insert(root->left, val);
  else insert(root->right, val);
}
int main() {
  TreeNode* root = NULL;
  int n, val;
  cin >> n;
  for (int i = 0; i < n; i++) {
    cin >> val;
    insert(root, val);
  }
  return 0;
}

2. 遍历二叉树

遍历二叉树就是把树中的所有节点按照一定的顺序访问一遍。常用的遍历方式有三种：前序遍历、中序遍历和后序遍历。

前序遍历：先访问根节点，然后依次访问左子树和右子树。


void preorder(TreeNode* root) {
  if (root) {
    cout << root->val << " ";
    preorder(root->left);
    preorder(root->right);
  }
}

中序遍历：先访问左子树，然后访问根节点，最后访问右子树。


void inorder(TreeNode* root) {
  if (root) {
    inorder(root->left);
    cout << root->val << " ";
    inorder(root->right);
  }
}

后序遍历：先访问左子树，然后访问右子树，最后访问根节点。


void postorder(TreeNode* root) {
  if (root) {
    postorder(root->left);
    postorder(root->right);
    cout << root->val << " ";
  }
}

3. 查找节点

查找二叉树中的某个节点可以采用递归的方法，从根节点开始依次比较待查找节点的大小关系，最终找到目标节点或者发现目标节点不存在。


TreeNode* find(TreeNode* root, int val) {
  if (root == NULL) return NULL;
  if (val == root->val) return root;
  if (val < root->val) return find(root->left, val);
  else return find(root->right, val);
}

4. 删除节点

删除二叉树中的节点分为三种情况：

1）叶子节点：直接删除。

2）仅有一个子节点：把子节点提上来代替要删除的节点。

3）有两个子节点：找到它右子树中最小的节点，用这个节点代替要删除的节点。


void remove(TreeNode* root, int val){
  if(!root)return;
  if(root->val == val){
    if(root->left == NULL)root = root->right;
    else if(root->right == NULL)root = root->left;
    else {
      TreeNode* tmp = root->right;
      while(tmp->left)tmp = tmp->left;
      root->val = tmp->val;
      remove(root->right,tmp->val);
    }
    return;
  }
  if(root->val > val)remove(root->left,val);
  else remove(root->right,val);
}

在实现二叉树的基本操作时，需要注意保证树的平衡性，尽量避免出现树的高度过高的情况。另外，可以采用迭代的方式来实现遍历和查找操作，这样可以节省内存空间和栈空间。当然，在实际项目中，也可以采用STL中提供的二叉树容器来实现一些常见的功能。

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

下一篇: C++桌面应用开发教程：快速上手Windows应用开发

评论区

()

相似文章