遍历二叉树的代码实现

简介: 遍历二叉树的代码实现

先序遍历(根--左--右)

递归法

void PreOrder(BiTree T){
    if(T != NULL){
        visit(T);                //访问根节点
        PreOrder(T->lchild);    //递归遍历左子树
        PreOrder(T->rchild);    //递归遍历右子树
    }
}

非递归法

void PreOrder(BiTree T){
    InitStack(S);                //使用栈存储二叉树的节点
    BiTree p = T;                //p为遍历二叉树的指针
    while(p || !IsEmpty(S)){    //二叉树不为空或栈不空是继续循环
        if(p != NULL){
            vist(p)                //访问拍p
            Push(S,p);            //p节点入栈
            p = p->lchild;        //继续向左遍历
        }
        else{
            Pop(S,p);            //p出栈
            p = p->rchild;        //转向右子树遍历
        }
    }
}

中序遍历(左--根--右)

递归法

void InOrder(BiTree T){
    if(T != NULL){
        InOrder(T->lchild);        //递归遍历左子树
        visit(T);                //访问根节点
        InOrder(T->rchild);        //递归遍历右子树
    }
}

非递归法

void InOrder(BiTree T){
    InitStack(S);                //使用栈存储二叉树的节点
    BiTree p = T;                //p为遍历二叉树的指针
    while(p || !IsEmpty(S)){    //二叉树不为空或栈不空是继续循环
        if(p != NULL){
            Push(S,p);            //p节点入栈
            p = p->lchild;        //继续向左遍历
        }
        else{
            Pop(S,p);            //p出栈
            visit(p);            //访问p
            p = p->rchild;        //转向右子树遍历
        }
    }
}

后序遍历(左--右--根)

递归法

void PostOrder(BiTree T){
    if(T != NULL){
        PostOrder(T->lchild);        //递归遍历左子树
        PostOrder(T->rchild);        //递归遍历右子树
        visit(T);                    //访问根节点
    }
}

非递归法

void PostOrder(BiTree T){
    InitStack(S);                    //使用栈存储二叉树的节点
    BiTree p = T;                    //p为遍历二叉树的指针
    BiTree r = NULL;                //记录最近访问的节点
    while(p || !IsEmpty(S)){        //二叉树不为空或栈不空是继续循环
        if(p != NULL){
            Push(S,p);                //p节点入栈
            p = p->lchild;            //继续向左遍历
        }
        else{
            GetTop(S,p);            //读取栈顶节点,不出栈
            if(p->rchild && p->rchild != r){    //右子树存在,且未被访问
                p = p->rchild;
                Push(S,p);                        //p节点入栈
                p = p->lchild;                    //转左遍历
            }
            else{
                Pop(S,p);                        //p出栈
                visit(p);                        //访问p
                r = p;                            //记录最近一次访问的节点
                p = NULL;
            }
        }
    }
}

层序遍历

void LevelOrder(BiTree T){
    InitQueue(Q);                //使用队列存储二叉树节点
    BiTree p;
    EnQueue(Q,T);                //根节点入队
    while(!IsEmpty(Q)){            //队列不空继续循环
        DeQueue(Q,p);            //队头节点出队
        vist(p);                //访问队头节点
        if(p->lchild != NULL){
            EnQueue(Q,p->lchild);    //左孩子入队
        }
        if(p->rchild != NULL){
            EnQueue(Q,p->rchild);    //右孩子入队
        }
    }            
}
目录
相关文章
代码随想录Day12 二叉树 LeetCode T102二叉树的层序遍历 T226 翻转二叉树 T101 对称二叉树
代码随想录Day12 二叉树 LeetCode T102二叉树的层序遍历 T226 翻转二叉树 T101 对称二叉树
64 0
|
3月前
|
存储 算法 Java
LeetCode经典算法题:二叉树遍历(递归遍历+迭代遍历+层序遍历)以及线索二叉树java详解
LeetCode经典算法题:二叉树遍历(递归遍历+迭代遍历+层序遍历)以及线索二叉树java详解
76 0
|
5月前
|
算法 Java 索引
【算法】重建二叉树并进行后序遍历的Java实现
【算法】重建二叉树并进行后序遍历的Java实现
50 5
|
算法
代码随想录 Day11 二叉树 LeetCode T144,145,94 前中后序遍历 (递归解法)
代码随想录 Day11 二叉树 LeetCode T144,145,94 前中后序遍历 (递归解法)
47 0
|
存储
链式二叉树OJ题思路分享
链式二叉树这一个板块的考题还是比较多的,这里我给大家分享几道很经典的OJ题,仅供参考! 分别是 1. 单值二叉树力扣965题----- 2. 检查两棵树是否相同力扣100题 ----- 3. 对称二叉树 力扣101题
|
算法
力扣704二分查找:思路分析+代码实现(递归与非递归)
力扣704二分查找:思路分析+代码实现(递归与非递归)
130 0
|
C++
剑指Offer - 面试题7:重构二叉树 (力扣 - 105、从前序与中序遍历序列构造二叉树)
剑指Offer - 面试题7:重构二叉树 (力扣 - 105、从前序与中序遍历序列构造二叉树)
61 0
|
算法 C++
【栈的应用】二叉树非递归中序遍历思想解析及代码实现
【栈的应用】二叉树非递归中序遍历思想解析及代码实现
194 0
【栈的应用】二叉树非递归中序遍历思想解析及代码实现
二叉树的前序遍历--非递归解法(简单难度)
二叉树的前序遍历--非递归解法(简单难度)
90 0
二叉树的前序遍历--非递归解法(简单难度)
二叉树的三种非递归遍历方式
二叉树的三种非递归遍历方式