二叉数遍历

2020年10月19日 1 条评论 11 次阅读 0 人点赞

简介

二叉树是一种非常重要的数据结构,非常多其他数据结构都是基于二叉树的基础演变而来的。对于二叉树,有深度遍历和广度遍历,深度遍历有前序、中序以及后序三种遍历方法,广度遍历即我们寻常所说的层次遍历。由于树的定义本身就是递归定义,因此採用递归的方法去实现树的三种遍历不仅easy理解并且代码非常简洁,而对于广度遍历来说,须要其他数据结构的支撑。比方堆了。所以。对于一段代码来说,可读性有时候要比代码本身的效率要重要的多。

四种基本的遍历思想为:

前序遍历:根结点 ---> 左子树 ---> 右子树

中序遍历:左子树---> 根结点 ---> 右子树

后序遍历:左子树 ---> 右子树 ---> 根结点

下面展示各种搜索方法的递归与非递归方法

前序

public void preOrderTraverse1(TreeNode root) {  
        if (root != null) {  
            System.out.print(root.val+"  ");  
            preOrderTraverse1(root.left);  
            preOrderTraverse1(root.right);  
        }  
    }  
public void preOrderTraverse2(TreeNode root) {  
        LinkedList<TreeNode> stack = new LinkedList<>();  
        TreeNode pNode = root;  
        while (pNode != null || !stack.isEmpty()) {  
            if (pNode != null) {  
                System.out.print(pNode.val+"  ");  
                stack.push(pNode);  
                pNode = pNode.left;  
            } else { //pNode == null && !stack.isEmpty()  
                TreeNode node = stack.pop();  
                pNode = node.right;  
            }  
        }  
    }  

中序

public void inOrderTraverse1(TreeNode root) {  
        if (root != null) {  
            inOrderTraverse1(root.left);  
            System.out.print(root.val+"  ");  
            inOrderTraverse1(root.right);  
        }  
    }  
public void inOrderTraverse2(TreeNode root) {  
        LinkedList<TreeNode> stack = new LinkedList<>();  
        TreeNode pNode = root;  
        while (pNode != null || !stack.isEmpty()) {  
            if (pNode != null) {  
                stack.push(pNode);  
                pNode = pNode.left;  
            } else { //pNode == null && !stack.isEmpty()  
                TreeNode node = stack.pop();  
                System.out.print(node.val+"  ");  
                pNode = node.right;  
            }  
        }  
    }  

后序

public void postOrderTraverse1(TreeNode root) {  
        if (root != null) {  
            postOrderTraverse1(root.left);  
            postOrderTraverse1(root.right);  
            System.out.print(root.val+"  ");  
        }  
    }  
Master

Master

这个人太懒什么东西都没留下

文章评论(1)

  • Master
    Master

    测试一下

    2021年5月3日