21xrx.com
2024-12-23 01:06:25 Monday
登录
文章检索 我的文章 写文章
C++实现二叉树的建立和遍历代码
2023-06-28 21:51:20 深夜i     --     --
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++语言实现二叉树的建立和遍历。建立二叉树需要使用递归,遍历二叉树则需要根据遍历顺序递归调用函数。二叉树是常用的数据结构之一,它可以应用于很多领域,例如图形、数据库和计算机科学等。

  
  

评论区

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