通俗易懂讲解C语言与Java中二叉树的三种非递归遍历方式_C/C++

通俗易懂讲解C语言与Java中二叉树的三种非递归遍历方式

2022-01-06 13:48飞人01_01 C/C++

二叉树是一种非常重要的数据结构，很多的数据结构都是基于二叉树的基础演变过来的。二叉树的前，中，后3种遍历方式，因为树的定义本身就是递归定义的，所以采用递归的方法来实现是很简单的

详解二叉树的三种非递归遍历方式（附C、java源码）

前言

二叉树的递归遍历方式很简单，三种递归遍历方式的区别，只是printf放的位置不一样而已，这里就不多讲了。把前序遍历代码贴在这里：

//结点
struct Node
{
	int val;
	struct Node* left, * right;
};

//前序遍历
void pre(Node* root) 
{
  if (root == null)
      return;
  printf("%d ",root->val);
  pre(root->left);
  pre(root->right);
}

前序、中序和后序这三种非递归的遍历方式，中序是最为简单的，其次是前序，再者就是后序，只是个人感觉。可能每个人感觉都不一样吧。

一、非递归中序遍历

中序遍历顺序：左子树->头结点->右子树。

如图―出自于《大话数据结构》

通俗易懂讲解C语言与Java中二叉树的三种非递归遍历方式

所以我们首先需要考虑的是将左手边（左子树）的结点压入栈，当到达底部时（NULL），我们就输出此时栈顶的元素。

然后转而去添加当前结点的右手边（右子树）的结点到栈里。

#define MAXSIZE 20  //整棵树最大的结点数，用于开辟数组当栈使用
typedef struct Node Node;
void in(Node* root)
{
  Node* stack[MAXSIZE] = { 0 };
  int size = 0; //用于指向arr数组，也是用于表示这个数组还有几个元素
  while (size != 0 || root != NULL)
  {
      if (root != NULL)
      {
          stack[size++] = root;
          root = root->left;  //继续往左子树走
      }
      else
      {
          //此时root为NULL，说明来到了左子树的最底部，此时输出栈顶元素，root往右子树走即可
          printf("%c ", stack[--size]->val);
          root = stack[size]->right;
      }
  }
}

二、非递归前序遍历

前序遍历顺序：头结点->左子树-> 右子树

我记得我在B站学算法的时候，听左程云老师所说，一些的递归行为，都可以自己用栈来实现。

确实，三种非递归的遍历方式实则也是需要自己实现栈的功能。接下来的前序遍历方式，要用到宽度优先遍历的思想，如图：

图片出自《大话数据结构》

通俗易懂讲解C语言与Java中二叉树的三种非递归遍历方式

先加入第一层的全部数据，然后在栈中使用第一层数据的同时，判断加入第二层的全部数据，第三层的也是一样…

#define MAXSIZE 20  //整棵树最大的结点数，用于开辟数组当栈使用
typedef struct Node Node;
void pre(Node* root)
{
  if (root == NULL)
      return;

  Node* stack[MAXSIZE] = { 0 }; //模拟栈
  int size = 0; //代表此时栈有多少元素
  arr[size++] = root;
  while (size != 0)
  {
      Node* node = stack[--size];
      printf("%c ", node->val);
      //先压入右孩子，再压入左孩子。这样在弹出的时候才是  先弹出左孩子 然后才是右孩子
      //头   左   右
      if (node->right != NULL)
          stack[size++] = node->right;
      if (node->left != NULL)
          stack[size++] = node->left;
  }
}

三、非递归后序遍历

在讲解了非递归的前序遍历，其实我们在前序遍历的基础之上改一下就能完成后序遍历。我们在将前序遍历时，在while循环里，加入左右孩子结点时，先加入栈的是右孩子，然后才是左孩子，只有这样，我们弹出来的顺序才是先左后右。

现在我们只需要改一下加入左右孩子的顺序时，我们先压入栈是左孩子，然后再压入右孩子。这样弹出来就是先右再左的顺序。那此时再加上头结点，那就是头结点->右孩子->左孩子。此时我们从后面往前面读，就是左孩子 -> 右孩子 ->头结点。这样就变成了后序遍历了。。。

图片出自《大话数据结构》

通俗易懂讲解C语言与Java中二叉树的三种非递归遍历方式

#define MAXSIZE 20  //整棵树最大的结点数，用于开辟数组当栈使用
typedef struct Node Node;
void postorder(Node* root)
{
  if (root == NULL)
      return;

  Node* stack1[MAXSIZE] = { 0 }; //主要栈
  Node* stack2[MAXSIZE] = { 0 };  //辅助栈
  int size1 = 0; //主要栈：代表数组的元素个数
  int size2 = 0; //辅助栈: 代表数组的元素个数
  stack1[size1++] = root;
  while (size1 != 0)
  {
      Node* node = stack1[--size1];
      stack2[size2++] = node; //暂时存入辅助栈

      //先压入左孩子，再压入右孩子
      if (node->left != NULL)
          stack1[size1++] = node->left;
      if (node->right != NULL)
          stack1[size1++] = node->right;
  }

  //倒着输出辅助栈的数据即可
  while (size2-- != 0)
      printf("%c ", stack2[size2]->val);
}

非递归与递归方式的遍历，有些相似之处，总结两种不同的方法，就能更深刻的理解这些方法。最后，C/C++的同学，记得回收malloc开辟的空间哦！！！

C语言源码

java语言源码

下期见啦！！！

到此这篇关于通俗易懂讲解C语言中二叉树的三种非递归遍历方式的文章就介绍到这了,更多相关C 二叉树非递归遍历内容请搜索服务器之家以前的文章或继续浏览下面的相关文章希望大家以后多多支持服务器之家！

原文链接：https://blog.csdn.net/x0919/article/details/118345568