精华内容
下载资源
问答
  • 遍历二叉树 遍历二叉树的先序、中序和非递归遍历二叉树的六种算法
  • 遍历二叉树

    千次阅读 2017-11-22 17:21:41
    遍历二叉树
     
    遍历二叉树
     
           今天我们学习了二叉树,现在我就基于二叉树的递归定义来说一说遍历二叉树的三种方法:先序、中序和后序。
           根据二叉树的递归定义可知,二叉树是由3个基本单元组成:根结点、左子树和右子树。因此若能依次遍历这三部分,便是遍历了整个二叉树。假如用L、D、R分别表示遍历左子树、访问根结点和遍历右子树,则可有DLR、LDR、LRD、DRL、RDL、RLD这6钟遍历二叉树的方案。若限定先左后右,则只有前3种情况,分别称之为先序遍历、中序遍历和后序遍历。下面我就分别来讲讲这三种遍历的规则吧!
    一、先序遍历:
           先序遍历的规则为:1.首先访问根结点;2.然后遍历左子树;3.最后遍历右子树。我们可以用一句口诀来帮助我们的记忆:先根再左后右。我知道只是这样口头说的话可能很难理解,我们用一个例子来解释一下吧:
    如上图所示:根据口诀:先根意思是先访问根结点得到第一个是A;再左,再访问左子树,访问到左子树时继续用口诀得到左子树的序列为BDE,然后再访问E的子树H;后右,最后访问右子树,也继续用那个口诀,得到右子树的序列为CFG;把所有遍历的序列结合起来就可以得到此二叉树的先序遍历结果:ABDEHCFG。先序遍历的代码实现如下:
     
    void PreOrder(PBTNode pHead) {
        if (NULL == pHead) {
            return;
        }
        printf("%C ",pHead->num);  //先访问根结点
        PreOrder(pHead->leftNode);  //再遍历左子树
        PreOrder(pHead->rightNode); //最后遍历右子树
    }
    
    二、中序遍历:
           中序遍历的规则为:1.首先遍历左子树;2.然后访问根结点;最后遍历右子树;同样可以用一句口诀可以概括:先左再根后右,我们依然以上图为例:先左,首先遍历左子树,得到序列DBE,因为B的右子树E的下面还有一个子树,但是是右子树,所以A的左子树的序列为DBEH;再根,然后再访问根结点;后右,最后再访问右子树,得到序列FCG;把所有遍历的序列结合起来就得到此二叉树的中序遍历结果:DBEHAFCG。中序遍历的代码实现如下:
     
    void InOrder(PBTNode pHead){
        if (NULL == pHead) {
            return;
        }
            InOrder(pHead->leftNode);//先遍历左子树
            printf("%C ", pHead->num);//再访问根结点
            InOrder(pHead->rightNode);//最后遍历右子树
    }
    三、后序遍历:
           后序遍历的规则为:1.首先遍历左子树;2.然后遍历右子树;3.最后访问根结点;依然用一句口诀:先左再右后根。我们还以上图为例用后序遍历的方法来遍历二叉树:先左,首先遍历左子树,得到序列DEB,因为E的子树为右子树,所以A的左子树的序列应该为DHEB;再右,然后再来遍历右子树,得到序列FGC;后根,最后再访问根结点;所以把所有遍历的序列结合起来就得到此二叉树的后序遍历结果:DHEBFGCA。后序遍历的代码实现如下:
     
    void PostOrder(PBTNode pHead) {
        if (NULL == pHead) {
            return;
        }
        PostOrder(pHead->leftNode);//先遍历左子树
        PostOrder(pHead->rightNode);//再遍历右子树
        printf("%C ", pHead->num);//最后访问根结点
    }
           
           这里需要说明一点的是由二叉树的先序序列和中序序列,或由其后序序列和中序序列都能唯一地确定一棵二叉树。下面我依然用一个例题来解释一下:
    例:
    设一棵二叉树的先序序列为:ABDFCEGH,中序序列为:BFDAGEHC
    1.画出这棵二叉树。
    2.用后序遍历来遍历这棵二叉树。
    这道题的解法为:首先我们可以根据先序序列来确定根结点A,然后根据中序序列来确定A的左子树BFD和右子树GEHC然后用同样的方法可以知道A的左子树和右子树的结构,最后可以得到如下图所示的二叉树:
           下面我们再来看看第二小题:用后序遍历来遍历这棵二叉树,同样记住这个口诀:先左再右后根,我们很容易便可以得出这棵二叉树的后序遍历序列为:FDBGHECA。
            以上就是我对遍历二叉树的一些理解,如果有什么不对的地方欢迎指正!!!
    展开全文
  • 二叉树遍历 二叉树遍历
  • 遍历 访问函数 主代码 定义结点数据类型 typedef struct bitnode { char data; struct bitnode *Lchild,*Rchild; } BiTNode,*BiTree; 建立一颗带头结点的二叉树 BiTree CreatTree() { BiTree p...

    目录

    定义结点数据类型

    建立一颗带头结点的二叉树

    遍历

    访问函数

    主代码



    定义结点数据类型

    typedef struct bitnode
    {
        char data;
        struct bitnode *Lchild,*Rchild;
    } BiTNode,*BiTree;


    建立一颗带头结点的二叉树

    BiTree CreatTree()
    {
        BiTree p;
        p=new(BiTNode);
        p->Lchild=NULL;
        p->Rchild=NULL;
        return p;
    }


    遍历

    访问函数

    void visit(BiTree bt)
    {
        cout<<bt->data<<' ';
    }


     

    ///DLR 前序
    void PreOrder(BiTree bt)
    {
        if(bt!=NULL)
        {
            visit(bt);
            PreOrder(bt->Lchild);
            PreOrder(bt->Rchild);
        }
        return;
    }

     

    ///LDR 中序
    void InOrder(BiTree bt)
    {
        if(!bt)
            return;
        else
        {
            InOrder(bt->Lchild);
            //cout<<bt->data;
            visit(bt);
            InOrder(bt->Rchild);
        }
    }

     

    ///LRD  后序
    void PostOrder(BiTree bt)
    {
        if(bt!=NULL)
        {
            PostOrder(bt->Lchild);
            PostOrder(bt->Rchild);
            visit(bt);
        }
        return;
    }



    主代码

    #include<bits/stdc++.h>
    using namespace std;
    typedef struct bitnode
    {
        char data;
        struct bitnode *Lchild,*Rchild;
    } BiTNode,*BiTree;
    ///建立一颗带头结点的二叉树
    
    BiTree CreatTree()
    {
        BiTree p;
        p=new(BiTNode);
        p->Lchild=NULL;
        p->Rchild=NULL;
        return p;
    }
    ///遍历
    void visit(BiTree bt)
    {
        cout<<bt->data<<' ';
    }
    ///DLR 前
    void PreOrder(BiTree bt)
    {
        if(bt!=NULL)
        {
            visit(bt);
            PreOrder(bt->Lchild);
            PreOrder(bt->Rchild);
        }
        return;
    }
    ///LDR 中
    void InOrder(BiTree bt)
    {
        if(!bt)
            return;
        else
        {
            InOrder(bt->Lchild);
            visit(bt);
            InOrder(bt->Rchild);
        }
    
    }
    ///LRD  后
    void PostOrder(BiTree bt)
    {
        if(bt!=NULL)
        {
            PostOrder(bt->Lchild);
            PostOrder(bt->Rchild);
            visit(bt);
        }
        return;
    }
    
    int main()
    {
        BiTree bt;
        bt=CreatTree();///建树
        /*  插入结点
          .....
                     */
        //遍历
        PreOrder(bt);
        InOrder(bt);
        PostOrder(bt);
        return 0;
    
    }
    

     

    展开全文
  • 【数据结构——遍历二叉树和线索二叉树】

    千次阅读 多人点赞 2020-10-30 20:04:04
    【数据结构——遍历二叉树和线索二叉树】 目录【数据结构——遍历二叉树和线索二叉树】一、遍历二叉树二级目录三级目录二、线索二叉树二级目录三级目录 一、遍历二叉树 二级目录 三级目录 二、线索二叉树 二级目录 ...

    【数据结构——遍历二叉树和线索二叉树】

    一、遍历二叉树

    遍历的定义——指按某条搜索路线遍访每个结点且不重复(又称周游)

    (一)遍历的三种规则

    1、先序遍历

    在这里插入图片描述

    若二叉树为空,则:空操作
    否则:
    访问根结点(D);
    先序遍历左子树(L);
    先序遍历右子树(R);

    void PreOrderTraverse(BiTree T)
    {
    	if (T)  //非空二叉树
    	{
    		printf("%d", T->data);  //访问根结点
    		PreOrderTraverse(T->lchild); //递归遍历左子树
    		PreOrderTraverse(T->rchild);  //递归遍历右子树
    	}
    }
    

    2、中序遍历

    在这里插入图片描述

    若二叉树为空,则:空操作
    否则:

    中序遍历左子树(L);
    访问根结点(D);
    中序遍历右子树(R);

    void InOrderTraverse(BiTree T)
    {
    	if (T)  //非空二叉树
    	{
    		InOrderTraverse(T->lchild); //递归遍历左子树
    		printf("%d", T->data);  //访问根结点
    		InOrderTraverse(T->rchild);  //递归遍历右子树
    	}
    }
    

    3、后序遍历

    在这里插入图片描述

    若二叉树为空,则:空操作
    否则:

    后序遍历左子树(L);
    后序遍历右子树(R);
    访问根结点(D);

    void PostOrderTraverse(BiTree T)
    {
    	if (T)  //非空二叉树
    	{
    		PostOrderTraverse(T->lchild); //递归遍历左子树
    		PostOrderTraverse(T->rchild);  //递归遍历右子树
    		printf("%d", T->data);  //访问根结点
    	}
    }
    

    (二)遍历的相关算法

    1、先序遍历建立二叉链表

    扩充先序序列:先序遍历二叉树时,如果当前要访问的结点不空,就记下这个结点值,如果空,就以“#”记下来,所得到的遍序序列。

    例如:下图的先序遍历序列是:ABCDEFG
    在这里插入图片描述

    扩充先序序列为:ABC##DE#G##F###

    在这里插入图片描述

    //先序遍历建立二叉链表
    void CreateBiTree(BiTree& T)
    {
    	scanf_s("%c", ch);
    	if (ch == "#")
    		T = NULL;//递归结束,建立空树
    	else
    	{
    		T = new BiTNode;
    		T->data = ch;//生成根结点
    		CreateBiTree(T->lchild);//递归建立左子树
    		CreateBiTree(T->rchild);//递归建立右子树
    	}
    }
    

    2、统计二叉树中叶子结点的个数

    算法基本思想:

    1、若二叉树为空,则叶子结点个数为零
    2、若二叉树中左儿子和右儿子均为空,则叶子结点的个数为1
    3、否则,整个二叉树的叶子结点个数等于其左子树中叶子结点个数和其右子树的叶子结点个数之和

    //统计二叉树中叶子结点的个数
    int CountLeaf(BiTree T)
    {
    	if (!T)
    		return 0;//空树返回0
    	if (!T->lchild && !T->rchild)
    		return 1;//结点无左右孩子返回1
    	else
    	{
    		m = CountLeaf(T->lchild);//递归统计左子树的叶子结点
    		n = CountLeaf(T->rchild);//递归统计右子树的叶子结点
    		return m + n;
    	}
    }
    

    3、求二叉树的深度

    算法基本思想:

    1、若二叉树为空树,则深度为0
    2、否则,二叉树的深度为左右子树的深度的最大值+1

    /*求二叉树的深度*/
    int Depth(BiTree T)
    {
    	if (!T) return 0;//空树
    	else  //二叉树的深度应该为左右子树的最大深度+1
    	{
    		m = Depth(T->lchild);
    		n = Depth(T->rchild);
    		if (m > n)
    			return (m + 1);
    		else
    			return (n + 1);
    	}
    }
    

    4、复制二叉树

    算法基本思想:

    1、若二叉树为空,则复制的二叉树也为空
    2、若二叉树不为空,则首先复制根结点,然后分别复制二叉树根结点的左子树和右子树

    /*复制二叉树*/
    void Copy(BiTree T, BiTree& NewT)
    {
    	if (!T)
    	{
    		NewT = NULL;//空树,递归结束
    		return;
    	}
    	else
    	{
    		NewT = new BiTNode;
    		NewT->data = T->data;//复制根结点
    		Copy(T->lchild, NewT->lchild);//递归复制左子树
    		Copy(T->rchild, NewT->rchild);//递归复制右子树
    	}
    }
    

    5、统计二叉树中结点的个数

    算法基本思想:

    1、如果是空树,则结点个数为0
    2、结点个数为左子树结点个数加上右子树结点个数再加一

    /*统计二叉树中结点的个数*/
    int NodeCount(BiTree T)
    {
    	if (!T)
    		return 0;
    	else
    		return NodeCount(T->lchild) + NodeCount(T->rchild) + 1;
    }
    

    二、线索二叉树

    1、相关概念

    线索:指向前驱或者后继结点的指针称为线索
    线索二叉树:加上线索的二叉链表表示的二叉树叫做线索二叉树
    线索化:对二叉树按某种遍历次序使其变为线索二叉树的过程叫做线索化
    ——在有n个结点的二叉链表中必定有n+1个空链域
    ——在线索二叉树的结点中增加两个标志域
    例如:

    在这里插入图片描述
    先序、中序、后续线索二叉树
    在这里插入图片描述

    在这里插入图片描述
    (1)先序线索化
    在这里插入图片描述
    (2)中序线索化
    在这里插入图片描述

    (3)后序线索化
    在这里插入图片描述
    注意:增加一个头结点

    • 头结点(如下图中的中序遍历):
    • LTag=0,lchild指向根结点
    • RTag=1,rchild指向遍历序列中最后一个结点
    • 遍历序列中的第一个结点的lchild域、最后一个结点的rchild域都指向头结点

    在这里插入图片描述

    2、中序线索化算法

    二叉树的二叉线索存储表示:

    /*二叉树的二叉线索存储表示*/
    typedef struct BiThrNode
    {
    	TElemType data;//数据域
    	struct BiThrNode* lchild, * rchild;//左右孩子指针
    	int LTag, RTag;//左右标志
    }BiThrNode,*BiThrTree;
    

    中序线索化是在已建立好的二叉链表(每个结点5个域)上,按中序遍历的方法在访问根结点时建立线索。

    算法一:以结点p为根的子树中序线索化
    算法步骤

    算法中有一全局变量:pre,在主调程序中初值为空,在整个线索化算法中pre始终指向当前结点p的前驱

    1、如果p非空,左子树递归线索化
    2、如果p的左子树为空,则给p加上左线索,将其LTag置为1,让p的左孩子指针指向pre(前驱);否则将p的LTag置为0
    3、如果pre的右孩子为空,则给pre加上右线索,将其RTag置为1.让pre的右孩子指针指向p(后继);否则将pre的RTag置为0
    4、将pre指向刚访问过的结点P,即pre = p
    5、右子树递归线索化

    算法描述

    /*以结点p为根的子树中序线索化*/
    void InThreading(BiThrTree p)
    {//pre为全局变量,初始化时其右孩子指针为空,便于在树的最左点开始建线索
    	if (p)
    	{
    		InThreading(p->lchild);//左子树递归线索化
    		if (!p->lchild)//p的左孩子为空
    		{
    			p->LTag = 1;//给p加上左线索
    			p->lchild = pre;//p的左孩子指针指向pre(前驱)
    		}
    		else
    			p->LTag = 0;
    		if (!p->rchild)//pre的右孩子为空
    		{
    			pre->RTag = 1;//给pre加上右线索
    			pre->rchild = p;//pre右孩子指针指向p(后继)
    		}
    		else
    			pre->RTag = 0;
    		pre = p;//保持pre指向p的前驱
    		InThreading(p->rchild);//右子树递归线索化
    	}
    }
    

    算法二:带头结点的中序线索化
    算法描述

    /*带有结点的二叉树中序线索化*/
    void InOrderThreading(BiThrTree& Thrt, BiThrTree T)
    {//中序遍历二叉树T,并将其中序线索化,Thrt指向头结点
    	Thrt = new BiThrNode;//建立结点
    	Thrt->LTag = 0;//头结点有左孩子,若树非空,则其左孩子为树根
    	Thrt->RTag = 1;//头结点的右孩子指针为右线索
    	Thrt->rchild = Thrt;//初始化时右指针指向自己
    	if (!T) Thrt->lchild = Thrt;//若树为空,则左指针也指向自己
    	else
    	{
    		Thrt->lchild = T;pre = Thrt;//头结点的左孩子指向根,pre初值指向头结点
    		InThreading(T);//调用算法一,对以T为根的二叉树进行中序线索化
    		pre->rchild = Thrt;//调用算法一结束后,pre为最右节点,pre的右线索指向头结点
    		pre->RTag = 1;
    		Thrt->rchild = pre;//头结点的右线索指向pre
    	}
    }
    

    3、遍历中序线索二叉树

    在中序线索二叉树中找p指针所指结点前驱的方法:

    1、若R->LTag = 1;则 lchild 域直接指向其前驱
    2、若R->LTag = 0;则结点的前驱应是其左子树的右链尾(RTag = 1)的结点

    在中序线索二叉树中找p指针所指结点后继的方法:

    1、若R->RTag = 1;则 rchild 域直接指向其后继
    2、若R->RTag = 0;则结点的后继应是其右子树的左链尾(LTag = 1)的结点

    /*遍历中序线索二叉树*/
    void InOrderTraverse_Thr(BiThrTree T)
    {//T指向头结点,头结点的左链lchild指向根结点
     //中序遍历二叉线索树T的非递归算法,对每个数据元素直接输出
    	p = T->lchild;//p指向根结点
    	while (p != T)//空树或遍历结束时,p==T
    	{
    		while (p->LTag == 0)//沿左孩子向下
    			p = p->lchild;//访问其左子树为空的结点
    		cout << p->data;
    		while (p->RTag == 1 && p->rchild != T)
    		{
    			p = p->rchild;//沿右线索访问其后继结点
    			cout << p->data;
    		}
    		p = p->rchild;
    	}
    }
    
    展开全文
  • 一般文件夹结构是n叉树,又不是二叉树,为什么要遍历二叉树呢?
  • 遍历二叉树

    2019-09-29 08:38:31
    java实现创建二叉树,并且遍历二叉树(此处使用非递归方式遍历); 用出栈入栈的方式遍历二叉树
  • 遍历二叉树C实现代码

    2018-02-24 20:17:25
    遍历二叉树的几种算法实现,主要如下: 1.前序遍历二叉树; 2.中序遍历二叉树; 3.后序遍历二叉树; 4.层次遍历二叉树
  • 层次遍历二叉树

    2014-10-24 12:14:16
    层次遍历二叉树
  • 分层遍历二叉树

    2015-10-18 20:58:56
    分层遍历二叉树
  • 6.3遍历二叉树和线索二叉树 6.3.1 遍历二叉树 一问题的提出 二先左后右的遍历算法 三算法的递归描述 四中序遍历算法的非递归描述 五遍历算法的应用举例 一问题的提出 何谓二叉树的遍历 顺着某一条搜索路径巡访二叉树...
  • 本题来自左神《程序员代码面试指南》“遍历二叉树的神级方法”题目。 题目 给定一棵二叉树的头节点 head,完成二叉树的先序、中序和后序遍历。如果二叉树的节点数为N,则要求时间复杂度为O(N),额外空间复杂度为O(1...

    本题来自左神《程序员代码面试指南》“遍历二叉树的神级方法”题目。

    题目

    给定一棵二叉树的头节点 head,完成二叉树的先序、中序和后序遍历。如果二叉树的节点数为N,则要求时间复杂度为O(N),额外空间复杂度为O(1)

    题解

    之前的题目已经剖析过如何用递归和非递归的方法实现遍历二叉树,但是很不幸,之前所有的方法虽然常用,但都无法做到额外空间复杂度为O(1)。这是因为遍历二叉树的递归方法实际使用了函数栈,非递归的方法使用了申请的栈,两者的额外空间都与树的高度相关,所以空间复杂度为O(h),h为二叉树的高度。

    如果完全不用栈结构,能完成三种遍历吗?答案是可以。方法是使用二叉树节点中大量指向null 的指针,本题实际上就是大名鼎鼎的Morris 遍历,由Joseph Morris 于1979年发明。

    首先来看普通的递归和非递归解法,其实都使用了栈结构,在处理完二叉树某个节点后可以回到上层去。为什么从下层回到上层会如此之难?因为二叉树的结构如此,每个节点都有指向孩子节点的指针,所以从上层到下层容易,但是没有指向父节点的指针,所以从下层到上层需要用栈结构辅助完成。

    Morris 遍历的实质就是避免用栈结构,而是让下层到上层有指针,具体是通过让底层节点指向null 的空闲指针指回上层的某个节点,从而完成下层到上层的移动。我们知道,二叉树上的很多节点都有大量的空闲指针,比如,某些节点没有右孩子节点,那么这个节点的right 指针就指向null,我们称为空闲状态,Morris 遍历正是利用了这些空闲指针。

    我们先不管先序、中序、后序的概念,先看看 Morris 遍历的过程

    假设当前节点为cur,初始时cur 就是整棵树的头节点,根据以下标准让cur 移动

    1. 如果cur 为null,则过程停止,否则继续下面的过程。
    2. 如果cur 没有左子树,则让cur 向右移动,即令cur = cur.right。
    3. 如果cur 有左子树,则找到cur 左子树上最右的节点,记为mostRight。
      1. 如果mostRight 的right 指针指向 null,则令mostRight.right = cur,也就是让mostRight
        的right 指针指向当前节点,然后让cur 向左移动,即令cur = cur.left。
      2. 如果mostRight 的right 指针指向 cur,则令mostRight.right = null,也就是让mostRight
        的 right 指针指向 null(目的是让二叉树恢复原状),然后让cur 向右移动,即令cur = cur.right。

    举个例子:假设一棵二叉树如图 3-9 所示
    在这里插入图片描述

    cur 依次到达的节点为:4、2、1、2、3、4、6、5、6、7,我们将这个序列叫Morris 序。

    可以看出,在一棵二叉树中,对于有左子树的节点都可以到达两次,对于没有左子树的节点都只会到达一次。

    对于任何一个能够到达两次的节点Y,是 如何知道此时的 cur 是第一次来到 Y 还是第二次来到 Y 呢如果Y 的左子树上的最右节点的指针(mostRight.right)是指向 null的,那么此时 cur 就是第一次到达Y;如果 mostRight.right 是指向 Y 的,那么此时cur 就是第二次到达 Y。这就是 Morris 遍历和 Morris 序的实质。

    请读者先理解Morris 遍历和Morris 序,因为可以根据Morris 序进一步加工出先序、中序和后序.

    package chapter_3_binarytreeproblem;
    
    public class Problem_05_MorrisTraversal {
    
    	public static class Node {
    		public int value;
    		Node left;
    		Node right;
    
    		public Node(int data) {
    			this.value = data;
    		}
    	}
    
    	/**
    	 * Morris序遍历
    	 */
    	public static void morris(Node head) {
    		if (head == null) {
    			return;
    		}
    		Node cur = head;
    		Node mostRight = null;
    		while (cur != null) {
    			mostRight = cur.left;
    			if (mostRight != null) { // 如果当前cur有左子树
    				// 找到cur左子树上最右的节点
    				while (mostRight.right != null && mostRight.right != cur) {
    					mostRight = mostRight.right;
    				}
    				// 从上面的while里出来后,mostRight就是cur左子树上最右的节点
    				if (mostRight.right == null) { // 如果mostRight.right是指向null的
    					mostRight.right = cur; // 让其指向cur
    					cur = cur.left; // cur向左移动
    					continue; // 回到最外层的while,继续判断cur的情况
    				} else { // 如果mostRight.right是指向cur的
    					mostRight.right = null; // 让其指向null
    				}
    			}
    			// cur如果没有左子树,cur向右移动
    			// 或者cur左子树上最右节点的右指针是指向cur的,cur向右移动
    			cur = cur.right;
    		}
    	}
    
    	/**
    	 * 中序遍历
    	 */
    	public static void morrisIn(Node head) {
    		if (head == null) {
    			return;
    		}
    		Node cur = head;
    		Node mostRight = null;
    		while (cur != null) {
    			mostRight = cur.left;
    			if (mostRight != null) {  // 如果当前cur有左子树
    				while (mostRight.right != null && mostRight.right != cur) {
    					mostRight = mostRight.right;
    				}
    				if (mostRight.right == null) { // 如果mostRight.right是指向null的
    					mostRight.right = cur;
    					cur = cur.left;
    					continue;
    				} else { // 如果mostRight.right是指向cur的
    					mostRight.right = null;
    				}
    			}
    			// cur没有左子树,或者cur左子树上最右节点的右指针是指向cur的
    			System.out.print(cur.value + " ");
    			cur = cur.right;
    		}
    		System.out.println();
    	}
    
    	/**
    	 * 前序遍历
    	 */
    	public static void morrisPre(Node head) {
    		if (head == null) {
    			return;
    		}
    		Node cur = head;
    		Node mostRight = null;
    		while (cur != null) {
    			mostRight = cur.left;
    			if (mostRight != null) {  // 如果当前cur有左子树
    				while (mostRight.right != null && mostRight.right != cur) {
    					mostRight = mostRight.right;
    				}
    				if (mostRight.right == null) { // 如果mostRight.right是指向null的,即第一次到达
    					mostRight.right = cur;
    					System.out.print(cur.value + " ");
    					cur = cur.left;
    					continue;
    				} else { // 如果mostRight.right是指向cur的,第二次到达
    					mostRight.right = null;
    				}
    			} else {
    				System.out.print(cur.value + " ");
    			}
    			cur = cur.right;
    		}
    		System.out.println();
    	}
    
    	/**
    	 * 后序遍历
    	 */
    	public static void morrisPos(Node head) {
    		if (head == null) {
    			return;
    		}
    		Node cur = head;
    		Node mostRight = null;
    		while (cur != null) {
    			mostRight = cur.left;
    			if (mostRight != null) {
    				while (mostRight.right != null && mostRight.right != cur) {
    					mostRight = mostRight.right;
    				}
    				if (mostRight.right == null) {
    					mostRight.right = cur;
    					cur = cur.left;
    					continue;
    				} else {
    					mostRight.right = null;
    					printEdge(cur.left);
    				}
    			}
    			cur = cur.right;
    		}
    		printEdge(head);
    		System.out.println();
    	}
    
    	public static void printEdge(Node head) {
    		Node tail = reverseEdge(head);
    		Node cur = tail;
    		while (cur != null) {
    			System.out.print(cur.value + " ");
    			cur = cur.right;
    		}
    		reverseEdge(tail);
    	}
    
    	public static Node reverseEdge(Node from) {
    		Node pre = null;
    		Node next = null;
    		while (from != null) {
    			next = from.right;
    			from.right = pre;
    			pre = from;
    			from = next;
    		}
    		return pre;
    	}
    
    	// for test -- print tree
    	public static void printTree(Node head) {
    		System.out.println("Binary Tree:");
    		printInOrder(head, 0, "H", 17);
    		System.out.println();
    	}
    
    	public static void printInOrder(Node head, int height, String to, int len) {
    		if (head == null) {
    			return;
    		}
    		printInOrder(head.right, height + 1, "v", len);
    		String val = to + head.value + to;
    		int lenM = val.length();
    		int lenL = (len - lenM) / 2;
    		int lenR = len - lenM - lenL;
    		val = getSpace(lenL) + val + getSpace(lenR);
    		System.out.println(getSpace(height * len) + val);
    		printInOrder(head.left, height + 1, "^", len);
    	}
    
    	public static String getSpace(int num) {
    		String space = " ";
    		StringBuffer buf = new StringBuffer("");
    		for (int i = 0; i < num; i++) {
    			buf.append(space);
    		}
    		return buf.toString();
    	}
    
    	public static void main(String[] args) {
    		Node head = new Node(4);
    		head.left = new Node(2);
    		head.right = new Node(6);
    		head.left.left = new Node(1);
    		head.left.right = new Node(3);
    		head.right.left = new Node(5);
    		head.right.right = new Node(7);
    		printTree(head);
    		morrisIn(head);
    		morrisPre(head);
    		morrisPos(head);
    		printTree(head);
    
    	}
    
    }
    
    
    展开全文
  • 主要介绍了C++ 遍历二叉树实例详解的相关资料,需要的朋友可以参考下
  • c++遍历二叉树

    2015-09-14 08:46:25
    用c++能够遍历二叉树,分享给大家,希望大家喜欢
  • 遍历二叉树程序

    2018-09-28 10:49:35
    遍历二叉树程序,亲自调试,注释详尽,有不懂的随时和大家交流,希望能帮到大家~
  • 递归方式遍历二叉树

    2019-09-27 15:47:02
    java实现创建二叉树,并且遍历二叉树(此处使用递归方式遍历); 创建二叉树的方式有很多,此处使用线性的链表转化成二叉树,链表节点的顺序就是前序遍历的顺序,链表中的null值,代表二叉树左节点或者右节点为null...
  • 先序遍历二叉树

    2014-06-11 22:19:11
    先序遍历二叉树
  • 遍历二叉树就是访问二叉树的每一个节点 二叉树父结点下先左访问,先序遍历(根左右) 例如:遍历以下的二叉树 遍历结果:ABDECF Python代码示例 # !/usr/bin/env python # -*-encoding: utf-8-*- # author:...
  • 按层次遍历二叉树

    2016-04-27 19:42:37
    按层次遍历二叉树
  • 遍历二叉树最全面讲解

    千次阅读 多人点赞 2020-06-11 10:34:33
    遍历二叉树一. 遍历二叉树1.介绍2.遍历的方式3.二叉树遍历的考试方式4. 遍历的应用(重点学习)二.遍历的非递归:(考研要考) 一. 遍历二叉树 1.介绍 什么叫做遍历? 官方回答:是指沿着某条搜索路线,依次对树中...
  • 6.3.1 遍历二叉树遍历定义遍历用途遍历方法指按某条搜索路线遍访每个结点且不重复又称周游它是树结构插入删除修改查找和排序运算的前提是二叉树一切运算的基础和核心对每个结点的查看通常都是先左后右无论是先序中序...
  • 数据结构非递归先序、中序、后序遍历二叉树,数据结构非递归先序、中序、后序遍历二叉树
  • 主要为大家详细介绍了java实现按层遍历二叉树,具有一定的参考价值,感兴趣的小伙伴们可以参考一下

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 259,983
精华内容 103,993
关键字:

怎么遍历二叉树