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

时间:2022-07-02 06:38:43

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); 
    }