本文共 5031 字，大约阅读时间需要 16 分钟。
满二叉树：
一个二叉树的所有非叶子结点都存在左右孩子，并且所有叶子结点都在同一层级上，那么这个树就是满二叉树
完全二叉树：
对一个有n个结点的二叉树，按层级顺序编号，则所有结点的编号从1到n。如果这个树所有结点和同样深度的满二叉树的编号从1到n结点位置相同，则这个二叉树为完全二叉树 数据结构包含物理结构和逻辑结构，二叉树属于逻辑结构，可通过多种物理结构来表达：链式存储结构和数组 使用数组存储时，会按照层级顺序的把二叉树的结点放到数组中对应的位置上。如果某个节点的左孩子或者右孩子空缺，则数组对应的位置也空出来，因为这样可以更方便地在数组中定位二叉树的孩子节点和父节点 加入一个父节点的下标时parent，那么他的左孩子的下标是 2 * parent + 1，右孩子下标为 2 * parent + 2；反过来如果知道左孩子是leftChild，则父节点的下标是 (leftChild - 1)/2 二叉树最主要的应用在于进行查找操作和维持相对顺序这两方面 二叉查找树特点： 1、如果左子树不为空，则左子树上所有节点的值均小于根节点的值 2、如果右子树不为空，则右子树上所有节点的值均大于跟节点的值 3、左右子树叶都是二叉查找树 对于一个节点分布相对均衡的二叉查找树来说，如果节点总数为n，那么搜索节点的时间复杂度就是O(logn)和树的深度是一样的，这种依靠比较大小来逐步查找的方式，和二分查找算法非常类似 二叉查找树要求左子树小于父节点、右子树大于父节点，正是这样保证了二叉树的有序性 二叉树自平衡的方式有多种，如红黑树、AVL树、树堆等二叉树是典型的非线形数据结构，遍历时需要把非线形关联的节点转化成一个线性的序列，以不同的方式来遍历，遍历出的序列顺序也不同
二叉树的遍历归纳为两大类 1、深度优先遍历（前序遍历、中序遍历、后续遍历） 前序遍历的顺序是：根结点、左节点、右节点 2、广度优先遍历（层级遍历）public class Ergodic { /** * 前序遍历 * @param node */ public static void preOrder(TreeNode node){ if(node == null){ return; } System.out.println(node.data); preOrder(node.leftNode); preOrder(node.rightNode); } /** * 中序遍历 * @param node */ public static void inOrder(TreeNode node){ if(node == null){ return; } inOrder(node.leftNode); System.out.println(node.data); inOrder(node.rightNode); } /** * 后序遍历 * @param node */ public static void postOrder(TreeNode node){ if(node == null){ return; } postOrder(node.leftNode); postOrder(node.rightNode); System.out.println(node.data); } /** * 使用栈处理，前序 * @param root */ public static void preOrderStack(TreeNode root){ Stack stack = new Stack<>(); TreeNode node = root; while (node != null || !stack.isEmpty()){ //迭代访问节点的左孩子，并入栈 while (node != null){ System.out.println(node.data); stack.push(node); node = node.leftNode; } //如果节点没有左孩子，则弹出栈顶元素，访问节点右孩子 if (!stack.isEmpty()){ node = stack.pop(); node = node.rightNode; } } } /** * 使用栈处理，中序 * @param root */ public static void inOrderStack(TreeNode root){ Stack stack = new Stack<>(); TreeNode node = root; while (node!=null || !stack.isEmpty()){ while (node != null){ stack.push(node); node = node.leftNode; } if(!stack.isEmpty()){ node = stack.pop(); System.out.println(node.data); node = node.rightNode; } } } /** * 使用栈处理，后序 * @param head */ public static void postOrderStack(TreeNode head) { if (head == null) { return; } Stack oneStack = new Stack<>(); Stack twoStack = new Stack<>(); oneStack.push(head); while (!oneStack.isEmpty()) { head = oneStack.pop(); twoStack.push(head); if (head.leftNode != null) { oneStack.push(head.leftNode); } if (head.rightNode != null) { oneStack.push(head.rightNode); } } while (!twoStack.isEmpty()) { System.out.println(twoStack.pop().data); } } /** * 广度优先，层级遍历 * @param head */ public static void levelOrder(TreeNode head){ Queue queue = new LinkedList() ; queue.offer(head); while (!queue.isEmpty()){ TreeNode node = queue.poll(); System.out.println(node.data); if(node.leftNode != null){ queue.offer(node.leftNode); } if(node.rightNode != null){ queue.offer(node.rightNode); } } } /** * 构建二叉树 * @param linkedList * @return */ public static TreeNode createTree(LinkedList linkedList){ TreeNode treeNode = null; if(linkedList == null || linkedList.isEmpty()){ return treeNode; } Integer data = linkedList.removeFirst(); if(data != null){ treeNode = new TreeNode(data); treeNode.leftNode = createTree(linkedList); treeNode.rightNode = createTree(linkedList); } return treeNode; } private static class TreeNode{ private Integer data; private TreeNode leftNode; private TreeNode rightNode; TreeNode(int data){ this.data = data; } } public static void main(String[] args) { LinkedList linkedList = new LinkedList (Arrays.asList(new Integer[]{3,2,9,null,null,10,null,null,8,null,4})); TreeNode treeNode = createTree(linkedList); System.out.println("前序遍历："); preOrder(treeNode); System.out.println("中序遍历："); inOrder(treeNode); System.out.println("后序遍历："); postOrder(treeNode); System.out.println("栈方式-前序遍历："); preOrderStack(treeNode); System.out.println("栈方式-中序遍历："); inOrderStack(treeNode); System.out.println("栈方式-后序遍历："); postOrderStack(treeNode); System.out.println("广度优先遍历："); levelOrder(treeNode); }}
转载地址：http://fqsvi.baihongyu.com/