二叉树的前序、中序、后序遍历,通过递归和非递归的方式实现【Java】
概述
二叉树的遍历,一个老生常谈的问题,大学的时候就天天学习,但是那时候大多是了解每中遍历的方式,但是并没有用代码实现,工作之后,使用代码实现一下。
三种遍历方式的区别
具体的介绍我这里就不说了,只总结性的说一下,所谓的前序,中序,后序,的前中后,其实就是根节点被访问的前中后,前序遍历就是根节点在最开始,中序遍历就是根节点在中间,后序遍历就是根节点在最后,当然这个根节点并不一定是二叉树的唯一根节点,而是每个节点只要有子节点,那这个节点其实都可以看作子节点的根节点。
下面就上代码
通过java自己实现二叉树
先定义节点
1 package com.example.demo.tree; 2 3 /** 4 * @author steve 5 * @date 2020/4/18 3:16 下午 6 */ 7 public class Node<E> { 8 public Node<E> left; 9 public Node<E> right; 10 public Node<E> parent; 11 public E element; 12 public Node(E element){ 13 this.element = element; 14 } 15 }
定义二叉树
1 package com.example.demo.tree; 2 3 import com.sun.scenario.effect.impl.sw.sse.SSEBlend_SRC_OUTPeer; 4 import org.omg.PortableInterceptor.INACTIVE; 5 6 import java.util.Comparator; 7 8 /** 9 * @author steve 10 * @date 2020/4/16 10:03 上午 11 */ 12 public class BinaryTree<E> { 13 14 private int size; 15 public Node<E> root; 16 private Comparator<E> comparator; 17 18 public BinaryTree(Comparator<E> comparator){ 19 this.comparator = comparator; 20 } 21 22 public BinaryTree(){ 23 this(null); 24 } 25 26 public void add(E element){ 27 if (root == null){ 28 Node node = new Node(element); 29 root = node; 30 }else { 31 Node<E> parent = root; 32 Node<E> node = root; 33 int com = 0; 34 while (node != null){ 35 parent = node; 36 if (comparator == null){ 37 com = ((Comparable)node.element).compareTo(element); 38 }else { 39 System.out.println("-------------"); 40 com = comparator.compare(node.element,element); 41 } 42 if (com > 0){ 43 node = node.left; 44 }else if (com < 0){ 45 node = node.right; 46 }else { 47 node.element = element; 48 return; 49 } 50 } 51 Node<E> newNode = new Node(element); 52 if (com > 0){ 53 parent.left = newNode; 54 newNode.parent = parent.left; 55 }else{ 56 parent.right = newNode; 57 newNode.parent = parent.right; 58 } 59 } 60 size ++; 61 } 62 public boolean isEmpty(){ 63 return size == 0; 64 } 65 public int size(){ 66 return size; 67 } 68 69 public String toString() { 70 String d = root == null ? null : root.element + ""; 71 if (root == null){ 72 return "root:"+d; 73 }else { 74 String b = root.left == null ? null : root.left.element + ""; 75 String c = root.right == null ? null : root.right.element + ""; 76 return "root:"+d + ", left:" + b + ", right:"+ c; 77 } 78 79 } 80 81 82 public static void main(String[] args) { 83 //这种方式就是匿名内部类,通过给一个类传一个接口作为参数,然后这个通过一个匿名内部类是实现这个接口来传入实现。 84 BinaryTree<Integer> binaryTree = new BinaryTree<>(new Comparator<Integer>() { 85 @Override 86 public int compare(Integer o1, Integer o2) { 87 return o1 - o2; 88 } 89 }); 90 91 BinaryTree<Integer> binaryTree1 = new BinaryTree<>(); 92 binaryTree1.add(1); 93 binaryTree1.add(2); 94 binaryTree1.add(0); 95 System.out.println(binaryTree1.size()); 96 System.out.println(binaryTree.toString()); 97 } 98 }