二叉树遍历（循环和递归）_二叉查找树结构使用循环遍历

递归

1.前序遍历

void preorder(BinTree *T)
{
    if(T==NULL)
        return;
    cout << T->data;
    preorder(T->left);
    preorder(T->right);
}

2.中序遍历

void inoeder(BinTree *T)
{
    if(T == NULL)
        return;
    inoeder(T->left);
    cout << T->data;
    inoeder(T->right);
}

3.后序遍历

void postorder(BinTree *T)
{
    if (T==NULL)
        return;
    postorder(T->left);
    postorder(T->right);
    cout << T->data;
}

循环

1.前序遍历 法一

void preorder(BinTree *T)
{
    //空树，直接返回
    if(T==NULL)
        return;
    //定义一个存放二叉树节点的栈结构
    stack<BinTree*>s;
    BinTree *pcur; 
    pcur = T;
    //循环遍历二叉树直到根节点为空或者栈为空
    while (pcur || !s.empty())
    {
        if (pcur)
        {
            cout << pcur->data;
            s.push(pcur);
            pcur = pcur->left;
        }else
        {
            //当根节点为空时，说明左子树已遍历完，通过取出栈顶结点，来访问根节点的右子树
            pcur = s.top();
            s.pop();
            pcur = pcur->right;
        }
    }
}

法二（自己）

void preOrder(binTree * root)
{
	if(root==NULL)
	return;
	
	stack<binTree*> stackTree;
	binTree* curTree;
	
	stackTree.push(root);
	
	while(!stackTree.empty())
	{
		curTree=stackTree.top();
		stackTree.pop();
		cout<<curTree->value;
		
		if(curTree->right!=NULL)
			stackTree.push(curTree->right);
		if(curTree->left!=NULL)
			stackTree.push(curTree->left);
	}
}

2.中序遍历

void inorder(BinTree *T)
{
    if(T == NULL)
        return;
    stack<BinTree*>s;
    BinTree *pcur;
    pcur = T;
    while (pcur || !s.empty())
    {
        if (pcur)
        {
            //根节点非空，入栈，继续遍历左子树直到根节点为空
            s.push(pcur);
            pcur = pcur->left;
        }else
        {
            //根节点为空，说明左子树已经遍历完，弹出根节点打印，通过根节点访问右子树
            pcur = s.top();
            s.pop();
            cout << pcur->data;
            pcur = pcur->right;            
        }
    }
}

3.后序遍历

法一，会改变原来的内容

void postorder2(BinTree *T)
{
    if(T == NULL)
        return;
    stack<BinTree*>s;
    s.push(T);
    BinTree *pcur;
    pcur = NULL;
    while (!s.empty())
    {
        pcur = s.top();
        if (pcur->left == NULL && pcur->right == NULL)
        {
            cout << pcur->data;
            s.pop();
        }else
        {
            //注意右孩子先入栈左孩子后入栈，这样再次循环时左孩子节点才先出栈
            if(pcur->right)
            {
                s.push(pcur->right);
                pcur->right = NULL;
            }
            if (pcur->left)
            {
                s.push(pcur->left);
                pcur->left = NULL;
            }    
        }
    }
}

法二，不用辅助栈，不改变内容

void PostOrderWithoutRecursion(BTNode* root)
{
    if (root == NULL)
        return;
    stack<btnode*> s;
    //pCur:当前访问节点，pLastVisit:上次访问节点
    BTNode* pCur, *pLastVisit;
    pCur = root;
    pLastVisit = NULL;
    //先把pCur移动到左子树最下边
    while (pCur)
    {
        s.push(pCur);
        pCur = pCur->lchild;
    }
    while (!s.empty())
    {
        //走到这里，pCur都是空，并已经遍历到左子树底端(看成扩充二叉树，则空，亦是某棵树的左孩子)
        pCur = s.top();
        s.pop();
        //一个根节点被访问的前提是：无右子树或右子树已被访问过
        if (pCur->rchild == NULL || pCur->rchild == pLastVisit)
        {
            cout << pCur->data;
            //修改最近被访问的节点
            pLastVisit = pCur;
        }
        /*这里的else语句可换成带条件的else if:
        else if (pCur->lchild == pLastVisit)//若左子树刚被访问过，则需先进入右子树(根节点需再次入栈)
        因为：上面的条件没通过就一定是下面的条件满足。仔细想想！
        */
        else
        {
            //根节点再次入栈
            s.push(pCur);
            //进入右子树，且可肯定右子树一定不为空
            pCur = pCur->rchild;
            while (pCur)
            {
                s.push(pCur);
                pCur = pCur->lchild;
            }
        }
    }
    cout << endl;
}

法三。不用辅助栈，不改变内容，推荐

void beh_traverse(BTree pTree)  
{  
    PSTACK stack = create_stack();  //创建一个空栈  
    BTree node_pop;          //用来保存出栈的节点  
    BTree pCur;              //定义指针，指向当前节点  
    BTree pPre = NULL;       //定义指针，指向上一各访问的节点  
  
    //先将树的根节点入栈  
    push_stack(stack,pTree);    
    //直到栈空时，结束循环  
    while(!is_empty(stack))  
    {  
        pCur = getTop(stack);   //当前节点置为栈顶节点  
        if((pCur->pLchild==NULL && pCur->pRchild==NULL) ||   
            (pPre!=NULL && (pCur->pLchild==pPre || pCur->pRchild==pPre)))  
        {  
            //如果当前节点没有左右孩子，或者有左孩子或有孩子，但已经被访问输出，  
            //则直接输出该节点，将其出栈，将其设为上一个访问的节点  
            printf("%c ", pCur->data);  
            pop_stack(stack,&node_pop);  
            pPre = pCur;  
        }  
        else  
        {  
            //如果不满足上面两种情况,则将其右孩子左孩子依次入栈  
            if(pCur->pRchild != NULL)  
                push_stack(stack,pCur->pRchild);  
            if(pCur->pLchild != NULL)  
                push_stack(stack,pCur->pLchild);  
        }  
    }  
}  

4.层次遍历

void leveltraversal(BinTree *T)
{
    queue<BinTree*> s;
    s.push(T);
    BinTree* pcur;
    while (!s.empty())
    {
        pcur=s.front();
        cout<<pcur->data;
        s.pop();
        if (pcur->left)
        {
            s.push(pcur->left);
        }
        if (pcur->right)
        {
            s.push(pcur->right);
        }
    }    
}

分层遍历二叉树，即从上到下按层次访问该树，每一层单独输出一行

void leveltraversal3(BinTree *T)
{
    if(T == NULL)
        return;
    queue<BinTree*>s;
    s.push(T);
    BinTree *pcur,*last,*nlast;
    last = T;
    nlast = NULL;
    while (!s.empty())
    {
        pcur = s.front();
        cout << pcur->data;
        s.pop();        
        if (pcur->left)
        {
            s.push(pcur->left);
            nlast = pcur->left;
        }
        if (pcur->right)
        {
            s.push(pcur->right);
            nlast = pcur->right;
        }
        if (last == pcur)
        {
            cout << endl;
            last = nlast;
        }            
    }
}