手机网站开发者工具,网站建设公司湖南,九一人才网赣州,呼伦贝尔人才网官方网站入口树 1.树、二叉树 2.二叉查找树 3.平衡二叉树、红黑树 4.递归树
一、树
1.树的常用概念 根节点、叶子节点、父节点、子节点、兄弟节点#xff0c;还有节点的高度、深度以及层数#xff0c;树的高度。
2.概念解释 节点#xff1a;树中的每个元素称为节点 父子关系#xff…树 1.树、二叉树 2.二叉查找树 3.平衡二叉树、红黑树 4.递归树
一、树
1.树的常用概念 根节点、叶子节点、父节点、子节点、兄弟节点还有节点的高度、深度以及层数树的高度。
2.概念解释 节点树中的每个元素称为节点 父子关系相邻两节点的连线称为父子关系 根节点没有父节点的节点 叶子节点没有子节点的节点 父节点指向子节点的节点 子节点被父节点指向的节点 兄弟节点具有相同父节点的多个节点称为兄弟节点关系 节点的高度节点到叶子节点的最长路径所包含的边数 节点的深度根节点到节点的路径所包含的边数 节点的层数节点的深度1根节点的层数是1 树的高度等于根节点的高度
二、二叉树 1.概念 ①什么是二叉树 每个节点最多只有2个子节点的树这两个节点分别是左子节点和右子节点。 ②什么是满二叉树 有一种二叉树除了叶子节点外每个节点都有左右两个子节点这种二叉树叫做满二叉树。 ③什么是完全二叉树 有一种二叉树叶子节点都在最底下两层最后一层叶子节都靠左排列并且除了最后一层其他层的节点个数都要达到最大这种二叉树叫做完全二叉树。
2.完全二叉树的存储 ①链式存储 每个节点由3个字段其中一个存储数据另外两个是指向左右子节点的指针。我们只要拎住根节点就可以通过左右子节点的指针把整棵树都串起来。这种存储方式比较常用大部分二叉树代码都是通过这种方式实现的。 ②顺序存储 用数组来存储对于完全二叉树如果节点X存储在数组中的下标为i那么它的左子节点的存储下标为2i右子节点的下标为2i1反过来下标i/2位置存储的就是该节点的父节点。注意根节点存储在下标为1的位置。完全二叉树用数组来存储时最省内存的方式。 3.二叉树的遍历 ①前序遍历对于树中的任意节点来说先打印这个节点然后再打印它的左子树最后打印它的右子树。 ②中序遍历对于树中的任意节点来说先打印它的左子树然后再打印它的本身最后打印它的右子树。 ③后序遍历对于树中的任意节点来说先打印它的左子树然后再打印它的右子树最后打印它本身。 前序遍历的递推公式 preOrder® print r-preOrder(r-left)-preOrder(r-right) 中序遍历的递推公式 inOrder® inOrder(r-left)-print r-inOrder(r-right) 后序遍历的递推公式N postOrder® postOrder(r-left)-postOrder(r-right)-print r 时间复杂度3种遍历方式中每个节点最多会被访问2次所以时间复杂度是O(n)。
三、二叉查找树
二叉查找树要求在树中的任意一个节点其左子树中的每个节点的值都要小于这个节点的值而右子树节点的值都大于这个节点的值.
1. 查找操作: public class BinarySearchTree {private Node tree;public Node find(int data) {Node p tree;while (p ! null) {if (data p.data) p p.left;else if (data p.data) p p.right;else return p;}return null;}public static class Node {private int data;private Node left;private Node right;public Node(int data) {this.data data;}}
}先取根节点如果它等于我们要查找的数据那就返回。 如果要查找的数据比根节点的值小那就在左子树中递归查找。 如果要查找的数据比根节点的值大那就在右子树递归查找.
2. 插入操作
如果要插入的数据比节点的数据大并且节点的右子树为空就将数据直接插到右子节点的位置。 如果不为空就再递归遍历右子树查找插入位置。 如果要插入的数据比节点数值小并且节点的左子树为空就将数据插入到左子节点的位置 如果不为空就再递归遍历左子树查找插入位置。 public void insert(int data) {if (tree null) {tree new Node(data);return;}Node p tree;while (p ! null) {if (data p.data) {if (p.right null) {p.right new Node(data);return;}p p.right;} else { // data p.dataif (p.left null) {p.left new Node(data);return;}p p.left;}}
}3. 删除操作 1要删除的节点没有子节点我们只需要直接将父节点中指向要删除节点的指针置为null, 比如图中的删除节点55. 2要删除的节点只有一个子节点(只有左子节点或者右子节点),我们只需要更新父节点中指向要删除节点的指针让它指向要删除节点的子节点就好了。 3要删除的节点有两个子节点我们需要找到这个节点的右子树中的最小节点把他替换到要删除的节点上。然后再删除掉这个最小节点因为最小节点肯定没有左子节点(如果没有左子结点那就不是最小节点了). public void delete(int data) {Node p tree; // p指向要删除的节点初始化指向根节点Node pp null; // pp记录的是p的父节点while (p ! null p.data ! data) {pp p;if (data p.data) p p.right;else p p.left;}if (p null) return; // 没有找到// 要删除的节点有两个子节点if (p.left ! null p.right ! null) { // 查找右子树中最小节点Node minP p.right;Node minPP p; // minPP表示minP的父节点while (minP.left ! null) {minPP minP;minP minP.left;}p.data minP.data; // 将minP的数据替换到p中p minP; // 下面就变成了删除minP了 先付好值执行最后删除的语句pp minPP;}// 删除节点是叶子节点或者仅有一个子节点Node child; // p的子节点if (p.left ! null) child p.left;else if (p.right ! null) child p.right;else child null;//执行最后删除的语句if (pp null) tree child; // 删除的是根节点else if (pp.left p) pp.left child;else pp.right child;
}二叉查找树可以支持快速地查找最大节点和最小节点前驱节点和后继节点. 中序遍历二叉查找树可以输出有序的数据序列时间复杂度是O(n),非常高效。
完全二叉树的高度小于等于log2n 平衡二叉查找树的高度接近logn. 插入删除查找的时间复杂度比较稳定为O(logn).
四、 散列表 vs 二叉查找树
1 散列表是无序存储的要有序的话需要先排序 二叉查找树只需要中序遍历就可以在O(n)时间复杂度内输出有序的数据序列。
散列表扩容耗时多遇到散列冲突时性能不稳定常用的平衡二叉树性能稳定时间复杂度稳定在O(logn)
3一般来说散列表查找删除插入操作的时间复杂度是常量级的。但因哈希冲突的存在这个常量不一定比logn小加上哈希函数的耗时也就未必比平衡二叉查找树的效率高.
散列表构造比二叉查找树要复杂需要考虑的东西很多。比如散列函数的设计冲突接近方法扩容缩容等. 平衡二叉查找树只需要考虑平衡性这个问题。
5为了避免过多的散列冲突散列表装在因子不能太大特别是基于开放寻址法接近冲突的散列表.
N、思考
1.二叉树有哪几种存储方式什么样的二叉树适合用数组来存储 ①链式存储 ②顺序存储 完全二叉树 2.给定一组数据比如1356910.你来算算可以构建出多少种不同的二叉树 n 3.我们讲了三种二叉树的遍历方式前、中、后序。实际上还有另一种遍历方式也就是按层遍历你知道如何实现吗
class Solution {public ListListInteger levelOrder(TreeNode root) {if (root null) return new ArrayList(0);ListListInteger result new ArrayList();QueueTreeNode queue new LinkedListTreeNode();queue.offer(root);QueueTreeNode curLevelNodes new LinkedListTreeNode();while (!queue.isEmpty()) {TreeNode node queue.poll();curLevelNodes.offer(node);if (queue.isEmpty()) {ListInteger list new ArrayList(curLevelNodes.size());while (!curLevelNodes.isEmpty()) {TreeNode curNode curLevelNodes.poll();list.add(curNode.val);if (curNode.left ! null) {queue.offer(curNode.left);}if (curNode.right ! null) {queue.offer(curNode.right);}}result.add(list);}}return result;}}4.如何通过编程求出一棵给定二叉树的确切高度呢
[Leetcode][第104题][JAVA][二叉树的最大深度][递归][BFS]
笔记整理来源 王争 数据结构与算法之美
