数据结构与算法 二叉树基本框架与知识点

二叉树的定义

二叉树是n个节点的集合，n >= 0。当 n = 0 时这为一颗空二叉树。或一个根节点带着两颗互不相交的左子树和右子树，同时左右子树仍为二叉树。

四种特殊的二叉树

满二叉树： 高度为h，节点有 (2^h - 1 )个节点的二叉树。对于编号为 i 的节点，编号为(i/2)向下取整的节点为该节点的双亲节点；如果该节点有子节点，编号2i 和 2i + 1 的节点为 该节点的孩子节点。完全二叉树： 高度为h，节点个数为n；并且该树的节点与高度为h的满二叉树编号为 1~n 的所有节点一一对应。排序二叉树： 左子树上的节点的排序属性（关键字）比根节点的排序属性小，右子树上的节点的排序属性大于根节点的排序属性。并且左右子树也为排序二叉树。平衡二叉树: 树上的任意节点的左右子树的高度差不大于1的二叉树。

二叉树的存储

顺序存储： 二叉树的节点从上至下、从左向右存储到一块连续的存储空间(数组)中，当节点为空时用数字0或者其他标识符号替代。由存储方式可知，当该二叉树极为不平衡时（节点不均匀的分布到某一边子树中），会出现大量的存储空间被浪费。

链式存储： 为了弥补顺序存储的缺点，利用包含数据域、左右指针的节点数据结构存储节点元素，这样能很好地利用碎片化的空间。

二叉树的遍历

递归遍历

前序遍历（遍历的顺序的命名由访问当前节点的顺序决定） /** * Traverse the tree by recursion in the pre order * @param node root */ public void preOderRecursionTraverse(TreeNode node){ if(node != null){ System.out.println(node);//visit preOderRecursionTraverse(node.left); preOderRecursionTraverse(node.right); } } 中序遍历 /** *Traverse the tree by recursion in the mid order * @param node root */ public void midOderRecursionTraverse(TreeNode node){ if(node != null){ midOderRecursionTraverse(node.left); System.out.println(node);//visit midOderRecursionTraverse(node.right); } } 后序遍历 /** *Traverse the tree by recursion in the post order * @param node root */ public void postOderRecursionTraverse(TreeNode node){ if(node != null){ postOderRecursionTraverse(node.left); postOderRecursionTraverse(node.right); System.out.println(node);//visit } }

非递归遍历

深度优先(利用栈stack)

1.1. 前序遍历

/** * Traverse the tree in the depth first and the pre order * @param node root */ public void preOderDepthFirstTraverse(TreeNode node){ TreeNode temp = node; Stack<TreeNode> stack = new Stack<>(); while (temp != null || !stack.isEmpty()){ if(temp != null){ System.out.println(temp);//visit stack.push(temp); temp = temp.left; }else { temp = stack.pop(); temp = temp.right; } } }

1.2. 中序遍历

/** * Traverse the tree in the depth first and the post order * @param node root */ public void midOderDepthFirstTraverse(TreeNode node){ TreeNode temp = node; Stack<TreeNode> stack = new Stack<>(); while (temp != null || !stack.isEmpty()){ if(temp != null){ stack.push(temp); temp = temp.left; }else { temp = stack.pop(); System.out.println(temp); temp = temp.right; } } } 广度优先（利用队列queue） /** * Traverse the tree in the width first * @param node root */ public void widthFirstTraverse(TreeNode node){ Queue<TreeNode> queue = new ArrayDeque<>(); TreeNode temp; queue.offer(node); while (!queue.isEmpty()){ temp = queue.poll(); System.out.println(temp);//visit if(temp.left != null){ queue.offer(temp.left); } if(temp.right != null){ queue.offer(temp.right); } } }

排序二叉树的基本操作

插入节点 /** * Add a node into the tree * @param value the value needs to be insert * @return indicator which shows if the value has been inserted. */ public int insertNode(int value){ TreeNode current = root; TreeNode pre = null; //locate the pre node which is the father node of inserted node while (current != null){ pre = current; if(current.val < value){ current = current.right; }else if(current.val > value){ current = current.left; }else { return 0; } } //insert node if(root == null){ root = new TreeNode(value); }else if(pre.val < value){ pre.right = new TreeNode(value); }else { pre.left = new TreeNode(value); } return 1; } 根据数组中元素的顺序构造树 /** * The constructor which builds the sorted binary tree * @param values, all nodes'value which will be used to construct * the tree. */ public SortedBinaryTree(int [] values){ for(int i = 0;i < values.length;i ++){ insertNode(values[i]); } } 查找某个节点 /** * Find the node which have the same value with the one provided * @param value the value which wants to be found * @return the node or null */ public TreeNode findNode(int value){ TreeNode node = root; while (node != null){ if(node.val < value){ node = node.right; }else if(node.val > value){ node = node.left; }else { return node; } } return null; } 删除某个节点 /** * 如果需要代码实现，需要为节点数据结构添加parent域用来指向父节点 * @param value */ public void removeNode(int value){ //分类讨论被删除节点的情况 //1.当节点为叶子节点：直接删除该节点 //2.当该节点只有一个子节点，用该节点的子节点替代该节点 //3.当该节点有左右子节点：用小于该节点的最大节点(左子树的最大节点)替代该节点 // 或用大于该最小节点（右子树的最小节点）替代该节点，再删除该节点。 }

完整代码

package DataStructureAndAlgorithm.nonlinearStructure.binaryTree; import java.util.ArrayDeque; import java.util.Queue; import java.util.Stack; public class SortedBinaryTree { public TreeNode root; /** * The constructor which builds the sorted binary tree * @param values, all nodes'value which will be used to construct * the tree. */ public SortedBinaryTree(int [] values){ for(int i = 0;i < values.length;i ++){ insertNode(values[i]); } } /** * Add a node into the tree * @param value the value needs to be insert * @return indicator which shows if the value has been inserted. */ public int insertNode(int value){ TreeNode current = root; TreeNode pre = null; //locate the pre node which is the father node of inserted node while (current != null){ pre = current; if(current.val < value){ current = current.right; }else if(current.val > value){ current = current.left; }else { return 0; } } //insert node if(root == null){ root = new TreeNode(value); }else if(pre.val < value){ pre.right = new TreeNode(value); }else { pre.left = new TreeNode(value); } return 1; } /** * Find the node which have the same value with the one provided * @param value the value which wants to be found * @return the node or null */ public TreeNode findNode(int value){ TreeNode node = root; while (node != null){ if(node.val < value){ node = node.right; }else if(node.val > value){ node = node.left; }else { return node; } } return null; } /** * Traverse the tree by recursion in the pre order * @param node root */ public void preOderRecursionTraverse(TreeNode node){ if(node != null){ System.out.println(node);//visit preOderRecursionTraverse(node.left); preOderRecursionTraverse(node.right); } } /** *Traverse the tree by recursion in the mid order * @param node root */ public void midOderRecursionTraverse(TreeNode node){ if(node != null){ midOderRecursionTraverse(node.left); System.out.println(node);//visit midOderRecursionTraverse(node.right); } } /** *Traverse the tree by recursion in the post order * @param node root */ public void postOderRecursionTraverse(TreeNode node){ if(node != null){ postOderRecursionTraverse(node.left); postOderRecursionTraverse(node.right); System.out.println(node);//visit } } /** * Traverse the tree in the depth first and the pre order * @param node root */ public void preOderDepthFirstTraverse(TreeNode node){ TreeNode temp = node; Stack<TreeNode> stack = new Stack<>(); while (temp != null || !stack.isEmpty()){ if(temp != null){ System.out.println(temp);//visit stack.push(temp); temp = temp.left; }else { temp = stack.pop(); temp = temp.right; } } } /** * Traverse the tree in the depth first and the post order * @param node root */ public void midOderDepthFirstTraverse(TreeNode node){ TreeNode temp = node; Stack<TreeNode> stack = new Stack<>(); while (temp != null || !stack.isEmpty()){ if(temp != null){ stack.push(temp); temp = temp.left; }else { temp = stack.pop(); System.out.println(temp); temp = temp.right; } } } /** * Traverse the tree in the width first * @param node root */ public void widthFirstTraverse(TreeNode node){ Queue<TreeNode> queue = new ArrayDeque<>(); TreeNode temp; queue.offer(node); while (!queue.isEmpty()){ temp = queue.poll(); System.out.println(temp);//visit if(temp.left != null){ queue.offer(temp.left); } if(temp.right != null){ queue.offer(temp.right); } } } /** * 如果需要代码实现，需要为节点数据结构添加parent域用来指向父节点 * @param value */ public void removeNode(int value){ //分类讨论被删除节点的情况 //1.当节点为叶子节点：直接删除该节点 //2.当该节点只有一个子节点，用该节点的子节点替代该节点 //3.当该节点有左右子节点：用小于该节点的最大节点(左子树的最大节点)替代该节点 // 或用大于该最小节点（右子树的最小节点）替代该节点，再删除该节点。 } public static void main(String[] args) { //construct a tree int [] values = new int[] {1, 2, 3, 4, 5, 6}; SortedBinaryTree tree = new SortedBinaryTree(values); //add two more nodes tree.insertNode( 7); tree.insertNode( 8); //find the node System.out.println(tree.findNode(8)); System.out.println("pre order in recursion"); tree.preOderRecursionTraverse(tree.root); System.out.println("mid order in recursion"); tree.midOderRecursionTraverse(tree.root); System.out.println("post order in recursion"); tree.postOderRecursionTraverse(tree.root); System.out.println("pre order in depth firsts"); tree.preOderDepthFirstTraverse(tree.root); System.out.println("Mid order in depth firsts"); tree.midOderDepthFirstTraverse(tree.root); System.out.println("width firsts"); tree.widthFirstTraverse(tree.root); } } package DataStructureAndAlgorithm.nonlinearStructure.binaryTree; public class TreeNode { int val; TreeNode left; TreeNode right; public TreeNode(int x) { val = x; } @Override public String toString() { return "TreeNode{" + "val=" + val + '}'; } }

分析排序二叉树的查找时间复杂度引出红黑树

排序二叉树查找的平均时间复杂度为O（log2（n））（每次查找排除一半直到找到目标元素）。当节点都在根的一边并且都为右节点或左节点时，时间复杂度为O（n）。这种情况被成为树的不平衡。如果树为平衡排序二叉树，查找的性能得到比较好的保证。如果我们要保证树的平衡，在删除或插入节点时就要保证树的平衡。这里引出树的平衡操作（调整节点位置使树保持平衡状态，旋转）的概念，但不做详细讨论。同时科学家提出另一种类平衡树的数据结构，红黑树。红黑树是大致平衡的但一般比平衡二叉树更高效（调整节点的次数较少）。在JDK中TreeMap就是红黑树的一个实例。红黑树的定义和特性： 3.1. 每个节点要么是红色要么是黑色(被标记为或被认为)。 3.2. 根节点永远是黑色。 3.3. 所有叶子节点都是空节点null，并且被认为是黑色的。 3.4. 每个红色节点的两个子节点都是黑色（每个叶子节点到根的路径上不会有两个连续的红色节点）。 3.5. 从任一节点到其子树中每个叶子节点的路径都包含相同数量的黑色节点。 3.6. 所以以上特性"保证了没有某一条路径的长度是其他路径的两倍。"