如何在C++中建立二叉树 |21xrx.com

如何在C++中建立二叉树

2023-07-04 20:32:30 深夜i -- --

C++ 二叉树建立

二叉树是一种常见的数据结构，可以在计算机科学中广泛应用。在C++中，建立二叉树有多种方法，本文将介绍其中一种基本的方法。

首先，我们需要定义二叉树的节点。一个二叉树节点包含左右两个子节点指针和节点值。代码如下：

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

在定义好二叉树节点之后，我们可以使用递归的方式来建立二叉树。具体而言，我们可以通过一个构造函数，不断地向二叉树中插入新节点。构造函数代码如下：

class BST{
public:
  BST()
    root = nullptr;
  
  void insert(int val){
    insertHelper(root, val);
  }
  TreeNode* getRoot()
    return root;
  
private:
  TreeNode *root;
  void insertHelper(TreeNode *&current, int val){
    if(current == nullptr){
      current = new TreeNode(val);
    }else if(val < current->val){
      insertHelper(current->left, val);
    }else{
      insertHelper(current->right, val);
    }
  }
};

该构造函数定义了一个名为BST的类，其中包含三个成员函数：BST，insert和getRoot。构造函数中，我们首先将根节点设置为nullptr。insert函数用于向二叉树中插入新节点，它调用了insertHelper函数。insertHelper函数通过递归的方式找到节点应该插入的位置，并创建一个新的节点。getRoot函数用于获取根节点，方便我们进行后续操作。

通过上述代码，我们就可以成功地建立一个二叉树。我们可以使用如下代码来创建一个包含5个节点的二叉树，并输出每个节点的值：

int main(){
  BST tree;
  tree.insert(5);
  tree.insert(3);
  tree.insert(7);
  tree.insert(2);
  tree.insert(4);
  TreeNode *root = tree.getRoot();
  cout<<"Binary Tree:"<<endl;
  printAllTree(root);
  return 0;
}

在这段代码中，我们首先创建一个名为tree的BST对象，然后通过insert函数插入5个节点。接着，我们使用getRoot函数获取根节点，并输出整棵树。

完整代码如下：

#include <iostream>
using namespace std;
struct TreeNode{
  int val;
  TreeNode *left;
  TreeNode *right;
  TreeNode(int x) : val(x), left(nullptr), right(nullptr){}
};
class BST{
public:
  BST()
    root = nullptr;
  
  void insert(int val){
    insertHelper(root, val);
  }
  TreeNode* getRoot()
    return root;
  
private:
  TreeNode *root;
  void insertHelper(TreeNode *&current, int val){
    if(current == nullptr){
      current = new TreeNode(val);
    }else if(val < current->val){
      insertHelper(current->left, val);
    }else{
      insertHelper(current->right, val);
    }
  }
};
void printAllTree(TreeNode *root){
  if(root!=nullptr){
    printAllTree(root->left);
    cout<<root->val<<' ';
    printAllTree(root->right);
  }
}
int main(){
  BST tree;
  tree.insert(5);
  tree.insert(3);
  tree.insert(7);
  tree.insert(2);
  tree.insert(4);
  TreeNode *root = tree.getRoot();
  cout<<"Binary Tree:"<<endl;
  printAllTree(root);
  return 0;
}

通过上述代码，我们就成功地在C++中建立了一个简单的二叉树。当然，该方法不一定适用于所有的二叉树建立场景，但在绝大多数情况下都能满足需求。

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

下一篇: C++ New操作符简单使用：菜鸟教程

评论区

相似文章