21xrx.com
2025-03-28 05:27:04 Friday
文章检索 我的文章 写文章
C++二叉树建立与遍历代码实现
2023-07-11 13:11:00 深夜i     15     0
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<<" ";
}

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

  
  

评论区