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

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

2023-07-11 13:11:00 深夜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* BuildBinaryTree() { 
  TreeNode *root = NULL; 
  int value; 
  cin >> value; 
  if(value!=-1) { 
    root = new TreeNode(value); 
    root->left = BuildBinaryTree(); 
    root->right = BuildBinaryTree(); 
  } 
  return root; 
}

在上面的代码中，我们定义了一个结构体TreeNode，表示二叉树的节点。我们使用BuildBinaryTree函数来递归建立二叉树，如果读入的值为-1，则表示该节点为空。而如果读入的值不是-1，则需要建立该节点，并递归建立左子树和右子树。

接下来，我们将介绍二叉树的遍历方法，遍历二叉树可以分为前序遍历、中序遍历和后序遍历三种方式。下面分别介绍这三种遍历方式的C++代码实现。

前序遍历：

前序遍历先访问根节点，然后再访问左子树和右子树。


void PreOrderTraversal(TreeNode* root) {
  if(root == NULL)
    return ;
  
  cout<<root->val<<" ";
  PreOrderTraversal(root->left);
  PreOrderTraversal(root->right);
}

中序遍历：

中序遍历先访问左子树，然后再访问根节点和右子树。


void InOrderTraversal(TreeNode* root) {
  if(root == NULL)
    return ;
  
  InOrderTraversal(root->left);
  cout<<root->val<<" ";
  InOrderTraversal(root->right);
}

后序遍历：

后序遍历先访问左子树，然后再访问右子树和根节点。


void PostOrderTraversal(TreeNode* root) {
  if(root == NULL)
    return ;
  
  PostOrderTraversal(root->left);
  PostOrderTraversal(root->right);
  cout<<root->val<<" ";
}

通过以上的代码实现，我们可以方便地建立和遍历二叉树。在实际使用中，我们可以通过修改代码来实现其他的操作，例如查找特定节点、删除节点等，从而满足不同的需求。

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

下一篇: 如何在C++中使用指针作为参数传递

评论区

()

相似文章