美文网首页
数据结构-二叉树的遍历

数据结构-二叉树的遍历

作者: 鼬殿 | 来源:发表于2020-05-25 19:15 被阅读0次

遍历是数据结构中的常见操作
把所有元素都访问一遍

线性数据结构的遍历比较简单

  • 正序遍历
  • 逆序遍历

根据结点访问顺序的不同，二叉树的常见遍历方式有4种

  • 前序遍历（Preorder Traversal）
  • 中序遍历（Inorder Traversal）
  • 后序遍历（Postorder Traversal）
  • 层序遍历（Level Order Traversal）

前序遍历（Preorder Traversal）

访问顺序
根节点、前序遍历左子树、前序遍历右子树
7、4、2、1、3、5、9、8、11、10、12

    /**
     * 前序遍历
     */
    public void preorderTraversal() {
        preorderTraversal(root);
    }
    
    private void preorderTraversal(Node<E> node) {
        if (node == null) return;
        System.out.println(node.element);
        preorderTraversal(node.left);
        preorderTraversal(node.right);
    }

中序遍历（Inorder Traversal）

访问顺序

  • 中序遍历左子树、根节点、中序遍历右子树
    1、2、3、4、5、7、8、9、10、11、12


  • 中序遍历右子树、根节点、中序遍历左子树
    12、11、10、9、8 、7、5、4、3、2、1

二叉搜索树的中序遍历结果是升序或者降序的

    /**
     * 中序遍历
     */
    public void inorderTraversal() {
        inorderTraversal(root);
    }
    
    private void inorderTraversal(Node<E> node) {
        if (node == null) return;
        inorderTraversal(node.left);
        System.out.println(node.element);
        inorderTraversal(node.right);
    }

后序遍历（Postorder Traversal）

后序遍历左子树、后序遍历右子树、根节点
1、3、2、5、4、8、10、12、11、9、7


    /**
     * 后序遍历
     */
    public void postorderTraversal() {
        postorderTraversal(root);
    }
    
    private void postorderTraversal(Node<E> node) {
        if (node == null) return;
        postorderTraversal(node.left);
        postorderTraversal(node.right);
        System.out.println(node.element);
    }

层序遍历（Level Order Traversal）

从上到下、从左到右依次访问每一个节点
7、4、9、2、5、8、11、1、3、10、12


实现思路：使用队列

  1. 将根节点入队
  2. 循环执行以下操作，直到队列为空
    将队头节点 A 出队，进行访问
    将 A 的左子节点入队
    将 A 的右子节点入队
    /**
     * 层序遍历
     */
    public void levelOrderTraversal(){
        if (root == null) return;
        Queue<Node<E>> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            Node<E> node = queue.poll();
            System.out.println(node.element);
            if (node.left != null) {
                queue.offer(node.left);
            }
            if (node.right != null) {
                queue.offer(node.right);
            }
        }
    }

遍历接口设计

    /**
     * 前序遍历
     */
    public void preorderTraversal(Visitor<E> visitor) {
        preorderTraversal(root,visitor);
    }
    
    private void preorderTraversal(Node<E> node,Visitor<E> visitor) {
        if (node == null || visitor == null) return;
        visitor.visit(node.element);
        preorderTraversal(node.left,visitor);
        preorderTraversal(node.right,visitor);
    }
    
    /**
     * 中序遍历
     */
    public void inorderTraversal(Visitor<E> visitor) {
        inorderTraversal(root,visitor);
    }
    
    private void inorderTraversal(Node<E> node,Visitor<E> visitor) {
        if (node == null || visitor == null) return;
        inorderTraversal(node.left,visitor);
        visitor.visit(node.element);
        inorderTraversal(node.right,visitor);
    }
    
    /**
     * 后序遍历
     */
    public void postorderTraversal(Visitor<E> visitor) {
        postorderTraversal(root,visitor);
    }
    
    private void postorderTraversal(Node<E> node,Visitor<E> visitor) {
        if (node == null || visitor == null) return;
        postorderTraversal(node.left,visitor);
        postorderTraversal(node.right,visitor);
        visitor.visit(node.element);
    }
    
    /**
     * 层序遍历
     */
    public void levelOrderTraversal(Visitor<E> visitor){
        if (root == null || visitor == null) return;
        Queue<Node<E>> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            Node<E> node = queue.poll();
            visitor.visit(node.element);
            if (node.left != null) {
                queue.offer(node.left);
            }
            if (node.right != null) {
                queue.offer(node.right);
            }
        }
    }
    
    public static interface Visitor<E> {
        void visit(E elemet);
    }

利用上一章节二叉搜索树调用层序遍历

 package njf;
import java.util.Comparator;

import njf.printer.BinaryTreeInfo;
import njf.printer.BinaryTrees;
import njf.BinarySearchTree.Visitor;
import njf.file.Files;

public class Main {
    static void test1() {
        Integer data[] = new Integer[] {
                7, 4, 9, 2, 5, 8, 11, 3, 12, 1
        };
        
        BinarySearchTree<Integer> bst = new BinarySearchTree<>();
        for (int i = 0; i < data.length; i++) {
            bst.add(data[i]);
        }
        BinaryTrees.println(bst);
        bst.levelOrderTraversal(new Visitor<Integer>() {
            @Override
            public void visit(Integer elemet) {
                System.out.print("_" + elemet + "_");
            }
        });
//      bst.preorderTraversal(new Visitor<Integer>() {
//          @Override
//          public void visit(Integer elemet) {
//              System.out.print("_" + elemet + "_");
//              
//          }
//      });
    }
    
    public static void main(String[] args) {
        test1();
    }
}

打印结果如下：

             ┌───7_p(null)───┐
             │               │
        ┌─4_p(7)─┐       ┌─9_p(7)─┐
        │        │       │        │
   ┌─2_p(4)─┐  5_p(4) 8_p(9)   11_p(9)─┐
   │        │                          │
1_p(2)    3_p(2)                    12_p(11)
_7__4__9__2__5__8__11__1__3__12_

遍历接口增强

/**
     * 前序遍历
     */
    public void preorderTraversal(Visitor<E> visitor) {
        if (visitor == null) return;
        preorderTraversal(root,visitor);
    }
    
    private void preorderTraversal(Node<E> node,Visitor<E> visitor) {
        if (node == null || visitor.stop) return;
        visitor.stop = visitor.visit(node.element);
        preorderTraversal(node.left,visitor);
        preorderTraversal(node.right,visitor);
        return;
    }
    
    /**
     * 中序遍历
     */
    public void inorderTraversal(Visitor<E> visitor) {
        if (visitor == null) return;
        inorderTraversal(root,visitor);
    }
    
    private void inorderTraversal(Node<E> node,Visitor<E> visitor) {
        if (node == null || visitor.stop) return;
        inorderTraversal(node.left,visitor);
        if (visitor.stop) return;
        visitor.stop = visitor.visit(node.element);
        inorderTraversal(node.right,visitor);
    }
    
    /**
     * 后序遍历
     */
    public void postorderTraversal(Visitor<E> visitor) {
        if (visitor == null) return;
        postorderTraversal(root,visitor);
    }
    
    private void postorderTraversal(Node<E> node,Visitor<E> visitor) {
        if (node == null || visitor.stop) return;
        postorderTraversal(node.left,visitor);
        postorderTraversal(node.right,visitor);
        if (visitor.stop) return;
        visitor.stop = visitor.visit(node.element);
    }
    
    /**
     * 层序遍历
     */
    public void levelOrderTraversal(Visitor<E> visitor){
        if (root == null || visitor == null) return;
        Queue<Node<E>> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            Node<E> node = queue.poll();
            if (visitor.visit(node.element)) return;
            if (node.left != null) {
                queue.offer(node.left);
            }
            if (node.right != null) {
                queue.offer(node.right);
            }
        }
    }
    /**
     * java抽象类
     */
    public static abstract class Visitor<E> {
        boolean stop;
        /**
         * @return 如果返回true，就代表停止遍历
         */
        public abstract boolean visit(E elemet);
    }

利用上一章节二叉搜索树调用层序遍历

package njf;
import java.util.Comparator;

import njf.printer.BinaryTreeInfo;
import njf.printer.BinaryTrees;
import njf.BinarySearchTree.Visitor;
import njf.file.Files;

public class Main {
    static void test5() {
        Integer data[] = new Integer[] {
                7, 4, 9, 2, 1
        };
        
        BinarySearchTree<Integer> bst = new BinarySearchTree<>();
        for (int i = 0; i < data.length; i++) {
            bst.add(data[i]);
        }
        BinaryTrees.println(bst);
        
        bst.preorderTraversal(new Visitor<Integer>() {
            public boolean visit(Integer element) {
                System.out.print(element + " ");
                return element == 2 ? true : false;
            }
        });
        System.out.println();
        
        bst.inorderTraversal(new Visitor<Integer>() {
            public boolean visit(Integer element) {
                System.out.print(element + " ");
                return element == 4 ? true : false;
            }
        });
        System.out.println();
        
        bst.postorderTraversal(new Visitor<Integer>() {
            public boolean visit(Integer element) {
                System.out.print(element + " ");
                return element == 4 ? true : false;
            }
        });
        System.out.println();
        
        bst.levelOrderTraversal(new Visitor<Integer>() {
            public boolean visit(Integer element) {
                System.out.print(element + " ");
                return element == 9 ? true : false;
            }
        });
        System.out.println();
    }
    
    public static void main(String[] args) {
        test5();
    }
}

打印结果如下：

             ┌─7_p(null)─┐
             │           │
        ┌─4_p(7)       9_p(7)
        │
   ┌─2_p(4)
   │
1_p(2)
7 4 2 
1 2 4 
1 2 4 
7 4 9

前序遍历 – 非递归

    public void preorder(Visitor<E> visitor) {
        if (visitor == null || root == null) return;
        Node<E> node = root;
        Stack<Node<E>> stack = new Stack<>();
        while (true) {
            if (node != null) {
                if (visitor.visit(node.element)) return;
                if (node.right != null) {
                    stack.push(node.right);
                }
                node = node.left;
            }else if(stack.isEmpty()){
                return; 
            }else {
                node = stack.pop();
            }
        }
    }

    public void preorder(Visitor<E> visitor) {
        if (visitor == null || root == null) return;
        Stack<Node<E>> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            Node<E> node = stack.pop();
            if (visitor.visit(node.element)) return;
            if (node.right != null) {
                stack.push(node.right);
            }
            if (node.left != null) {
                stack.push(node.left);
            }
        }
    }

中序遍历 – 非递归

public void inorder(Visitor<E> visitor) {
        if (visitor == null || root == null) return;
        Stack<Node<E>> stack = new Stack<>();
        Node<E> node = root;
        while (true) {
            if (node != null) {
                stack.push(node);
                node = node.left;
            }else if (stack.isEmpty()) {
                return;
            }else {
                node = stack.pop();
                if (visitor.visit(node.element)) return;
                node = node.right;
            }
        }
    }

后序遍历 – 非递归

public void postorder(Visitor<E> visitor) {
        if (visitor == null || root == null) return;
        // 记录上一次弹出访问的节点
        Node<E> prev = null;
        Stack<Node<E>> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            Node<E> top = stack.peek();
            if (top.isLeaf()|| (prev != null && prev.parent == top)) {//没有子节点
                prev = stack.pop();
                if (visitor.visit(prev.element)) return;
            }else {
                if (top.right != null) {
                    stack.push(top.right);
                }
                if (top.left != null) {
                    stack.push(top.left);
                }
            }
        }
    }

练习：计算二叉树的高度

  • 递归法
public int height() {
      return height(root);
}
    
    /**
     * 计算二叉树的高度，利用递归
     */
private int height(Node<E> node) {
    if (node == null) return 0;
    return 1 + Math.max(height(node.left), height(node.right));
}
  • 层序遍历
    /**
     * 计算二叉树的高度，利用层序遍历
     */
    public int height() {
        if (root == null) return 0;
        // 树的高度
        int height = 0;
        // 存储着每一层的元素数量
        int levelSize = 1;
        Queue<Node<E>> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            Node<E> node = queue.poll();
            levelSize --;
            if (node.left != null) {
                queue.offer(node.left);
            }
            if (node.right != null) {
                queue.offer(node.right);
            }
            if (levelSize == 0) {// 意味着即将要访问下一层
                levelSize = queue.size();
                height ++;
            }
        }
        return height;
    }

练习: 判断一棵树是否为完全二叉树


◼ 如果树为空，返回 false
◼ 如果树不为空，开始层序遍历二叉树(用队列)
如果 node.left!=null，将 node.left 入队
如果 node.left==null && node.right!=null，返回 false
如果 node.right!=null，将 node.right 入队
如果 node.right==null
那么后面遍历的节点应该都为叶子节点，才是完全二叉树
否则返回 false
代码实现
public boolean isCompleteTree() {
        if (root == null) return false;
        Queue<Node<E>> queue = new LinkedList<>();
        queue.offer(root);
        boolean isLeaf = false;
        while (!queue.isEmpty()) {
            Node<E> node = queue.poll();
            //如果出现叶子结点，但是后面结点又不是叶子结点，false
            if (isLeaf && !(node.left == null && node.right == null)) return false;
            if (node.left != null) {
                queue.offer(node.left);
            }else if(node.right != null) {// node.left == null && node.right != null
                return false;
            }
            if(node.right != null) {
                queue.offer(node.right);
            }else {// node.right == null
                isLeaf = true;
            }
        }
        return true;
    }

利用上一章节二叉搜索树验证是否为完全二叉树

package njf;
import java.util.Comparator;

import njf.printer.BinaryTreeInfo;
import njf.printer.BinaryTrees;
import njf.BinarySearchTree.Visitor;
import njf.file.Files;

public class Main {
    static void test7() {
        Integer data[] = new Integer[] {
                7, 4, 10, 2, 5, 9, 11, 3, 1
        };
        
        BinarySearchTree<Integer> bst = new BinarySearchTree<>();
        for (int i = 0; i < data.length; i++) {
            bst.add(data[i]);
        }
        BinaryTrees.println(bst);
        System.out.println("是否为完全二叉树" + bst.isCompleteTree());
    }
    
    public static void main(String[] args) {
        test7();
    }
}

结果如下：

             ┌───7_p(null)────┐
             │                │
        ┌─4_p(7)─┐       ┌─10_p(7)─┐
        │        │       │         │
   ┌─2_p(4)─┐  5_p(4) 9_p(10)   11_p(10)
   │        │
1_p(2)    3_p(2)
是否为完全二叉树true

根据遍历结果重构二叉树

◼ 以下结果可以保证重构出唯一的一棵二叉树

  • 前序遍历 + 中序遍历
    例如：
    前序遍历：4 2 1 3 6 5
    中序遍历：1 2 3 4 5 6
  • 后序遍历 + 中序遍历

◼ 前序遍历 + 后序遍历
✓ 如果它是一棵真二叉树（Proper Binary Tree），结果是唯一的
✓ 不然结果不唯一

前驱节点（predecessor）

◼ 前驱节点：中序遍历时的前一个节点

如果是二叉搜索树，前驱节点就是前一个比它小的节点

实现思路：
◼ 如果node.left != null
举例：6、13、8

predecessor = node.left.right.right.right...

终止条件：right 为 null

◼ 如果node.left == null && node.parent != null
举例：7、11、9、1

predecessor = node.parent.parent.parent...

终止条件：node 在 parent 的右子树中

◼ 如果node.left == null && node.parent == null
那就没有前驱节点
举例：没有左子树的根节点

代码实现:

    /**
     * 是否为前驱结点
     */
    private Node<E> predecessor(Node<E> node) {
        if (node == null) return node;
        // 前驱节点在左子树当中（left.right.right.right....）
        Node<E> p = node.left;
        if (p != null) {
            while (p.right != null) {
                p = p.right;
            }
            return p;
        }
        // 从父结点、祖父节点中寻找前驱节点
        while (node.parent != null && node.parent.left == node) {
            node = node.parent;
        }
        // node.parent == null
        // node == node.parent.right
        return node.parent;
    }

后继节点（successor）

后继节点：中序遍历时的后一个节点

如果是二叉搜索树，后继节点就是后一个比它大的节点


◼ 如果node.right != null
举例：1、8、4 
successor = node.right.left.left.left...

终止条件：left 为 null

◼ 如果node.right == null && node.parent != null
举例：7、6、3、11

successor = node.parent.parent.parent...

终止条件：node 在 parent 的左子树中

◼ 如果node.right == null && node.parent == null
那就没有前驱节点
举例：没有右子树的根节点

    /**
     * 是否为后继结点
     */
    private Node<E> successor(Node<E> node) {
        if (node == null) return node;
        // 后继节点在右子树当中（right.left.left.left....）
        Node<E> p = node.right;
        if (p != null) {
            while (p.left != null) {
                p = p.left;
            }
            return p;
        }
        // 从父结点、祖父节点中寻找前驱节点
        while (node.parent != null && node.parent.right == node) {
            node = node.parent;
        }
        // node.parent == null
        // node == node.parent.left
        return node.parent;
    }

相关文章

  • 二叉树的遍历

    数据结构算法 二叉树的遍历

  • python实现二叉树的遍历

    二叉树是一种非常重要的数据结构，很多其它数据结构都是基于二叉树的基础演变而来的。对于二叉树，有深度遍历和广度遍历，...

  • 算法系列--二叉树的三种遍历的六种实现

    0. 二叉树是常见的数据结构，二叉树常见的遍历方式有前序遍历，中序遍历和后序遍历。前序遍历就是中-左-右节点的顺序...

  • 二叉树的四种遍历方法

    二叉树的数据结构 1、前序遍历（递归） 2、中序遍历（递归） 3、后序遍历（递归） 4、层次遍历（队列）

  • Python实现深度优先与广度优先

    二叉树的两种遍历是数据结构的经典考察题目, 广度遍历考察队列结构, 深度遍历考察递归 二叉树 深度优先 先序遍历(...

  • 数据结构第12讲 二叉树的层次遍历

    数据结构第12讲 二叉树的层次遍历 二叉树的遍历一般有先序遍历、中序遍历和后序遍历，这三种遍历比较简单。今天我们讲...

  • 算法学习

    ### 实现二叉树以及二叉树遍历数据结构递归比较重要 1.先序遍历 先序遍历，就是先遍历根节点然后再遍历左子树，最...

  • 二叉树的总结

    1、二叉树的数据结构 2、二叉树的创建 树的结构: 输入:AB#C##D## ; 3、二叉树的遍历 二叉树的遍历分...

  • 数据结构之二叉树

    数据结构之二叉树 递归构造二叉树 二叉树节点: 递归构造: 图示: 递归遍历 递归实现先序遍历 图示: 递归实现中...

  • 数据结构之二叉树

    数据结构之二叉树 本文讲解二叉树的基本操作： 查找节点 计算树的高度 清空树 递归遍历：先序遍历、中序遍历、后序遍...

网友评论

      本文标题：数据结构-二叉树的遍历

      本文链接：https://www.haomeiwen.com/subject/incuahtx.html

      延伸阅读

      深度阅读

      • 您也可以注册成为美文阅读网的作者，发表您的原创作品、分享您的心情！

      栏目导航

      热点阅读

      关于我们|服务条款|联系我们|数据结构-二叉树的遍历|投稿指南|网站地图|RSS订阅|排版工具|手机版

      提供经典美文摘抄,优美散文欣赏,现代诗歌精选,短篇小说,心情随笔,表白情书范文,故事会在线阅读欣赏

      Copyright © 2014-2023 Haomeiwen.com All Rights Reserved. 好美文阅读网 版权所有

      备案信息：桂公网安备 45052102000051号 · 桂ICP备13007215号-3

      本站所收录作品、热点评论等信息部分来源互联网，目的只是为了系统归纳学习和传递资讯

      所有作品版权归原创作者所有，与本站立场无关，如不慎侵犯了你的权益，请联系我们告知，我们将做删除处理！