C++ 教程：如何建立二叉树 |21xrx.com

C++ 教程：如何建立二叉树

2023-07-05 12:53:33 深夜i -- --

C++ 二叉树建立教程数据结构

在计算机科学中，二叉树是一种重要的数据结构，它常常用于搜索和排序等算法中。学习如何建立二叉树是作为一名程序员必须掌握的技能之一。本篇文章旨在介绍如何用C++语言建立二叉树。

1.理解二叉树的概念

二叉树可视为一个有根节点的树形结构，其中每个节点有两个子节点，分别称为左子节点和右子节点。如果它没有子节点，那么该节点就是叶子节点。二叉树的根节点没有父节点。

2.定义二叉树的结构

在C++中定义二叉树的结构应该包括两个主要元素：树节点和根节点。树节点应该包含左右子节点的指针和数据成员。根节点指向该树节点的根节点。


struct TreeNode {
  int data;
  TreeNode * left;
  TreeNode * right;
  TreeNode(int x) : data(x), left(NULL), right(NULL) {}
};
class BinaryTree {
private:
  TreeNode * root;
public:
  /* constructors and methods */
};

3.建立二叉树

在C++中，可以用递归方法来建立二叉树。具体实现过程如下：


void BinaryTree::insert(int x, TreeNode *& node) {
  if(node == NULL) {
    node = new TreeNode(x);
  }
  else if(x < node->data) {
    insert(x, node->left);
  }
  else if(x > node->data) {
    insert(x, node->right);
  }
  else
    // data already exists
  
}
void BinaryTree::insert(int x) {
  insert(x, root);
}

以上是建立二叉树的核心函数之一。它首先检查当前的节点是否为空。如果是，则新建一个节点，否则检查输入的值是否比当前节点的值小，如果是，递归地将输入值插入到左子树中; 如果比当前节点的值大，则递归地将输入值插入到右子树中。


BinaryTree bt;
bt.insert(9);
bt.insert(5);
bt.insert(3);
bt.insert(7);
bt.insert(11);
bt.insert(15);

通过以上代码，我们可以成功地建立了一个二叉树。

4.遍历二叉树

建立二叉树之后，就需要遍历它，以便进行操作和查找。遍历操作主要有三个：前序遍历，中序遍历，后序遍历。

- 前序遍历：根节点 -> 左子树 -> 右子树

- 中序遍历：左子树 -> 根节点 -> 右子树

- 后序遍历：左子树 -> 右子树 -> 根节点

我们以中序遍历为例来遍历建立好的二叉树。


void BinaryTree::inOrderTraversal(TreeNode * node) {
  if(node == NULL)
    return;
  
  else {
    inOrderTraversal(node->left);
    cout << node->data << " ";
    inOrderTraversal(node->right);
  }
}
void BinaryTree::inOrderTraversal() {
  inOrderTraversal(root);
}

这里我们使用递归的方式来实现中序遍历。遍历过程为先遍历左子树，然后输出根节点的值，然后遍历右子树。

通过以上代码，我们已经可以成功建立二叉树和遍历它。可以结合不同的实际问题，来动态改变二叉树的结构，以满足不同的需求。

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

下一篇: C++ 转换为字符串

评论区

()

相似文章