目录
二叉树是数据结构中的重点,也是难点。二叉树是一种非线性结构,比数组、栈、队列等线性结构相比复杂度更高,想要做到心中有“树”,需要自己动手画图、观察、思考,才能领会其真谛。该文将会结合图形,深入理解二叉树、满二叉树及完全二叉树的概念。
// 结点 class Node<E> { E e; Node left, right; Node(E e) { this.e= e; this.left = null; this.right = null; } }
/** * 完全二叉树的线性存储 * * @author zhuhuix * @date 2020-06-24 */ public class FullBinaryTree { private Object[] arr; private int size; FullBinaryTree(int capacity) { this.arr = new Object[capacity + 1]; this.size = 0; } public int getSize() { return this.size; } public boolean isEmpty() { return this.size == 0; } public void add(Object e, int index) { assert index <= this.arr.length; this.arr[index] = e; this.size++; } @Override public String toString() { return "FullBinaryTree{" + "arr=" + Arrays.toString(arr) + ", size=" + size + '}'; } public static void main(String[] args) { FullBinaryTree fullBinaryTree = new FullBinaryTree(26); // 从下标1开始存入26个字母 for (Character c = 'A'; c <= 'Z'; c++) { fullBinaryTree.add(c, c - 'A' + 1); } System.out.println( fullBinaryTree.toString()); } }
/** * 完全二叉树的创建与遍历 * * @author zhuhuix * @date 2020-06-24 */ public class BinaryTree { // 结点 private Node root; // 结点数 private int size; // 存放结点 private ArrayList<Node> list; public BinaryTree() { this.root = null; this.size = 0; this.list = new ArrayList<>(); } public void createTree(Object[] array){ for(int i=0;i<array.length;i++){ Node node =new Node(array[i]); list.add(node); if (this.root==null){ this.root = node; } } if(list.size()>0){ for(int i=0;i<array.length/2;i++){ if(2*i+1<list.size()) { list.get(i).left=list.get(2 * i + 1); } if(2*i+2<list.size()) { list.get(i).right=list.get(2 * i + 2); } } } } // 前序遍历 public void preOrder(Node root){ if(root == null){ return ; } else{ System.out.println(root.getData()); } preOrder(root.left); preOrder(root.right); } public Node getRoot() { return root; } // 私有内部类-树结点 private class Node { Object data; Node left, right; Node(Object data) { this.data = data; this.left = null; this.right = null; } Object getData() { return data; } } public static void main(String[] args) { BinaryTree binaryTree = new BinaryTree(); Character[] array ={'A','B','C','D','E','F','G','H','I','J','K','L', 'M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z'}; binaryTree.createTree(array); binaryTree.preOrder(binaryTree.getRoot()); } }
原文链接:https://www.cnblogs.com/zhuhuix/p/13370437.html