美文网首页
18-二叉树的遍历

18-二叉树的遍历

作者: weyan | 来源:发表于2021-08-26 21:08 被阅读0次

一、前序遍历


1.递归写法
  • 以二叉搜索树代码为例
递归方法

二、中序遍历

1.递归写法

  • 以二叉搜索树代码为例


    递归方法

三、后序遍历

1.递归写法

  • 以二叉搜索树代码为例

四.层序遍历

  • 以二叉搜索树代码为例
image.png

附：二叉搜索树的代码

package com.weyan;

import java.util.Comparator;
import java.util.LinkedList;
import java.util.Queue;

import com.weyan.printer.BinaryTreeInfo;

@SuppressWarnings("unused")

//使用自定义打印器 需要实现BinaryTreeInfo类中的几个方法：root/ left/ right/ string
public class BinarySearchTree<E> implements BinaryTreeInfo {
    
    private int size;
    //根节点
    private Node<E> root;
    private Comparator<E> comparator;
    
    //构造函数 不传入参数
    public BinarySearchTree() {
        this(null);
    }
    //构造函数 传入参数：比较器
    public BinarySearchTree(Comparator<E> comparator) {
        this.comparator = comparator;
    }
    
    public int size() {
        return size;
    }
    
    public boolean isEmpty() {
        return size == 0;
    }
    
    public void clear() {
        
    }
    
    public void add(E element) {
        elementNotNullCheck(element);
        //添加第一个节点
        if (root == null) {
            root = new Node<>(element, null);
            size ++;
            return;
        }
        //添加的不是第一个节点
        //找到父节点
        Node<E> parent = root;
        Node<E> node = root;
        int cmp = 0;
        while (node != null) {
            parent = node;
            cmp = compare(element, node.element);
            if (cmp > 0) {
                node = node.right;
            }else if(cmp < 0) {
                node = node.left;
            }else {//相等
                node.element = element;
                return;
            }
        }
        //看看插入到父节点的哪个位置
        Node<E> newNode = new Node<E>(element, parent);
        if (cmp > 0) {
            parent.right = newNode;
        }else if(cmp < 0) {
            parent.left = newNode;
        }
        size ++;
    }
    
    public void remove(E element) {
        
    }
    
    public boolean contains(E element) {
        return false;
    }
    
    //比较两个节点,返回值==0代表e1和e2相等;返回值>0代表e1>e2;返回值<0代表e1<e2
    @SuppressWarnings("unchecked")
    private int compare(E e1 , E e2) {
        if (comparator != null) {
            return comparator.compare(e1, e2);
        }
        return ((Comparable<E>) e1).compareTo(e2);
    
    }
    
    //判断一个节点是否为空
    private void elementNotNullCheck(E element) {
        if (element == null) {
            throw new IllegalArgumentException("element must not be null");
        }
    }
    
    //前序遍历（递归方法）
    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);
    }
    
    //中序遍历（递归方法）
        public void inorderTraversal() { 
            preorderTraversal(root);
        }
        
        private void inorderTraversal(Node<E> node) {
            if (node == null) return;
            preorderTraversal(node.left);
            System.out.println(node.element);
            preorderTraversal(node.right);
        }
    //后序遍历（递归方法）
    public void postorderTraversal() {
        postorderTraversal(root);
    }
    private void postorderTraversal(Node<E> node) {
        if (node == null) return;
        preorderTraversal(node.left);
        preorderTraversal(node.right);
        System.out.println(node.element);
    }
    
    //层序遍历(通过链表实现)
    private 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);
            }
        }
    }
    
    private static class Node<E> {
        E element;
        //左子节点
        Node<E> left;
        //右子节点
        Node<E> right;
        //父节点
        Node<E> parent;
        //构造函数
        public Node(E element,Node<E> parent) {
            this.element = element;
            this.parent = parent;
        }
    }
    
    
    /*使用自定义打印器 需要实现以下几个方法
     * 
     */
    @Override
    public Object root() {
        // TODO Auto-generated method stub
        return root;
    }
    
    @SuppressWarnings("unchecked")
    @Override
    public Object left(Object node) {
        // TODO Auto-generated method stub
        return ((Node<E>) node).left;
    }
    
    @SuppressWarnings("unchecked")
    @Override
    public Object right(Object node) {
        // TODO Auto-generated method stub
        return ((Node<E>) node).right;
    }
    
    @SuppressWarnings("unchecked")
    @Override
    public Object string(Object node) {
        // TODO Auto-generated method stub
        //打印出parent
        Node<E> myNode = (Node<E>) node;
        String parentString = "null";
        if (myNode.parent != null) {
            parentString = myNode.parent.element.toString();
        }
        return myNode.element + "_(" + parentString + ")";
    }
}

五、遍历的应用

1.计算二叉树的高度

  • 递归写法
  • 采用层序遍历
/**---层序遍历写法---**/
    //二叉树的高度
    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;
    }

六、练习

（一）

代码-以二叉搜索树为例

package com.weyan;

import java.util.Comparator;
import java.util.LinkedList;
import java.util.Queue;

import com.weyan.printer.BinaryTreeInfo;

@SuppressWarnings("unused")

//使用自定义打印器 需要实现BinaryTreeInfo类中的几个方法：root/ left/ right/ string
public class BinarySearchTree<E> implements BinaryTreeInfo {
    
    private int size;
    //根节点
    private Node<E> root;
    private Comparator<E> comparator;
    
    //构造函数 不传入参数
    public BinarySearchTree() {
        this(null);
    }
    //构造函数 传入参数：比较器
    public BinarySearchTree(Comparator<E> comparator) {
        this.comparator = comparator;
    }
    
    public int size() {
        return size;
    }
    
    public boolean isEmpty() {
        return size == 0;
    }
    
    public void clear() {
        
    }
    
    public void add(E element) {
        elementNotNullCheck(element);
        //添加第一个节点
        if (root == null) {
            root = new Node<>(element, null);
            size ++;
            return;
        }
        //添加的不是第一个节点
        //找到父节点
        Node<E> parent = root;
        Node<E> node = root;
        int cmp = 0;
        while (node != null) {
            parent = node;
            cmp = compare(element, node.element);
            if (cmp > 0) {
                node = node.right;
            }else if(cmp < 0) {
                node = node.left;
            }else {//相等
                node.element = element;
                return;
            }
        }
        //看看插入到父节点的哪个位置
        Node<E> newNode = new Node<E>(element, parent);
        if (cmp > 0) {
            parent.right = newNode;
        }else if(cmp < 0) {
            parent.left = newNode;
        }
        size ++;
    }
    
    public void remove(E element) {
        
    }
    
    public boolean contains(E element) {
        return false;
    }
    
    /**---递归写法---**/
    //二叉树的高度
//  public int height() {
//      return nodeHeight(root);
//  }
    //节点高度
//  private int nodeHeight(Node<E> node) {
//      if (node == null) return 0;
//      return 1 + Math.max(nodeHeight(node.left), nodeHeight(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;
    }
    
    //比较两个节点,返回值==0代表e1和e2相等;返回值>0代表e1>e2;返回值<0代表e1<e2
    @SuppressWarnings("unchecked")
    private int compare(E e1 , E e2) {
        if (comparator != null) {
            return comparator.compare(e1, e2);
        }
        return ((Comparable<E>) e1).compareTo(e2);
    
    }
    
    //判断一个节点是否为空
    private void elementNotNullCheck(E element) {
        if (element == null) {
            throw new IllegalArgumentException("element must not be null");
        }
    }
    
    //前序遍历（递归方法）
    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);
    }
    
    //中序遍历（递归方法）
        public void inorderTraversal() { 
            preorderTraversal(root);
        }
        
        private void inorderTraversal(Node<E> node) {
            if (node == null) return;
            preorderTraversal(node.left);
            System.out.println(node.element);
            preorderTraversal(node.right);
        }
    //后序遍历（递归方法）
    public void postorderTraversal() {
        postorderTraversal(root);
    }
    private void postorderTraversal(Node<E> node) {
        if (node == null) return;
        preorderTraversal(node.left);
        preorderTraversal(node.right);
        System.out.println(node.element);
    }
    
    //层序遍历(通过链表实现)
    private 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 boolean isComplete() {
        if (root == null) return false;
        Queue<Node<E>> queue = new LinkedList<>();
        queue.offer(root);
        
        boolean leaf = false;
        while (!queue.isEmpty()) {
            Node<E> node = queue.poll();
            if (leaf && !node.isLeaf()) return false;
            
            if (node.left != null) {
                queue.offer(node.left);
            }else if (node.right != null) {
                return false;
            } 
            
            if (node.right != null) {
                queue.offer(node.right);
            }else {
                //后面遍历的节点都必须是叶子节点
                leaf = true;
            }
        }
        
        return true;
    }
    
    private static class Node<E> {
        E element;
        //左子节点
        Node<E> left;
        //右子节点
        Node<E> right;
        //父节点
        Node<E> parent;
        //构造函数
        public Node(E element,Node<E> parent) {
            this.element = element;
            this.parent = parent;
        }
        //是否是叶子节点
        public boolean isLeaf() {
            return left == null && right == null;
        }
        
    }
    
    
    /*使用自定义打印器 需要实现以下几个方法
     * 
     */
    @Override
    public Object root() {
        // TODO Auto-generated method stub
        return root;
    }
    
    @SuppressWarnings("unchecked")
    @Override
    public Object left(Object node) {
        // TODO Auto-generated method stub
        return ((Node<E>) node).left;
    }
    
    @SuppressWarnings("unchecked")
    @Override
    public Object right(Object node) {
        // TODO Auto-generated method stub
        return ((Node<E>) node).right;
    }
    
    @SuppressWarnings("unchecked")
    @Override
    public Object string(Object node) {
        // TODO Auto-generated method stub
        //打印出parent
        Node<E> myNode = (Node<E>) node;
        String parentString = "null";
        if (myNode.parent != null) {
            parentString = myNode.parent.element.toString();
        }
        return myNode.element + "_(" + parentString + ")";
    }
}
（二）翻转二叉树
package 二叉树;

import java.util.LinkedList;
import java.util.Queue;

/*url:https://leetcode-cn.com/problems/invert-binary-tree/
 * 翻转二叉树
 */
public class _226_翻转二叉树 {
    /*--------------递归方法-------------*/
    // 1.前序遍历
//  public TreeNode invertTree(TreeNode root) {
//      if (root == null) return root;
//      TreeNode tmp = root.left;
//      root.left = root.right;
//      root.right = tmp;
//      invertTree(root.left);
//      invertTree(root.right);
//      return root;
//    }

    // 2.后序遍历
//  public TreeNode invertTree(TreeNode root) {
//      if (root == null) return root;
//      invertTree(root.left);
//      invertTree(root.right);
//      TreeNode tmp = root.left;
//      root.left = root.right;
//      root.right = tmp;
//      return root;
//    }

    // 3.中序遍历
//  public TreeNode invertTree(TreeNode root) {
//      if (root == null)  return root;
//      invertTree(root.left);
//      TreeNode tmp = root.left;
//      root.left = root.right;
//      root.right = tmp;
//      invertTree(root.left);
//      return root;
//  }

    /*--------------迭代（非递归）-------------*/
    // 4.层序遍历
    public TreeNode invertTree(TreeNode root) {
        if (root == null)
            return root;
        
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            TreeNode tmp = node.left;
            node.left = node.right;
            node.right = tmp;
            if (node.left != null) {
                queue.offer(node.left);
            }
            if (node.right != null) {
                queue.offer(node.right);
            }
        }
        return root;
    }

}
验证结果
（三）重构二叉树

相关文章

  • 二叉树 基础操作

    二叉树的使用 二叉树结构 先序创建二叉树 DFS 先序遍历二叉树 中序遍历二叉树 后序遍历二叉树 BFS 层次遍历...

  • 二叉树遍历

    二叉树 二叉树的存储结构 前序遍历 中序遍历 后序遍历 遍历代码 反转二叉树 深入学习二叉树 二叉树-你必须要懂！...

  • 二叉树操作

    树节点 逐行顺序解析二叉树 前序遍历二叉树 中序遍历二叉树 后序遍历二叉树 删除指定数值的节点 前序遍历顺序存储的...

  • 关于二叉树的算法题

    前序遍历中序遍历后序遍历判断是否是平衡二叉树判断是否是对称二叉树判断二叉树高度按照层遍历二叉树判断二叉树宽度

  • 二叉树三种遍历Swift代码实现

    二叉树的三种遍历 二叉树 前序遍历 中序遍历 后序遍历 另外 不得不说，得到二叉树的前序遍历和中序遍历的结果或者后...

  • 数据结构与算法之二叉树遍历(七)

    目录 前序遍历中序遍历后序遍历层序遍历遍历方式的选择条件根据遍历结果重构二叉树翻转二叉树计算二叉树的高度判断一棵树...

  • 二叉树的遍历

    二叉树的遍历 二叉树遍历 分为前序遍历、中序遍历和后序遍历。 前序遍历 (DLR) 先访问根节点，然后前序遍历左子...

  • 数据结构：树的实现和遍历（c++）

    （一）二叉树的遍历——递归实现 二叉树常见的遍历方式分为前序遍历、中序遍历和后序遍历。 1 前序遍历 前序遍历也叫...

  • 18-二叉树的遍历

    一、前序遍历 以二叉搜索树代码为例 二、中序遍历 1.递归写法 以二叉搜索树代码为例递归方法 三、后序遍历 1.递...

  • 二叉树的蛇形层次遍历(LeetCode.103)

    题目 解析 首先参考二叉树的层次遍历层次遍历二叉树（LeetCode--102二叉树的层次遍历）[https://...

网友评论

      本文标题：18-二叉树的遍历

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

      延伸阅读

      深度阅读

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

      栏目导航

      热点阅读

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

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

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

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

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

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