C语言二叉树的三种遍历方式的实现及原理

二叉树遍历分为三种:前序、中序、后序,其中序遍历最为重要。为啥叫这个名字?是根据根节点的顺序命名的。

比如上图正常的一个满节点,A:根节点、B:左节点、C:右节点,前序顺序是ABC(根节点排最先,然后同级先左后右);中序顺序是BAC(先左后根最后右);后序顺序是BCA(先左后右最后根)。

比如上图二叉树遍历结果

前序遍历:ABCDEFGHK

中序遍历:BDCAEHGKF

后序遍历:DCBHKGFEA

分析中序遍历如下图,中序比较重要(java很多树排序是基于中序,后面讲解分析)

下面介绍一下,二叉树的三种遍历方式,其中每一种遍历方式都有三种实现方式。

节点定义:

struct TreeNode
{
  int val;
  TreeNode *left,*right;
  TreeNode(int val){
    this->val = val;
    this ->left = this->right = NULL;
  }
};

先序遍历

以上面这张图为例:我们讲讲树的三种遍历方式:

先序遍历:先访问根节点,然后访问左孩子,最后访问右孩子。

所以,上面遍历的结果是:GEDACHS。

下面,我们来看看具体代码实现

1.递归实现

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

2.使用辅助栈  

实现思路:1.将根节点入栈
       2.每次从栈顶弹出一个节点,访问该节点
       3.把当前节点的右孩子入栈
       4.把当前节点的左孩子入栈

  具体实现:

void preOrder2(TreeNode *root){
  if (root == NULL)
    return;
  stack<TreeNode*> stk; //开辟一个栈空间
  stk.push(root);
  while(!stk.empty()){
    TreeNode* pNode = stk.pop();
    cout<<pNode->val;
    if (pNode->right!=NULL)
      stk.push(pNode->right);
    if (pNode->left!=NULL)
      stk.push(pNode->left);

  }
}

3.Morris遍历

Morris遍历,常数的空间即可在O(n)时间内完成二叉树的遍历。

O(1)空间进行遍历困难之处在于在遍历的子结点的时候如何重新返回其父节点?

在Morris遍历算法中,通过修改叶子结点的左右空指针来指向其前驱或者后继结点来实现的。

其本质:线索二叉树(Threaded Binary Tree),通过利用叶子节点空的right指针,指向中序遍历的后继节点,从而避免了对 stack 的依赖。

具体实现:

void preOrder(TreeNode* root){
  if (root == NULL)
    return;

  TreeNode* pNode = root;
  while(pNode != NULL){
    if (pNode->left == NULL)
    {
      cout<<pNode->val<<endl;
      pNode = pNode->right;
    }
    else{
      TreeNode* pPre = pNode->left;
      while(pPre->right != NULL && pPre->right != pNode){
        pPre = pPre->right;
      }

      if (pPre->right == NULL)
      {
        /* code */
        pPre->right = pNode;
        cout<<pNode->val<<endl;
        pNode = pNode->left;
      }
      else{
        pPre->right = NULL;
        pNode = pNode->right;
      }
    }
  }
}

中序遍历

中序遍历:先访问左孩点,然后访问根节点,最后访问右孩子。

所以,上面遍历的结果是:DEAGHCS。

下面,我们来看看具体代码实现

1.递归实现

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

2.使用辅助栈

实现思路:

初始化一个二叉树结点pNode指向根结点;

若pNode非空,那么就把pNode入栈,并把pNode变为其左孩子;(直到最左边的结点)

若pNode为空,弹出栈顶的结点,并访问该结点,将pNode指向其右孩子(访问最左边的结点,并遍历其右子树)

具体实现:

void InOrder(TreeNode *root){
  if (root==NULL)
  {
    return;
  }
  stack<TreeNode*> stk;
  TreeNode *pNode = root;
  while(pNode!=NULL || !stk.empty()){
    if (pNode != NULL)
    {
      stk.push(pNode);
      pNode = pNode->left;
    }
    else{
      pNode = stk.pop();
      stk.pop();
      cout<<pNode->val<<endl;
      pNode = pNode->right;
    }
  }
}

3.Morris遍历

实现思路:

1.如果当前节点pNode的左孩子为空,那么输出该节点,并把该节点的右孩子作为当前节点

2.如果当前节点pNode的左孩子非空,那么找出该节点在中序遍历的前驱结点prev

当第一次访问该前驱结点prev时,其右孩子必定为空,那么就将其右孩子设置为当前结点,以便根据这个指针返回到当前结点pNode中,并将当前结点pNode设置为其左孩子;  

当该前驱结点pPre的右孩子为当前结点,那么就输出当前结点,并把前驱结点的右孩子设置为空(恢复树的结构),将当前结点更新为当前结点的右孩子;

3.重复以上两步,直到当前结点为空。

具体实现:

void InOrder(TreeNode *root){
  if (root == NULL)
    return;

  TreeNode* pNode = root;
  while(pNode != NULL){
    if (pNode->left == NULL)
    {
      cout<<pNode->val<<endl;
      pNode = pNode->right;
    }
    else{
      TreeNode* pPre = pNode->left;
      while(pPre->right != NULL && pPre->right != pNode){
        pPre = pPre->right;
      }

      if (pPre->right == NULL)
      {
        /* code */
        pPre->right = pNode;
        pNode = pNode->left;
      }
      else{
        pPre->right = NULL;
        cout<<pNode->val<<endl;
        pNode = pNode->right;
      }
    }
  }
}

后序遍历

后序遍历:先访问左孩子,然后访问右孩子,最后访问根节点。

所以,上面遍历的结果是:DAEHSCG。

下面,我们来看看具体代码实现:

1.递归实现

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

2.使用辅助栈

void postOrder(TreeNode *root) {
  if(root == NULL)
    return;

  stack<TreeNode *> stk;
  stk.push(root);
  TreeNode *prev = NULL;
  while(!stk.empty()) {
    TreeNode *pNode = stk.top();
    if(!prev || prev->left == pNode || prev->right == pNode) { // traverse down
      if(pNode->left)
        stk.push(pNode->left);
      else if(pNode->right)
        stk.push(pNode->right);
     /* else {
        cout << pNode->val << endl;
        stk.pop();
      }
    */
    }
    else if(pNode->left == prev) { // traverse up from left
      if(pNode->right)
        stk.push(pNode->right);
    }
  /* else if(pNode->right == prev) { // traverse up from right
        cout << pNode->val << endl;
        stk.pop();
    }
  */
    else {
      cout << pNode->val << endl;
      stk.pop();
    }
    prev = pNode;
  }
}

双辅助栈实现思路:  

  • 设置两个栈stk, stk2;
  • 将根结点压入第一个栈stk;
  • 弹出stk栈顶的结点,并把该结点压入第二个栈stk2;
  • 将当前结点的左孩子和右孩子先后分别入栈stk;
  • 当所有元素都压入stk2后,依次弹出stk2的栈顶结点,并访问之。
  • 第一个栈的入栈顺序是:根结点,左孩子和右孩子;于是,压入第二个栈的顺序是:根结点,右孩子和左孩子。

因此,弹出的顺序就是:左孩子,右孩子和根结点。

void PostOrder2(TreeNode *root){ //两个栈实现
  if (root == NULL)
    return;

  stack<TreeNode*> stk,stk2;
  stk.push(root);
  while(!stk.empty()){
    TreeNode* pNode = stk.top();
    stk.pop();
    stk2.push(pNode);// 将根节点压栈
    if (pNode->left != NULL) // 如果左孩子不为空,则压栈
    {
      stk.push(pNode->left);
    }
    if (pNode->right != NULL) // 如果左孩子不为空,则压栈
    {
      stk.push(pNode->right);
    }
  }
  while(!stk2.empty()){
    cout<<stk2.top()->val<<endl;
    stk2.pop();
  }
}

3.Morris遍历实现

实现思路:

1.先建立一个临时结点dummy,并令其左孩子为根结点root,将当前结点设置为dummy;

2.如果当前结点的左孩子为空,则将其右孩子作为当前结点;

3.如果当前结点的左孩子不为空,则找到其在中序遍历中的前驱结点,

  • -如果前驱结点的右孩子为空,将它的右孩子设置为当前结点,将当前结点更新为当前结点的左孩子;
  • -如果前驱结点的右孩子为当前结点,倒序输出从当前结点的左孩子到该前驱结点这条路径上所有的结点。将前驱结点的右孩子设置为空,将当前结点更新为当前结点的右孩子。

4.重复以上过程,直到当前结点为空。

具体实现:

void reverse(TreeNode* p1,TreeNode *p2){
  if (p1 == p2)
    return;
  TreeNode* x = p1;
  TreeNode* y = p1->right;

  while(true){
    TreeNode* tmp = y->right;
    y->right = x;
    x = y;
    y = tmp;
    if (x == p2)
      break;
  }
}
void printReverse(TreeNode* p1,TreeNode *p2){
  reverse(p1,p2);
  TreeNode* pNode = p2;
  while(true){
    cout<<pNode->val<<endl;
    if (pNode == p1)
      break;
    pNode = pNode->right;
  }
  reverse(p2,p1);
}
void PostOrder3(TreeNode* root){
  if(root == NULL)
    return;

  TreeNode *dummy = new TreeNode(-1);
  dummy->left = root;
  TreeNode *pNode = dummy;
  while(pNode != NULL) {
    if(pNode->left == NULL)
      pNode = pNode->right;
    else {
      TreeNode *pPrev = pNode->left;
      while(pPrev->right != NULL && pPrev->right != pNode)
        pPrev = pPrev->right;

      if(pPrev->right == NULL) {
        pPrev->right = pNode;
        pNode = pNode->left;
      }
      else {
        printReverse(pNode->left, pPrev);
        pPrev->right = NULL;
        pNode = pNode->right;
      }
    }
  }
}

总结

上述三种遍历方式时间复杂度和空间复杂度分析:

1.递归遍历和非递归遍历 时间复杂度0(n) 空间复杂度O(n)

2.Morris遍历 时间复杂度0(n) 空间复杂度O(1)

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持我们。

(0)

相关推荐

  • 举例讲解C语言程序中对二叉树数据结构的各种遍历方式

    二叉树遍历的基本思想 二叉树的遍历本质上其实就是入栈出栈的问题,递归算法简单且容易理解,但是效率始终是个问题.非递归算法可以清楚的知道每步实现的细节,但是乍一看不想递归算法那么好理解,各有各的好处吧.接下来根据下图讲讲树的遍历. 1.先序遍历:先序遍历是先输出根节点,再输出左子树,最后输出右子树.上图的先序遍历结果就是:ABCDEF 2.中序遍历:中序遍历是先输出左子树,再输出根节点,最后输出右子树.上图的中序遍历结果就是:CBDAEF 3.后序遍历:后序遍历是先输出左子树,再输出右子树,最后输

  • C语言实现线索二叉树的定义与遍历示例

    本文实例讲述了C语言实现线索二叉树的定义与遍历.分享给大家供大家参考,具体如下: #include <stdio.h> #include <malloc.h> typedef char TElemType; // 二叉树的二叉线索存储表示 typedef enum{ Link, Thread }PointerTag; // Link(0):指针,Thread(1):线索 typedef struct BiThrNode { TElemType data; struct BiThrN

  • C语言非递归后序遍历二叉树

    本文实例为大家分享了C语言非递归后序遍历二叉树的具体代码,供大家参考,具体内容如下 法一:实现思路:一个栈 先按 根->右子树->左子树的顺序访问二叉树.访问时不输出.另一个栈存入前一个栈只进栈的结点. 最后输出后一个栈的结点数据. #include<stdio.h> #include<stdlib.h> typedef struct TreeNode{ char element; struct TreeNode *left,*right; }Tree,*BTree;

  • C语言实现二叉树遍历的迭代算法

    本文实例讲述了C语言实现二叉树遍历的迭代算法,是数据结构算法中非常经典的一类算法.分享给大家供大家参考. 具体实现方法如下: 二叉树中序遍历的迭代算法: #include <iostream> #include <stack> using namespace std; struct Node { Node(int i, Node* l = NULL, Node* r = NULL) : item(i), left(l), right(r) {} int item; Node* le

  • C语言数据结构之二叉树的非递归后序遍历算法

    C语言数据结构之二叉树的非递归后序遍历算法 前言: 前序.中序.后序的非递归遍历中,要数后序最为麻烦,如果只在栈中保留指向结点的指针,那是不够的,必须有一些额外的信息存放在栈中. 方法有很多,这里只举一种,先定义栈结点的数据结构 typedef struct{Node * p; int rvisited;}SNode //Node 是二叉树的结点结构,rvisited==1代表p所指向的结点的右结点已被访问过. lastOrderTraverse(BiTree bt){ //首先,从根节点开始,

  • C语言二叉树常见操作详解【前序,中序,后序,层次遍历及非递归查找,统计个数,比较,求深度】

    本文实例讲述了C语言二叉树常见操作.分享给大家供大家参考,具体如下: 一.基本概念 每个结点最多有两棵子树,左子树和右子树,次序不可以颠倒. 性质: 1.非空二叉树的第n层上至多有2^(n-1)个元素. 2.深度为h的二叉树至多有2^h-1个结点. 满二叉树:所有终端都在同一层次,且非终端结点的度数为2. 在满二叉树中若其深度为h,则其所包含的结点数必为2^h-1. 完全二叉树:除了最大的层次即成为一颗满二叉树且层次最大那层所有的结点均向左靠齐,即集中在左面的位置上,不能有空位置. 对于完全二叉

  • C语言二叉树的非递归遍历实例分析

    本文以实例形式讲述了C语言实现二叉树的非递归遍历方法.是数据结构与算法设计中常用的技巧.分享给大家供大家参考.具体方法如下: 先序遍历: void preOrder(Node *p) //非递归 { if(!p) return; stack<Node*> s; Node *t; s.push(p); while(!s.empty()) { t=s.top(); printf("%d\n",t->data); s.pop(); if(t->right) s.pus

  • C语言数据结构之线索二叉树及其遍历

    C语言数据结构之线索二叉树及其遍历 遍历二叉树就是以一定的规则将二叉树中的节点排列成一个线性序列,从而得到二叉树节点的各种遍历序列,其实质是:对一个非线性的结构进行线性化.使得在这个访问序列中每一个节点都有一个直接前驱和直接后继.传统的链式结构只能体现一种父子关系,¥不能直接得到节点在遍历中的前驱和后继¥,而我们知道二叉链表表示的二叉树中有大量的空指针,当使用这些空的指针存放指向节点的前驱和后继的指针时,则可以更加方便的运用二叉树的某些操作.引入线索二叉树的目的是: 为了加快查找节点的前驱和后继

  • C语言二叉树的三种遍历方式的实现及原理

    二叉树遍历分为三种:前序.中序.后序,其中序遍历最为重要.为啥叫这个名字?是根据根节点的顺序命名的. 比如上图正常的一个满节点,A:根节点.B:左节点.C:右节点,前序顺序是ABC(根节点排最先,然后同级先左后右):中序顺序是BAC(先左后根最后右):后序顺序是BCA(先左后右最后根). 比如上图二叉树遍历结果 前序遍历:ABCDEFGHK 中序遍历:BDCAEHGKF 后序遍历:DCBHKGFEA 分析中序遍历如下图,中序比较重要(java很多树排序是基于中序,后面讲解分析) 下面介绍一下,二

  • 图解二叉树的三种遍历方式及java实现代码

    二叉树(binary tree)是一颗树,其中每个节点都不能有多于两个的儿子. 1.二叉树节点 作为图的特殊形式,二叉树的基本组成单元是节点与边:作为数据结构,其基本的组成实体是二叉树节点(binary tree node),而边则对应于节点之间的相互引用. 如下,给出了二叉树节点的数据结构图示和相关代码: // 定义节点类: private static class BinNode { private Object element; private BinNode lChild;// 定义指向

  • Java二叉树的四种遍历方式详解

    二叉树的四种遍历方式: 二叉树的遍历(traversing binary tree)是指从根结点出发,按照某种次序依次访问二叉树中所有的结点,使得每个结点被访问依次且仅被访问一次. 四种遍历方式分别为:先序遍历.中序遍历.后序遍历.层序遍历. 遍历之前,我们首先介绍一下,如何创建一个二叉树,在这里用的是先建左树在建右树的方法, 首先要声明结点TreeNode类,代码如下: public class TreeNode { public int data; public TreeNode leftC

  • 对python For 循环的三种遍历方式解析

    实例如下所示: array = ["a","b","c"] for item in array: print(item) for index in range(len(array)): print(str(index)+".."+array[index]) for index,val in enumerate(array): print(str(index)+"--"+val); 打印结果 a b c 0.

  • Go语言实现二维数组的2种遍历方式以及案例详解

    二维数组遍历的2种方式: package main import ( "fmt" ) func main() { //定义一个二维数组 var arr = [2][3]int{{1, 4, 3},{7, 5, 6}} //方式1. 用for循环来遍历 for i := 0; i < len(arr); i++ { for j := 0; j < len(arr[i]); j++ { fmt.Printf("%v ",arr[i][j]) } fmt.Pr

  • 教你如何使用Python实现二叉树结构及三种遍历

    一:代码实现 class TreeNode: """节点类""" def __init__(self, mid, left=None, right=None): self.mid = mid self.left = left self.right = right # 树类 class Tree: """树类""" def __init__(self, root=None): self.r

  • C语言中斐波那契数列的三种实现方式(递归、循环、矩阵)

    目录 一.递归 二.循环 三.矩阵 <剑指offer>里讲到了一种斐波那契数列的 O(logN) 时间复杂度的实现,觉得挺有意思的,三种方法都记录一下. 一.递归 一般来说递归实现的代码都要比循环要简洁,但是效率不高,比如递归计算斐波那契数列第n个元素. long long Fibonacci_Solution1(unsigned int n) { // printf("%d ", n); if (n <= 0) return 0; if (n == 1) retur

  • Python 二叉树的层序建立与三种遍历实现详解

    前言 二叉树(Binary Tree)时数据结构中一个非常重要的结构,其具有....(此处省略好多字)....等的优良特点. 之前在刷LeetCode的时候把有关树的题目全部跳过了,(ORZ:我这种连数据结构都不会的人刷j8Leetcode啊!!!) 所以 !!!敲黑板了!!!今天我就在B站看了数据结构中关于树的内容后,又用我浅薄的Python大法来实现一些树的建立和遍历. 关于树的建立我觉得层序建立对于使用者来说最为直观,输入很好写.(好吧,我是看LeetCode中的树输入都是采用层序输入觉得

  • Python实现重建二叉树的三种方法详解

    本文实例讲述了Python实现重建二叉树的三种方法.分享给大家供大家参考,具体如下: 学习算法中,探寻重建二叉树的方法: 用input 前序遍历顺序输入字符重建 前序遍历顺序字符串递归解析重建 前序遍历顺序字符串堆栈解析重建 如果懒得去看后面的内容,可以直接点击此处本站下载完整实例代码. 思路 学习算法中,python 算法方面的资料相对较少,二叉树解析重建更少,只能摸着石头过河. 通过不同方式遍历二叉树,可以得出不同节点的排序.那么,在已知节点排序的前提下,通过某种遍历方式,可以将排序进行解析

  • Map集合的四种遍历方式代码示例

    很久以前写的代码,和上一个做比较吧!便于以后查看. import java.util.HashMap; import java.util.Iterator; import java.util.Map; public class TestMap { public static void main(String[] args) { Map<Integer, String> map = new HashMap<Integer, String>(); map.put(1, "a&

随机推荐