二叉树学习笔记（一）之遍历二叉树
二叉树基础知识
概念
二叉树的性质
满二叉树与完全二叉树
二叉树的存储结构
顺序存储
链式存储
二叉树的遍历
首先来认识一下遍历
先序遍历
递归遍历
非递归遍历
中序遍历
递归遍历
非递归遍历
后序遍历
递归遍历
非递归遍历
层次遍历
使用队列的非递归遍历
遍历的应用
求二叉树深度
叶子节点计数
销毁二叉树
删除指定元素结点的子树
复制二叉树

二叉树基础知识
概念

二叉树定义：含有n（n>=0）个节点的有限集合
非空二叉树中：

有且仅有一个根节点
其余节点划分为两个互不相交的子集L和R，L称为左子树，R称为右子树


任一结点的左、右子树的根称为该结点的左、右孩子，反过来，该结点称为孩子的双亲
度：结点的孩子个数
叶子结点：度为0 的结点
非叶子结点：度大于0，也称为内部结点或分支结点
二叉树的深度（或高度）：结点的最大层次称为二叉树的深度（或高度）。（所谓层次，根节点即为第一层，以此类推）

二叉树的性质

在非空二叉树的第 i 层上最多右 2^(i-1) 个结点（i>=1）
深度为 k 的二叉树最多有 2^k - 1 个结点（k>=1）
对于任意一颗二叉树，如果度为 0 的结点个数为 n0 ,度为 2 的结点个数为   n2，则 n0 = n2+1
具有 n 个结点的完全二叉树的深度 k = [log2n] + 1
对于含 n 个结点的完全二叉树中编号为 i (1<=i<=n) 的结点

如果 i = 1，则 i 结点是这颗完全二叉树的根，没有双亲；否则其双亲的编号为 [i/2]
如果 2i>n，则 i 结点没有左孩子；否则其左孩子的编号为 2i
如果 2i+1>n，则 i 结点没有右孩子；否则其右孩子的编号为 2i+1



满二叉树与完全二叉树


满二叉树：深度为 k 且有 2^k - 1 个结点的二叉树


完全二叉树：完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。深度为K且含 n 个结点的二叉树，如果其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应，则称之为完全二叉树。换句话讲，在一棵二叉树中，除最后一层外，若其余层都是满的，并且最后一层或者是满的，或者是在右边缺少连续若干节点，则此二叉树为完全二叉树。



二叉树的存储结构
顺序存储
    // 一维数组实现
    typedef char TElemType;	  // 假设结点元素类型为字符
    typedef struct {
    TElemType * elem;	      // 0号单元闲置
    int lastIndex;		      // 二叉树最后一个结点的编号
    } SqBiTree;

链式存储

二叉链表

typedef struct BiTNode{
    TElemType data;	  				// 数据域
    struct BiTNode *lchild,*rchild;	// 左、右孩子指针域
} BiTNode,*BiTNode;


三叉链表

typedef struct TriTNode{
    TElemType data;	  						// 数据域
    struct TriTNode *parent,*lchild,*rchild;// 双亲左、右孩子指针域
} TriTNode,*TriTNode;

二叉树的遍历
首先来认识一下遍历
遍历：树的遍历（也称为树的搜索）是图的遍历的一种，指的是按照某种规则，不重复地访问某种树的所有结点，使得每个结点被且仅被访问的过程。具体的访问操作可能是检查节点的值、更新节点的值等。二叉树的遍历也适用于其它树的遍历。
遍历是二叉树的一类重要操作，也是二叉树的其他一些操作和各种应用算法的基本框架。
遍历有两种类别，一种是深度优先遍历，另一种是广度优先遍历

深度优先遍历：先访问子节点，再访问父节点，最后是第二个子节点

先序遍历：VLR，即根结点->左结点->右节点
中序遍历：LVR，即左结点->根结点->右节点
后序遍历：LRV，即左结点->右结点->根节点


广度优先遍历：先访问第一个子节点，再访问第二个子节点，最后访问父节点，二叉树的广度优先遍历就是层次遍历


由于从给定的某个节点出发，有多个可以前往的下一个节点（树不是线性数据结构），所以在顺序计算（即非并行计算）的情况下，只能推迟对某些节点的访问——即以某种方式保存起来以便稍后再访问。常见的做法是采用栈（LIFO）或队列（FIFO）。由于树本身是一种自我引用（即递归定义）的数据结构，因此很自然也可以用递归方式。
所以，下面我重点总结了这两种不同的遍历实现方式。
注：本文所讲的数据结构均为C语言版
先序遍历
递归遍历
Status PreOrderTraverse(BiTree T,Status(*visit)(TElemType e)){
   if(NULL == T) return OK;
   if(ERROR == visit(T->data))
       return ERROR; //访问结点的数据域
   if(ERROR == PreOrderTraverse(T->lchild,visit))
       return ERROR; //递归遍历T的左子树
   return PreOrderTraverse(T->rchild,visit);//递归遍历T的右子树
    
}

非递归遍历
1.使用栈的非递归先序遍历算法
/**********
二叉链表类型定义：
typedef struct BiTNode {
  TElemType  data;
  struct BiTNode  *lchild,*rchild;
} BiTNode, *BiTree;
栈类型Stack的相关定义：
typedef BiTree SElemType;   	      // 栈的元素类型
Status InitStack(Stack &S); 	      // 初始化栈
Status StackEmpty(Stack S); 	      // 判栈空
Status Push(Stack &S, SElemType e);	  // 进栈
Status Pop(Stack &S, SElemType &e);   // 出栈 
Status GetTop(Stack S, SElemType &e); // 取栈顶元素
**********/
void PreOrder(BiTree T, void (*visit)(TElemType))
/*对每个结点的元素域data调用函数visit进行访问 */
{
   Stack S;   InitStack(S);
   BiTree p = T;
   // 先序访问根节点，遍历左节点 ，左节点入栈
   // StackEmpty(Stack S);S为空返回true反之false;
   // 当栈不空或 p非空时
   while(!StackEmpty(S) || p!=NULL){
     while(p!=NULL){
        visit(p->data);
        Push(S,p);
        p = p->lchild;
     }
     if(!StackEmpty(S)){
        Pop(S,p); // 执行完 p指向S出栈的元素
        p = p->rchild;
     }
   }
}


2.不使用栈，使用三叉链表的非递归先序遍历算法
/**********  
三叉链表类型定义：  
typedef struct TriTNode {  
	TElemType data;  
	struct TriTNode *parent, *lchild, *rchild;  
} TriTNode, *TriTree;  
**********/  
void PreOrder(BiTree T, void (*visit)(TElemType)){
    TriTree p, pr;
    if(T!=NULL){
        p = T;
        while(p!=NULL){
            visit(p->data);//输出当前的结点
            if(p->lchild!=NULL){
                p = p->lchild;//若有左孩子，继续访问
            }
            else if(p->rchild!=NULL){
                p = p->rchild;//若有右孩子，继续访问
            }
            else{
              //沿双亲指针链查找，找到第一个由右孩子的p结点
              //找不到则结束
                do{
                    pr = p;
                    p = p->parent;
                }while(p!=NULL&&(p->rchild==pr||NULL==p->rchild)) //p有右孩子但不是pr，结束循环
            	if(p) p = p->rchild;//找到后，p指向右孩子结点
            }
        }
    }
}

中序遍历
递归遍历
Status InOrderTraverse(BiTree T,Status(*visit)(TElemType e)){
   if(NULL == T) return OK;
   if(ERROR == InOrderTraverse(T->lchild,visit))
       return ERROR; //递归遍历T的左子树
   if(ERROR == visit(T->data))
       return ERROR; //访问结点的数据域
   return InOrderTraverse(T->rchild,visit);//递归遍历T的右子树
    
}

非递归遍历
1.使用栈的非递归中序遍历算法
/**********
二叉链表类型定义：
typedef struct BiTNode {
  TElemType  data;
  struct BiTNode  *lchild,*rchild;
} BiTNode, *BiTree;
栈类型Stack的相关定义：
typedef BiTree SElemType;   	      // 栈的元素类型
Status InitStack(Stack &S); 	      // 初始化栈
Status StackEmpty(Stack S); 	      // 判栈空
Status Push(Stack &S, SElemType e);	  // 进栈
Status Pop(Stack &S, SElemType &e);   // 出栈 
Status GetTop(Stack S, SElemType &e); // 取栈顶元素
**********/
BiTNode *GoFarLeft(BiTree T,Stack &S){
    //从T结点出发，沿左分支走到底，沿途结点的指针入栈S，返回左上结点的指针
    if(!T) return NULL;
    while(T->lchild!=NULL){
        Push(S,T);
        T = T->lchild;
    }
    return T;
} 
void InOrderTraverse(BiTree T,void(*visit)(TElemType e)){
    Stack S;   InitStack(S);
    BiTree p；
    p = GoFarLeft(T, S);//找到最左下的结点，并将沿途结点的指针入栈S
    while(p!=NULL){
        visit(p->data);//访问结点
        if(p->rchild!=NULL){
            //令p指向其右孩子为根的子树的最左下结点
            p = GoFarLeft(p->rchild, S);
        }
        else if(!StackEmpty(S)){
            //栈不空时退栈
            Pop(S,p);
        }
        else p = NULL;//栈空表明遍历结束
    }
}


2.不使用栈，使用三叉链表的非递归中序遍历算法
/**********  
三叉链表类型定义：  
typedef struct TriTNode {  
	TElemType data;  
	struct TriTNode *parent, *lchild, *rchild;  
} TriTNode, *TriTree;  
**********/  
void InOrder(TriTree PT, void (*visit)(TElemType)){
	TriTree p=PT, pr;  
	while(NULL != p) {
        if (p->lchild != NULL) {  
            p = p->lchild;   //寻找最左下结点
        }  
        else {  
            visit(p->data);
            //当前节点左子树为空，但右子树不一定为空，
            //所以该节点可能是这个子树的根节点，要先访问，
            //如果有右节点，才能在右节点之前访问
            if (p->rchild != NULL) {  
                //若有右子树，转到该子树，继续寻找最左下结点
                p =p->rchild;
            }
            else { 
                //执行到这里
                //p 要不是最左下节点，要不是没有孩子的右节点
                //其实也就是叶子节点
                pr = p;    //否则返回其父亲
                p = p->parent;  
                while (p != NULL && (p->lchild != pr || NULL == p->rchild))//若其不是从左子树回溯来的，或左结点的父亲并没有右孩子 
                {
                    if (p->lchild == pr) {//若最左结点的父亲并没有右孩子         
                    	visit(p->data);//直接访问父亲
                    }
                    pr = p;  //父亲已被访问，故返回上一级
                    p = p->parent;  
                //该while循环沿双亲链一直查找，若无右孩子则访问
                //直至找到第一个有右孩子的结点为止
                //（但不访问该结点，留给下步if语句访问
                }
                if (NULL != p) {
                 //访问父亲，并转到右孩子
                 //（经上步while处理，可以确定此时p有右孩子）
                    visit(p->data);
                    p = p->rchild;
                }
            }
        }
    }
}

后序遍历
递归遍历
Status PostOrderTraverse(BiTree T,Status(*visit)(TElemType e)){
   if(NULL == T) return OK;
   if(ERROR == PostOrderTraverse(T->lchild,visit))
       return ERROR; //递归遍历T的左子树
   if(ERROR == PostOrderTraverse(T->rchild,visit))
       return ERROR; //递归遍历T的右子树
   return visit(T->data);//访问结点的数据域
    
}

非递归遍历
1.使用栈的非递归后序遍历算法
/**********
二叉链表类型定义：
typedef struct BiTNode {
  TElemType  data;
  struct BiTNode  *lchild,*rchild;
} BiTNode, *BiTree;
为分辨后序遍历时两次进栈的不同返回点，需在指针进栈时同时将一个标志进栈
typedef struct {
  struct BiTNode *ptr; // 二叉树结点的指针类型
  int  tag; 		   // 标志 值为 0 或 1
} SElemType;    	   // 栈的元素类型
栈类型Stack的相关定义：
typedef BiTree SElemType;   	      // 栈的元素类型
Status InitStack(Stack &S); 	      // 初始化栈
Status StackEmpty(Stack S); 	      // 判栈空
Status Push(Stack &S, SElemType e);	  // 进栈
Status Pop(Stack &S, SElemType &e);   // 出栈 
Status GetTop(Stack S, SElemType &e); // 取栈顶元素
**********/
void PostOrder(BiTree T, void (*visit)(TElemType))
/* 使用栈，非递归后序遍历二叉树T，     */
/* 对每个结点的元素域data调用函数visit */
{
    Stack S; InitStack(S); 
    SElemType e; BiTree p=T;
    e.tag=0; 
    while((!StackEmpty(S)||p==T)&&T!=NULL){
        while(p){// 这个小 while循环的目的是先遍历每个子树的左节点到底，并将沿途的左节点入栈
            e.ptr=p;
            e.tag=0;
            Push(S,e); // 入栈
            p=p->lchild;                        
        }// 小while结束，此时的栈顶元素也就是要访问的起始节点      
        if(!StackEmpty(S)){  // tag==1，e为第二次出现在栈顶
            Pop(S,e); // 取出栈顶元素，并返回给e,e指向出栈元素，方便下面的tag值判断
            if(e.tag == 1)  {
                p=e.ptr;
                visit(p->data);// 访问该结点 
                p = NULL;
            }
            else  {                
                p=e.ptr;
                if(p->rchild){  // 如果存在右子树，设tag == 1
                    e.tag=1;
                    Push(S,e); // 重新入栈，它是根节点，留着等下再访问
                    p=p->rchild;  // 使 p指向右子树
                }
                else{//没有右子树 ，直接访问该节点
                    p=e.ptr;
                    visit(p->data);
                    p = NULL;
                }
            }
        }
        else{//栈空则 p为NULL
            p=NULL;
        }
    }//大while结束        
}


2.不使用栈，使用三叉链表的非递归后序遍历算法
/**********  
在三叉链表的结点中增设一个标志域  (mark取值0,1或2)以区分遍历过程中到达该结点时应继续向左或向右或访问该结点
带标志域的三叉链表类型定义：  
typedef struct TriTNode {  
	TElemType data;  
	struct TriTNode *lchild, *rchild, *parent;  
	int mark; // 标志域  
} TriTNode, *TriTree;  
**********/  
void PostOrder(TriTree T, void (*visit)(TElemType))  
/* 不使用栈，非递归后序遍历二叉树T， */  
/* 对每个结点的元素域data调用函数visit */  
{  //mark ==  0 向左访问，1 访问自身，2 向右访问  
    TriTree p= T, pr;  
    if(p==NULL) return ; 
    while(true){  
        while(p!=NULL&&p->mark!=1){  
            if(p->rchild!=NULL) //若有右孩子  
                p->mark=2;  
            else p->mark=1;  
            pr=p; 
            p=p->lchild;  
        }  
        p=pr; // p为最左下节点，可能有右孩子
        pr=pr->parent;  
        if(p->mark==2)  { // p有右孩子
            p->mark=1; // p访问完右边后下次要访问自己 
            p=p->rchild;
        }  
        else{  
            visit(p->data); // 访问
            p->mark=1;  
        }  
        if(p->data==T->data)  break;  
    }  
}

层次遍历
层次遍历是按二叉树的层次从小到大且每层从左到右的顺序依次访问结点
对于顺序存储结构的二叉树，其结点在数组中的顺序下标序列与层次遍历的访问顺序一致，因此可直接根据数组得到层次遍历的结果。
对于链式存储结构的二叉树，难以获得结点的同一层的下一层结点，从层末结点也难以得到下一层的层首结点。所以可使用一个辅助队列存储当前层被访问过的结点。
使用队列的非递归遍历
算法如下：
/**********
二叉链表类型定义：
typedef struct BiTNode {
  TElemType  data;
  struct BiTNode  *lchild,*rchild;
} BiTNode, *BiTree;
**********/
void LevelOrderTraverse(BiTree T,Status(*visit)(TEleType e)){
    if(T!=NULL){
        Queue Q; 	InitQueue(Q);
        BiTree p = T; //初始化
        visit(p->data); //访问根节点
        EnQueue(Q,p); //并将根节点入队
    }
    while(OK==DeQueue(Q,p))//当队非空时重复执行出队操作
    {
        if(p->lchild!=NULL)//访问左孩子并入队
        {
        	visit(p->lchild->data);
            EnQueue(Q,p->lchild);
        }
        if(p->rchild!=NULL)//访问右孩子并入队
        {
            visit(p->rchild->data);
            EnQueue(Q,p->rchild);
        }
    }
}

遍历的应用
求二叉树深度
利用后序遍历框架递归求左、右子树深度，然后取两者的较大值加 1（根节点）作为深度值返回。代码如下：
int BiTreeDepth(BiTree T){
    int depthLeft,depthRight;
    if(NULL==T) return 0; //二叉树深度为0
    else{
        depthLeft = BiTreeDepth(T->lchild);
        depthRight = BiTreeDepth(T->rchild);
        return 1+((depthLeft>depthRight)?depthLeft:depthRight);
    }
}

叶子节点计数
利用先序遍历框架递归实现，算法如下：
void CountLeaf(BiTree T, int &count){
    if(T!=NULL){
        if(NULL == T->lchild && NULL == T->rchild){
            count++;  // 对叶子结点计数
        }
        CountLeaf(T->lchild, count); // 对左子树递归计数
        CountLeaf(T->rchild, count); // 对右子树递归计数
    }
}

销毁二叉树
代码如下：
void DestroyBiTree(BiTree &T){
    if(T!=NULL){
        DestroyBiTree(T->lchild);// 递归销毁左子树
        DestroyBiTree(T->rchild);// 递归销毁右子树
        free(T);				 // 释放根节点
    }
}

删除指定元素结点的子树
代码如下：
void ReleaseX(BiTree &T, char x)
/* 对于二叉树T中每一个元素值为x的结点， */
/* 删去以它为根的子树，并释放相应的空间 */
{
    if(!T) return ;
    ReleaseX(T->lchild,x);
    ReleaseX(T->rchild,x);
    if(T->data == x) free(T);
}

复制二叉树
代码如下：
void CopyBiTree(BiTree T, BiTree &TT)
/* 递归复制二叉树T得到TT */
{
   TT = (BiTree)malloc(sizeof(BiTNode));
   if(T){
        TT->data = T->data;
        TT->lchild = T->lchild;
        TT->rchild = T->rchild;
        if(T->lchild) CopyBiTree(T->lchild,TT->lchild);
        if(T->rchild)CopyBiTree(T->rchild,TT->rchild);
   }
   else  free(TT);
}

二叉树递归遍历与非递归遍历


二叉树递归遍历与非递归遍历
引言
递归式遍历
前序遍历
中序遍历
后序遍历

非递归式遍历
前序遍历
中序遍历
后序遍历

一种更简单的非递归式遍历
前序遍历
中序遍历
后序遍历

总结





引言

由于二叉树是由递归定义的一种数据结构，因此递归式遍历也就是最符直觉的一种遍历方式。此外，由于递归的简洁性以及三种递归的高度统一，因此递归式遍历也是容易理解以及最简单好记的方式。然而，递归也会有其缺点，例如当一颗二叉树的深度很深的适合，采用递归的方式便有可能引起segment fault。因此，在必要的时候也需要将二叉树的遍历写成非递归的形式。

首先我们需要生成一棵树，来进行遍历以及测试，树的结构如下所示



树结构节点定义如下：



struct TreeNode
{
    int val;
    TreeNode * left; //左子树
    TreeNode * right; //右子树
    TreeNode(int x):val(x),left(NULL),right(NULL)
    {
    }
};




递归式遍历

树结构本身采用递归式定义，因此采用递归方式遍历也很直观和容易理解，各种遍历方式c++代码如下



前序遍历

先序遍历按照根节点->左子树->右子树的顺序进行遍历，首先我们先去方位其根节点，如果其存在左子树，便转向左子树遍历，遍历完左子树后，如果存在右子树，便转向右子树遍历，因此其代码如下



void Preorder_Recursive(TreeNode * root)
{
    if(!root) //如果遇到空树或到达叶节点的孩子(NULL)
    {
        return;
    }

    cout << root->val <<" "; //操作根节点

    if(root->left) 
    {
        Preorder_Recursive(root->left); //转向左子树
    }
    if(root->right)
    {
         Preorder_Recursive(root->right); //转向右子树
    }
}


调用上述函数的输出结果为：



Preorder_Recursive 1 2 4 5 6 8 9 7 3 



中序遍历

中序遍历是按照左子树->根节点->右子树的顺序遍历二叉树，因此其代码如下:



void Inorder_Recursive(TreeNode * root)
{
    if(!root) //如果遇到空树或到达叶节点的孩子(NULL)
    {
         return;
    }

    if(root->left)
    {
        Inorder_Recursive(root->left); //转向左子树
    }

    cout << root->val << " "; //操作根节点

    if(root->right)
    {
         Inorder_Recursive(root->right); //转向右子树
    }
}


输出结果为：



Inorder_Recursive 4 2 6 8 9 5 7 1 3 



后序遍历

后序遍历按照左子树->右子树->根节点的顺序进行遍历，因此其代码如下:



void Postorder_Recursive(TreeNode * root)
{
    if(!root) //如果遇到空树或到达叶节点的孩子(NULL)
    {
         return ;
    }

    if(root->left)
    {
        Postorder_Recursive(root->left); //转向左子树
    }
    if(root->right)
    {
         Postorder_Recursive(root->right); //转向右子树
    }

    cout << root->val << " "; //操作根节点
}


调用上述函数得到后序遍历序列为：



Postorder_Recursive 4 9 8 6 7 5 2 3 1 



非递归式遍历



前序遍历

根据上述前序遍历的递归式代码我们将其改造成迭代式算法。 

首先，我们观察下图所示的先序遍历的递归式代码的节点访问顺序，



前序遍历首先从根节点出发，一路向左，一直访问到最左边的节点，(图中的4号节点)，如箭头1 2 所示。而后，转向其兄弟节点(也就是2号节点的右子树)，继续重复如上过程。当访问完某个节点的右子树时（比如说8），即应当找到其某个双亲节点(比如说5)的还未访问的右子树继续访问。

如上，我们可以利用自己维护的栈结构实现算法如下： 

1. 建立一指针root，令其指向二叉树的根节点 

2. 如果栈为空则返回，不为空则循根节点->左子树的顺序一路向左访问节点并入栈 

3. 当到达最左边节点时，栈中最上方元素出栈 

4. 如果出栈元素有右子树，则令root指向它，并重复2、3步 

5. 如果出栈元素无右子树，则继续出栈元素并重复4、 5步

将上述算法兑换为代码为：



void Preorder_Iterative(TreeNode * root)
{
     if(!root)
     {
         return;
     }

     stack<TreeNode*> s;

     while(root)
     {
          cout << root->val << " ";

          if(root->left)
          {
              s.push(root);
              root = root->left;
          }
          else if (root->right)
          {
               root = root->right;
          }
          else
          {
              while(!root->right && !s.empty())
              {
                  root = s.top();
                  s.pop();
              }
              root = root->right;
          }
     }

}

调用上述程序，得到先序遍历序列为



Preorder_iterative 1 2 4 5 6 8 9 7 3  



中序遍历

同样，沿用刚才的习惯，首先画出中序遍历的节点访问轨迹



从上面的图中可以发现，中序遍历是从4号节点，也就是从最左边的节点开始访问。因此，我们先找到这棵树的最左边的节点进行访问。然后访问其双亲节点(2号节点)，再次访问双亲节点的右子树的最左边的节点，不断重复上述步骤即可遍历完一棵二叉树。


  
如果一个节点没有左子树，那么最左边的节点就是它自己，比如6、8、9号节点


根据以上描述，总结算法大体如下：

设立指针root,并指向二叉树的根节点
找到root最左边的节点，并将沿路节点入栈
元素出栈并令root指向它，访问之
如果root有右子树，令root指向它，算法回到2
如果root没有右子树，重复3、4、5
将其兑换为代码如下：



void Inorder_Iterative(TreeNode * root)
{
    if(!root)
    {
        return;
    }

    stack<TreeNode *> s;

    while(root)
    {
        while(root->left) //找到最左边的节点
        {
            s.push(root);
            root = root->left;
        }

        cout << root->val << " "; //访问之

        while(!root->right && !s.empty())
        {
             root = s.top();
             s.pop();
             cout << root->val << " ";
        }

        root = root->right;
    }
}


运行后得到中序遍历序列：



Inorder_Iterative 4 2 6 8 9 5 7 1 3 



后序遍历

后续遍历的迭代式写法是三种遍历里面最难的一种，不过按照我们上面的方法进行分析依然能够写出其算法。

首先我们画出后续遍历的访问轨迹图：



可以看出，其跟中序访问的起点都是一样的，都是首先找到最左边的节点并访问之。在一路向左找的过程中，将沿途经过节点都放入栈中。然后，在其双亲节点不出栈的情况下转到其兄弟节点（双亲节点的右子树），并继续找到最左边节点访问，转到其兄弟节点，……直到访问完最下层的右子树(如9号节点)，才开始栈中元素退栈并访问。

但是这里会出现一个问题就是比如说将5号节点从栈中退出来时如果不去转向它的右子树(7号节点)访问，那么它的右子树就会访问不到，如果转向了的话，那么8号节点退栈时就会再次转向其右子树(9号节点)进行访问。显然9号节点已经是被访问过了的。

因此，我们这里可以对栈中元素做一标记，当已经经由它转向右子树了的标记为false,当这样的节点位于栈顶时，只需直接退栈并访问即可。对于未经它转向右子树的默认标记问true,当这种节点位于栈，不能直接退栈，而是要经由它转向它的右子树并将其标记为false,当它再次位于栈顶时，才可直接退栈并访问。 

因此，对上面所说总结大体如下

设立指针root，指向二叉树根节点
一路向左走，走到最左边节点，并将沿途节点压人栈中，且标记为true
访问栈顶节点
如果栈顶节点标记为true,将其标记为false,令root指向其右子树
如果栈顶节点标记为false,将其出栈并访问之
兑换为代码如下：



struct TreeNodeWithMark
{
    TreeNode * node;
    bool isFirst;
    TreeNodeWithMark(TreeNode * p):node(p),isFirst(true)
    {
    }
};

void Lastorder_Iterative(TreeNode * root)
{
     if(!root)
     {
         return;
     }

     TreeNodeWithMark * temp = NULL;
     stack<TreeNodeWithMark *> s;

     while(root || !s.empty())
     {
         //找到最左边节点
          while(root)
          {
              s.push(new TreeNodeWithMark(root));
              root = root->left;
          }

          if(!s.empty())
          {
               temp = s.top(); // 访问栈顶元素
               if(temp->isFirst) //还未经其转到过右子树
               {
                   temp->isFirst = false;
                   root = temp->node->right;
               }
               else //已经经过其转到过右子树
               {
                    s.pop();
                    cout << temp->node->val << " ";
                    root = NULL;
               }
          }
     }
}


调用上述代码，输出后序遍历序列：



Lastorder_Iterative 4 9 8 6 7 5 2 3 1 



一种更简单的非递归式遍历

迭代式的二叉树遍历虽然提高了程序的鲁棒性但是却不容易理解。即使已经弄明白了算法的思想但是手生的人想要快速写出这三种算法也应该不是一件容易的事情。

因此，下面将把三种迭代式算法作一统一，使其更加易记易理解。



前序遍历

先看这样一个先序遍历的迭代式遍历版本:



void Preorder_Iterative_easy(TreeNode * root)
{
    if(!root)
    {
         return;
    }

    stack<TreeNode*> s;
    s.push(root);

    while(!s.empty())
    {
        root = s.top();
        s.pop();

         cout << root->val << " ";

         if(root->right)
         {
             s.push(root->right);
         }
         if(root->left)
         {
             s.push(root->left);
         }
    }
}


执行输出为：



Preorder_Iterative_easy 1 2 4 5 6 8 9 7 3 

在这个算法中，通过root指针将其左子树以及右子树按先序遍历的倒序放入栈中，这样就可以按照先序遍历的顺序进行出栈并遍历。

基于这种想法，我们可以将中序遍历和后续遍历写成类似的形式，这样，三个算法之间唯一变化的就是root指针以及其左右子树的入栈顺序其余部分则可以保持不变。下面将介绍这种形式的中序遍历和后续遍历算法。



中序遍历

在上述形式的中序遍历以及后序遍历算法中，root指针在第一次出栈时不能对其进行操作(否则就会变成先序遍历了)，因此，root指针还需要进行第二次入栈操作才能使其本身以及其左右子树在栈中形成正确的顺序并在第二次出栈时进行操作。因此，可以借鉴上面的迭代式后序遍历算法的做法，设置一标识位进行判断。

想清楚了做法，我们开始写代码：



void Inorder_Iterative_easy(TreeNode * root)
{
    if(!root)
    {
        return;
    }

    stack<TreeNodeWithMark*> s;
    s.push(new TreeNodeWithMark(root));
    TreeNodeWithMark * curr;

    while(!s.empty())
    {
         curr = s.top();
         root = curr->node;
         s.pop();

         if(curr->isFirst)
         {
             curr->isFirst = false;

             if(root->right)
             {
                  s.push(new TreeNodeWithMark(root->right));
             }

             s.push(curr);

             if(root->left)
             {
                 s.push(new TreeNodeWithMark(root->left));
             }
         }
         else
         {
             cout << root->val << " ";
         }
    }
}


执行输出：



Inorder_Iterative_easy 4 2 6 8 9 5 7 1 3



后序遍历

有了上面的遍历算法，再写后序遍历真的是简单无比：



void Lastorder_Iterative_easy(TreeNode * root)
{
    if(!root)
    {
        return;
    }

    stack<TreeNodeWithMark*> s;
    s.push(new TreeNodeWithMark(root));
    TreeNodeWithMark * curr;

    while(!s.empty())
    {
         curr = s.top();
         root = curr->node;
         s.pop();

         if(curr->isFirst)
         {
             curr->isFirst = false;

             s.push(curr);

             if(root->right)
             {
                  s.push(new TreeNodeWithMark(root->right));
             }

             if(root->left)
             {
                 s.push(new TreeNodeWithMark(root->left));
             }
         }
         else
         {
             cout << root->val << " ";
         }
    }
}


执行输出：



Lastorder_Iterative_easy 4 9 8 6 7 5 2 3 1 

可以看出，这次三个算法的唯一不同就是s.push(curr);这条语句的位置。

这次，这三个算法的不同只是根节点的入栈顺序的不同，相信理解了其中的一个算法，其余的两个算法也能够很快速的写出。

不过，这种算法也有它的缺点，那就是额外多占用了O(n)的空间。

总结

综上所述，三种便利算法各有利弊。

递归式算法高度同一，最为简洁也最好理解，但是当二叉树的高度很大时往往会引起递归深度过深从而引起程序异常。

一般的迭代式算法不够简洁也不够统一，因此也不好理解，但是却换来了最好的性能优势。

最后的迭代式算法也对三种便利方式进行了统一，比一般的迭代式算法简洁也比一般的迭代式算法好理解，但是却损失了一定的性能。

总之，三种遍历方式没有绝对的谁好谁坏，到底使用哪种还是要看具体的应用场景。

本文到此结束，作者水平有限（还是个小菜鸟），算法也未经过更多样例测试验证，如若存在错误，欢迎指正。大家相互学习，共同提高:-D

学而不思则罔，思而不学则殆
【数据结构】二叉树遍历（递归遍历和非递归遍历）
二叉树
递归遍历
递归前序遍历
递归中序遍历
递归后序遍历
非递归遍历
前序遍历
第一种解法
第二种解法
中序遍历
思路
图解算法过程
算法
后续遍历
算法思想
算法图解
算法
层次遍历
二叉树相关学习的网站


二叉树
定义：每个节点最多有两个子树的数成为二叉树
递归遍历
public class TreeNode {
    TreeNode left;
    TreeNode right;
    char values;

    public TreeNode(char values) {
        this.values = values;
    }
}

递归前序遍历
    static void preOrder(TreeNode r) {
        if (r != null) {
            System.out.print(r.values);
            preOrder(r.left);
            preOrder(r.right);
        }
    }

递归中序遍历
    static void InOrder(TreeNode r) {
        if (r != null) {
            InOrder(r.left);
            System.out.print(r.values);
            InOrder(r.right);
        }
    }

递归后序遍历
    static void PostOrder(TreeNode r) {
        if (r != null) {
            PostOrder(r.left);
            PostOrder(r.right);
            System.out.print(r.values);
        }
    }

三种递归遍历中，递归遍历左子树和右子树的顺序时固定的，只是访问根节点的顺序不同。不管采取那种遍历方法，每个节点都访问一次且只访问一次。因此时间复杂度为$O(n)$

在递归遍历工作栈的栈深恰好是树的深度，所以在最坏的情况下，（比如单边树），二叉树的有n个节点且深度为n的单支树，遍历算法的空间复杂度为:$O(n)$
非递归遍历
前序遍历
使用栈作为辅助工具。
第一种解法
    static void nonRecursivePre(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        if (root == null) {
            System.out.println("root == null");
            return;
        }
        stack.push(root);
        while (!stack.empty()){
            TreeNode treeNode = stack.pop();
            //访问节点
            System.out.print(treeNode.values);
            //右子树入栈
            if (treeNode.right != null){
                stack.push(treeNode.right);
            }
            //左子树入栈
            if (treeNode.left != null){
                stack.push(treeNode.left);
            }
        }
        System.out.println();
    }

第二种解法
    static void nonRecursivePre2(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        TreeNode treeNode = root;
        while (treeNode != null || !stack.empty()) { //栈不为空或者treeNode不为null时循环
            if (treeNode != null) {                  //一路向左走到底
                System.out.print(treeNode.values);   //入栈前访问
                stack.push(treeNode);                //入栈
                treeNode = treeNode.left;            //左孩子不为空，一直向左走
            } else {                                 //出栈，并转向出栈节点的右孩子
                treeNode = stack.pop();              //出栈
                treeNode = treeNode.right;           //向右子树走，treeNode指向为当前节点的右孩子
            }
        }
        System.out.println();
    }

中序遍历
思路


沿着跟的左孩子，依次入栈，直到左孩子为空，说明已经找到可以输出的节点
栈顶元素出栈继续访问：若其右孩子为空，继续执行2,其右孩子不为空，则将右子树执行1


图解算法过程
开始时二叉树如下：栈内数据为空



沿着这左子树入栈，一直到D，此时栈顶为D,D的左孩子为null.



D出栈，并访问D.treeNode 指向D的右孩子



由于D右孩子为空，treeNode 为空，那么就继续执行2，出栈操作。此时出栈B.访问B.treeNode 指向B的右孩子E



下一次循环，由于treeNode 指向E,所以E入栈，treeNode 指向E的左孩子



下一次循环：E的左孩子为空，所以treeNode 为空，所以E出栈，并访问，treeNode 指向E的右孩子



下一次循环的时候，treeNode 指向E的右孩子为空，所有继续出栈，此时A出栈并访问。treeNode 指向A的右孩子C



下一次循环treeNode 指向A的右孩子C，所以C入栈，treeNode 指向C的左孩子



下一次循环，由于treeNode 指向C的左孩子为空，所以C出栈，并访问C,treeNode 再指向C的右孩子



下一次循环，treeNode 再指向C的右孩子的为空，且栈也为空，退出整个遍历，结束。

下面是算法。
算法
    static void nonRecursiveMiddle(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        TreeNode treeNode = root;
        while (treeNode != null || !stack.empty()) { //栈不为空或者treeNode不为null时循环
            if (treeNode != null) {                  //一路向左走到底
                stack.push(treeNode);                //入栈
                treeNode = treeNode.left;            //左孩子不为空，一直向左走
            } else {                                 //出栈，并转向出栈节点的右孩子
                treeNode = stack.pop();              //出栈
                System.out.print(treeNode.values);   //访问出栈元素
                treeNode = treeNode.right;           //向右子树走，treeNode指向为当前节点的右孩子
            }
        }
        System.out.println();
    }

后续遍历
算法思想

后续非递归遍历二叉树是先访问左子树，在访问右子树，最后访问根节点。

1.沿着根的左孩子，依次入队，直到左孩子为空

2.读栈顶元素：若其右孩子不空，且未被访问过，将右子树转执行1；否则栈顶元素出栈并访问。

结合一个例子来分析：
算法图解
初始是如下：



1.沿着根的左孩子，依次入队，直到左孩子为空，此时栈内元素为ABD.



2.此时栈顶元素D右孩子为空，出栈并访问


3.此时栈顶元素是B,B的右孩子不空且未被访问过，E入栈



4.E的左孩子为空，且右孩子为空。出栈并访问。



5.此时栈顶元素B的右孩子不为空，但是已经访问过，B出栈并访问。



6.A栈顶元素，A的右孩子不为空，且未被访问过，C入栈



7.栈顶C的左右孩子都为空，出栈并访问


8 栈顶A的右孩子不为空但是已被访问过，A出栈并访问。


在上出算法的第二步中，必须分清返回时是从左子树还是从右子树返回的，因此需要一个辅助指针，指向最近被访问的节点。
算法
    //非递归后序遍历
    static void nonRecursivePost(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        TreeNode treeNode = root;
        TreeNode lastVisit = null;
        while (treeNode != null || !stack.empty()) { //栈不为空或者treeNode不为null时循环
            if (treeNode != null) {                  //一路向左走到底
                stack.push(treeNode);                //入栈
                treeNode = treeNode.left;            //左孩子不为空，一直向左走
            } else {                                 //出栈，并转向出栈节点的右孩子
                treeNode = stack.peek();             //读取栈顶元素，注意不是出栈
                if (treeNode.right != null && lastVisit != treeNode.right) { //右子树存在且未被访问过
                    treeNode = treeNode.right;       //转向右子树
                    stack.push(treeNode);            //入栈
                    treeNode = treeNode.left;        //在走到最左
                } else {
                    treeNode = stack.pop();            //出栈
                    System.out.print(treeNode.values); //访问该节点
                    lastVisit = treeNode;              //记录最近访问的节点
                    treeNode = null;                   //节点访问完后,置为null
                }
            }
        }
        System.out.println();
    }

层次遍历
辅助队列。

二叉树根节点入队，然后出队访问节点，若存在左子树，左子树入队；若存在右子树，右子树入队。然后出队，…知道队列为空。
    //辅助队列
    static void levelOrder(TreeNode root) {
        ArrayDeque<TreeNode> deque = new ArrayDeque<>();
        if (root == null) {
            return;
        }
        deque.add(root);
        while (!deque.isEmpty()) {
            TreeNode treeNode = deque.pop();
            System.out.print(treeNode.values);
            if (treeNode.left != null) {
                deque.add(treeNode.left);
            }
            if (treeNode.right != null) {
                deque.add(treeNode.right);
            }
        }
        System.out.println();
    }

二叉树相关学习的网站
动画展示二叉树 https://visualgo.net/zh/bst

二叉树动画展示 http://btv.melezinek.cz/binary-search-tree.html

各种数据结构 动画总结 https://www.cs.usfca.edu/~galles/visualization/Algorithms.html

                                                                                              二叉树的非递归遍历及其递归遍历算法
 二叉树的结构定义是一个递归的定义，在树的定义中用到了树的概念。在二叉树的一些应用中，，常常需要通过遍历二叉树获取某些元素的属性。


一：递归遍历  
      1.递归先序遍历
                        /*递归先序遍历二叉树（DLR)*/
Status PreOrderTraverse(BiTree T, Status(*Visit)(TELemType e)){
	if (T){
		if (Visit(T->data)){
			if (PreOrderTraverse(T->lchild, Visit)){
				if (PreOrderTraverse(T->rchild, Visit))return OK;
			}
		}
		return ERROR;
	}
	else return OK;
}
       2.递归中序遍历
                      /*递归中序遍历二叉树*/
Status InOrderTraverse(BiTree T, Status(*Visit)(TELemType e)){
	if (T){
		if (InOrderTraverse(T->lchild, Visit)){
			if (Visit(T->data)){
				if (InOrderTraverse(T->rchild, Visit))return OK;
			}
		}
		return ERROR;
	}
	else return OK;
}
       3.递归后序遍历
   /*递归后序遍历二叉树*/
Status PosOrderTraverse(BiTree T, Status(*Visit)(TELemType e)){
	if (T){
		if (PosOrderTraverse(T->lchild, Visit)){
			if (PosOrderTraverse(T->rchild, Visit)){
				if(Visit(T->data))return OK;
			}
		}
		return ERROR;
	}
	else return OK;
}
     
二：非递归遍历（在非递归遍历中要用到栈的结构）
       1.非递归先序遍历
    /*非递归先序遍历二叉树*/
Status PreOrderTraverse1(BiTree T, Status(*Visit)(TELemType e)){
	BiTree p;
	Stack S;
	InitStack(S);
	p = T;
	while (p != NULL || !StackEmpty(S)){
		while (p != NULL){
			Visit(p->data);
			Push(S, p);
			p = p->lchild;
		}
		if (!StackEmpty(S)){
			Pop(S, p);
			p = p->rchild;
		}
	}
	return OK;
}
       2.非递归中序遍历
    /*非递归中序遍历*/
Status InOrderTraverse1(BiTree T, Status(*Visit)(TELemType e)){
	BiTree p;
	Stack S;
	InitStack(S);
	p = T;
	while (p != NULL || !StackEmpty(S)){
		while (p != NULL){
			Push(S, p);
			p = p->lchild;
		}
		if (!StackEmpty(S)){
			Pop(S, p);
			Visit(p->data);
			p = p->rchild;
		}
	}
	return OK;
}


        3.非递归后序遍历
     /*非递归后序遍历*/
Status PosOrderTraverse1(BiTree T, Status(*Visit)(TELemType e)){
	BiTree p;
	Stack S;
	InitStack(S);
	p = T;
	while (p != NULL || !StackEmpty(S)){
		while (p != NULL){
			p->isFirst = true;
			Push(S, p);
			p = p->lchild;
		}
		if (!StackEmpty(S)){
			Pop(S, p);
			if (p->isFirst == true){          //该结点p是否是第一次出现在栈顶
				p->isFirst = false;
				Push(S, p);
				p = p->rchild;
			}
			else{ 
				Visit(p->data);
				p = NULL;
			}
		}
	}
	return OK;
}