21xrx.com
2024-11-22 13:31:52 Friday
登录
文章检索 我的文章 写文章
如何用C++输入二叉搜索树?
2023-06-23 00:41:29 深夜i     --     --
C++ 输入 二叉搜索树

C++是一种强大的编程语言,它具有不同的数据类型和功能,它可以很容易地实现各种数据结构,包括二叉搜索树。

二叉搜索树是一种常用的数据结构,它是一个二叉树,其中每个节点都包含一个值,并且左子树中的所有值都小于该节点的值,右子树中的所有值都大于该节点的值。因此,它非常适合用于搜索和排序。

要输入二叉搜索树,您可以使用递归方法,其大致流程如下:

- 如果根节点为空,将其设为新节点。

- 如果新节点的值小于根节点的值,则将其插入到左子树中。

- 如果新节点的值大于等于根节点的值,则将其插入到右子树中。

- 最后返回根节点。

让我们看一下如何使用C++编写递归函数来输入二叉搜索树:


#include <iostream>

using namespace std;

// 树结点的定义

struct TreeNode {

  int val;

  TreeNode *left;

  TreeNode *right;

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

};

// 递归函数

TreeNode* insert(TreeNode* root, int val) {

  if (root == NULL) {  // 如果根节点为空,则创建新节点

    return new TreeNode(val);

  }

  if (val < root->val) { // 如果新节点的值小于当前节点的值,则插入到左子树中

    root->left = insert(root->left, val);

  } else {  // 否则插入到右子树中

    root->right = insert(root->right, val);

  }

  return root;

}

int main() {

  TreeNode* root = NULL;

  int n;

  cin >> n;

  for (int i = 0; i < n; i++) {

    int val;

    cin >> val;

    root = insert(root, val);  // 插入新节点

  }

  return 0;

}

在这个程序中,我们先定义了一个节点结构体,然后定义了一个名为insert的递归函数。在这个函数中,我们通过比较当前节点的值和新节点的值来确定在左子树还是右子树中插入新节点。最后,我们返回根节点,这样就可以将所有新节点递归地插入到树中。

在主函数中,我们首先定义了一个空的根节点,然后读取n个值,每个值表示要插入到二叉搜索树中的节点值,并将其作为参数传递给insert函数。

通过这种方法,您可以使用C++轻松输入二叉搜索树。

  
  

评论区

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