先序遍历二叉树的递归实现与非递归实现深入解析

1、先序遍历二叉树  递归实现
思想：若二叉树为空，返回。否则
1）遍历根节点；
2）先序遍历左子树；
3）先序遍历右子树；

代码：
代码如下:
template<typename elemType>
void PreOrder(nodeType<elemType> *root) 
{ 
    if(root==NULL) 
        return ; 
    visit(root->data); // visit the data
    PreOrder(root->lchild); //递归调用，先序遍历左子树 
    PreOrder(root->rchild); //递归调用，先序遍历右子树 
} 

2、先序遍历二叉树 非递归实现
思想：二叉树的非递归先序遍历，先序遍历思想：先让根进栈，只要栈不为空，就可以做弹出操作， 每次弹出一个结点，记得把它的左右结点都进栈，记得右子树先进栈，这样可以保证右子树在栈中总处于左子树的下面。

前序遍历二叉树的非递归算法思想
建立栈 Stack；
t 指向根；
当 t 不空 或 Stack 不空时反复做：
      若 t 不空，访问t，t 入 栈；t 指向左子女；
      否则：出栈顶元素到 t 中；
      t 指向右子女；
结束
代码如下:
void PreOrder_Nonrecursive(BinaryTree T)     //先序遍历的非递归   
{ 
    if(!T) return ;   
    stack<BinaryTree> s; 
    s.push(T); 
    while(!s.empty()) 
    { 
        BinaryTree temp = s.top(); 
        visit(temp->data); 
        s.pop(); 
        if(temp->rchild) 
            s.push(temp->rchild); 
        if(temp->lchild) 
            s.push(temp->lchild); 
    } 
} 

您可能感兴趣的文章:平衡二叉树AVL操作模板平衡二叉树的实现实例二叉树的非递归后序遍历算法实例详解二叉树先序遍历的非递归算法具体实现二叉树先根（先序）遍历的改进c语言版本二叉树基本操作示例(先序 递归 非递归)python二叉树遍历的实现方法python二叉树的实现实例C++二叉树结构的建立与基本操作二叉树遍历 非递归 C++实现代码PHP Class&Object -- 解析PHP实现二叉树PHP Class&Object -- PHP 自排序二叉树的深入解析如何在二叉树中找出和为某一值的所有路径探讨:C++实现链式二叉树(用非递归方式先序,中序,后序遍历二叉树)深入理解二叉树的非递归遍历深入遍历二叉树的各种操作详解（非递归遍历）深入二叉树两个结点的最低共同父结点的详解二叉树前序遍历的非递归算法

二叉树 先序遍历 遍历 递归