C++实现二叉树的建立和遍历代码 |21xrx.com

C++实现二叉树的建立和遍历代码

2023-06-28 21:51:20 深夜i 20 0

C++ 二叉树建立遍历代码

在数据结构中，二叉树是一种常见的数据结构，它由节点和边组成，其中每个节点最多只有两个子节点。二叉树的遍历方式有三种，分别是前序遍历、中序遍历和后序遍历。本文将介绍如何使用C++语言实现二叉树的建立和遍历。

1. 二叉树的建立

首先，我们需要定义二叉树的结构体：

struct BinaryTreeNode
{
  int data; //节点数据
  BinaryTreeNode* left; //左子节点指针
  BinaryTreeNode* right; //右子节点指针
};

接下来，我们可以通过递归方式来建立二叉树。下面是一个示例代码：

BinaryTreeNode* createBinaryTree()
{
  int val;
  cin >> val; //输入节点的值
  if (val == -1) //如果输入值为-1，则表示该节点为空
  
    return NULL;
  
  BinaryTreeNode* newNode = new BinaryTreeNode();
  newNode->data = val;
  newNode->left = createBinaryTree(); //递归建立左子树
  newNode->right = createBinaryTree(); //递归建立右子树
  return newNode;
}

该函数会从输入流中读取节点的值，如果值为-1，则返回NULL表示该节点为空；否则，使用new关键字创建一个新节点，并递归地建立其左右子树。最终，该函数返回根节点的指针。

2. 二叉树的遍历

接下来，我们将介绍三种遍历方式：前序遍历、中序遍历和后序遍历。这三种遍历方式的差别在于遍历顺序不同。

- 前序遍历

前序遍历的遍历顺序是：根节点 -> 左子树 -> 右子树。下面是一个示例代码：

void preOrderTraversal(BinaryTreeNode* root)
{
  if (root == NULL)
  
    return;
  
  cout << root->data << " "; //先访问根节点
  preOrderTraversal(root->left); //递归遍历左子树
  preOrderTraversal(root->right); //递归遍历右子树
}

首先，访问根节点，并递归遍历左右子树。

- 中序遍历

中序遍历的遍历顺序是：左子树 -> 根节点 -> 右子树。下面是一个示例代码：

void inOrderTraversal(BinaryTreeNode* root)
{
  if (root == NULL)
  
    return;
  
  inOrderTraversal(root->left); //递归遍历左子树
  cout << root->data << " "; //访问根节点
  inOrderTraversal(root->right); //递归遍历右子树
}

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

- 后序遍历

后序遍历的遍历顺序是：左子树 -> 右子树 -> 根节点。下面是一个示例代码：

void postOrderTraversal(BinaryTreeNode* root)
{
  if (root == NULL)
  
    return;
  
  postOrderTraversal(root->left); //递归遍历左子树
  postOrderTraversal(root->right); //递归遍历右子树
  cout << root->data << " "; //访问根节点
}

先递归遍历左右子树，最后访问根节点。

3. 总结

本文介绍了如何使用C++语言实现二叉树的建立和遍历。建立二叉树需要使用递归，遍历二叉树则需要根据遍历顺序递归调用函数。二叉树是常用的数据结构之一，它可以应用于很多领域，例如图形、数据库和计算机科学等。

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

下一篇: C++中的for循环语法及用法详解

评论区

相似文章