程序员社区

【数据结构与算法】二叉树遍历

搜索二叉树概念

二叉树是树的特殊一种,具有如下特点:
1、每个结点最多有两颗子树,结点的度最大为2。
2、左子树和右子树是有顺序的,次序不能颠倒。
3、即使某结点只有一个子树,也要区分左右子树。

【数据结构与算法】二叉树遍历插图
搜索二叉树

递归遍历

前序遍历

基本思想:先访问根结点,再先序遍历左子树,最后再先序遍历右子树即根—左—右。

public static void preRecDisplay(TreeNode node){
        //前序遍历
        if (node!=null){
            System.out.println(node.data);
            preRecDisplay(node.leftNode);
            preRecDisplay(node.rightNode);
        }

    }

中序遍历
基本思想:先中序遍历左子树,然后再访问根结点,最后再中序遍历右子树即左—根—右。

    public static void midRecDisplay(TreeNode node){
        //中序遍历
        if (node!=null) {
            midRecDisplay(node.leftNode);
            System.out.println(node.data);
            midRecDisplay(node.rightNode);
        }
    }

后序遍历
基本思想:先后序遍历左子树,然后再后序遍历右子树,最后再访问根结点即左—右—根。

    public static void postRecDisplay(TreeNode node){
        //后序遍历
        if (node!=null) {
            postRecDisplay(node.leftNode);
            postRecDisplay(node.rightNode);
            System.out.println(node.data);
        }
    }

    public static void main(String[] args){
        int datas[] = {1,2,3,4,5,6,7,8,9};
        Tree tree = new Tree(datas);
        postRecDisplay(tree.root);
    }

非递归遍历

前序遍历

对于任一结点p:

a. 访问结点p,并将结点p入栈;

b. 判断结点p的左孩子是否为空,若为空,则取栈顶结点并进行出栈操作,并将栈顶结点的右孩子置为当前的结点p,循环置a;若不为空,则将p的左孩子置为当前结点p;

c. 直到p为空,并且栈为空,则遍历结束。

 public static void preDisplay(TreeNode node){
        //前序遍历
        Stack<TreeNode> stack = new Stack<>();
        while (true){
            while (node!=null){
                //输出就是遍历的过程,前序遍历先输出当前节点
                System.out.println(node.data);
                //最后输出右节点,那就用stack来保存它
                stack.push(node);
                //当前节点置为左节点,下次循环就可以输出左节点
                node=node.leftNode;
            }

            if (stack.isEmpty()){
                return;
            }
            //当前节点置为右节点
            node = stack.pop().rightNode;
        }


    }

中序遍历

根据中序遍历的顺序,对于任一结点,优先访问其左孩子,而左孩子结点又可以看做一个根结点,然后继续访问其左孩子结点,直到遇到左孩子结点为空的结点才停止访问,然后按相同的规则访问其右子树。其处理过程如下:

对于任一结点:

a. 若其左孩子不为空,则将p入栈,并将p的左孩子设置为当前的p,然后对当前结点再进行相同的操作;
b. 若其左孩子为空,则取栈顶元素并进行出栈操作,访问该栈顶结点,然后将当前的p置为栈顶结点的右孩子;
c. 直到p为空并且栈为空,则遍历结束。

    public static void midDisplay(TreeNode node){
        //中序遍历
        Stack<TreeNode> stack = new Stack<>();
        while (true){
            //循环截止说明当前节点没有左节点了
            while (node!=null){
                //需要先输出左节点,只能讲当前节点入栈,暂时不输出
                stack.push(node);
                //先输出左节点
                node=node.leftNode;
            }

            if (stack.isEmpty()){
                return;
            }

            node = stack.pop();
            //当前节点没有左子树了,该轮到它自己输出了
            System.out.println(node.data);
            //输出右子树的过程
            node = node.rightNode;
        }
    }

后序遍历

后序遍历的非递归实现是三种遍历方式中最难的一种。因为在后序遍历中,要保证左孩子和右孩子都已被访问,并且左孩子在右孩子之前访问才能访问根结点,这就为流程控制带来了难题。

要保证根结点在左孩子和右孩子访问之后才能访问,因此对于任一结点p,先将其入栈。若p不存在左孩子和右孩子,则可以直接访问它。当前p节点为左子树输出一次,然后重复入栈过程,当前节点p为右子树,那么他的父节点就必定不能重复的将右子树入栈。则之间循环输出即可。
当前节点p有右节点 ,需要将右节点放到stack中,重复上述过程。

    public static void postListN(TreeNode node){
        //后序遍历
        Stack<TreeNode> stack = new Stack<>();
        while (true){
            while (node!=null){
                //最后输出当前节点,所有先入栈保存
                stack.push(node);
                node=node.leftNode;
            }
            if (stack.isEmpty()){
                return;
            }
            //当前节点
            node = stack.lastElement();
            //在这里当前节点有几种情况
            //1.当前节点没有右节点,需要输出,同时输出也有几种情况
                // (1 当前节点为左子树 输出一次,然后重复入栈过程
                // (2 当前节点为右子树 当前节点已经为右子树,输出完毕,那么他的父节点就必定不能重复的将右子树入栈
            //2.当前节点有右节点  需要将右节点放到stack中
            //判断当前节点有没有右节点
            if (node.rightNode==null){
                //没右节点
                stack.pop();
                System.out.println(node.data);
                node = node.rightNode;
                //判断当前node是不是右分支
                while (stack.lastElement().rightNode==node){
                    //是右分支
                    TreeNode root = stack.pop();
                    System.out.println(root.data);
                    if (stack.isEmpty()){
                        break;
                    }
                }
            }
            //判断栈是否为空
            if (!stack.isEmpty()){
                //将当前节点置为右节点
                node=stack.lastElement().rightNode;
            }else{
                node=null;
            }
        }
    }
赞(0) 打赏
未经允许不得转载:IDEA激活码 » 【数据结构与算法】二叉树遍历

相关推荐

  • 暂无文章

一个分享Java & Python知识的社区