做网站的又营业执照的吗,网站开发 asp.net php,凡科建站微信小程序,网站seo诊断方案20172332 2017-2018-2 《程序设计与数据结构》第七周学习总结 教材学习内容总结 第十一章 二叉查找树 1.二叉查找树#xff1a;一种带有附加属性的二叉树。即每个结点其左孩子都要小于其父结点#xff0c;而父结点又小于或等于其右孩子。#xff08;左孩子父结点右孩… 20172332 2017-2018-2 《程序设计与数据结构》第七周学习总结 教材学习内容总结 第十一章 二叉查找树 1.二叉查找树一种带有附加属性的二叉树。即每个结点其左孩子都要小于其父结点而父结点又小于或等于其右孩子。左孩子父结点右孩子2.二叉查找树不仅具有二叉树的操作还具有以下的特殊操作 3.用链表实现二叉查找树每个BinaryTreeNode对象要维护一个指向结点所存储元素的引用另外还要维护指向结点的每个孩子的引用。4.二叉查找树的构造函数代码引用了父类的两个构造函数 public LinkedBinarySearchTree() {super();}public LinkedBinarySearchTree(T element) {super(element);if (!(element instanceof Comparable))throw new NonComparableElementException(LinkedBinarySearchTree);} 5.addElement操作 ①如果这个元素不是Comparable则该方法会抛出NoComparableElementException异常 ②如果树为空则这个新元素成为根结点 ③如果树非空这个新元素会与树根元素进行比较 1如果小于根结点中存储的元素且根的左孩子为null则这个元素成为根的左孩子。2如果这个新元素小于根结点中存储的那个元素且根的左孩子不是null则会遍历根的左孩子并再次进行比较操作。3如果这个新元素大于或等于树根存储的那个元素且根的右孩子为null则这个新元素会成为根的右孩子。4如果这个新元素大于或等于树根处存储的那个元素且根的右孩子不是null则会遍历根的右孩子并再次进行比较操作。 代码实现 public void addElement(T element) {if (!(element instanceof Comparable))throw new NonComparableElementException(LinkedBinarySearchTree);ComparableT comparableElement (ComparableT)element;if (isEmpty())root new BinaryTreeNodeT(element);else {if (comparableElement.compareTo(root.getElement()) 0){if (root.getLeft() null) this.getRootNode().setLeft(new BinaryTreeNodeT(element));elseaddElement(element, root.getLeft());}else{if (root.getRight() null) this.getRootNode().setRight(new BinaryTreeNodeT(element));elseaddElement(element, root.getRight());}}modCount;}private void addElement(T element, BinaryTreeNodeT node) {ComparableT comparableElement (ComparableT)element;if (comparableElement.compareTo(node.getElement()) 0){if (node.getLeft() null) node.setLeft(new BinaryTreeNodeT(element));elseaddElement(element, node.getLeft());}else{if (node.getRight() null) node.setRight(new BinaryTreeNodeT(element));elseaddElement(element, node.getRight());}} 6.removeElement操作必须推选出另一个结点来代替要被删除的那个结点 ①找不到给定目标元素时抛出ElementNotFoundException异常。 ②如果被删除结点没有孩子则replacement返回null。 ③如果被删除结点只有一个孩子则replacement返回这个孩子。 ④如果被删除结点有两个孩子则replacement会返回中序后继者因为相等元素会放到右边代码实现 public T removeElement(T targetElement) throws ElementNotFoundException {T result null;if (isEmpty())throw new ElementNotFoundException(LinkedBinarySearchTree);else{BinaryTreeNodeT parent null;if (((ComparableT)targetElement).equals(root.element)) {result root.element;BinaryTreeNodeT temp replacement(root);if (temp null)root null;else {root.element temp.element;root.setRight(temp.right);root.setLeft(temp.left);}modCount--;}else { parent root;if (((Comparable)targetElement).compareTo(root.element) 0)result removeElement(targetElement, root.getLeft(), parent);elseresult removeElement(targetElement, root.getRight(), parent);}}return result;}private T removeElement(T targetElement, BinaryTreeNodeT node, BinaryTreeNodeT parent) throws ElementNotFoundException {T result null;if (node null)throw new ElementNotFoundException(LinkedBinarySearchTree);else{if (((ComparableT)targetElement).equals(node.element)) {result node.element;BinaryTreeNodeT temp replacement(node);if (parent.right node)parent.right temp;else parent.left temp;modCount--;}else { parent node;if (((Comparable)targetElement).compareTo(node.element) 0)result removeElement(targetElement, node.getLeft(), parent);elseresult removeElement(targetElement, node.getRight(), parent);}}return result;}private BinaryTreeNodeT replacement(BinaryTreeNodeT node) {BinaryTreeNodeT result null;if ((node.left null) (node.right null))result null;else if ((node.left ! null) (node.right null))result node.left;else if ((node.left null) (node.right ! null))result node.right;else{BinaryTreeNodeT current node.right;BinaryTreeNodeT parent node;while (current.left ! null){parent current;current current.left;}current.left node.left;if (node.right ! current){parent.left current.right;current.right node.right;}result current;}return result;} 7.removeAllOccurrences操作使用了contains方法find方法被重载以便利用二叉查找树的有序属性。 ①当在树中找不到指定元素时则抛出ElementNotFoundException异常 ②如果指定的元素不是Comparable则该方法也会抛出ClassCastException异常。 ③只要树中还含有目标元素就会再次调用removeElement方法。代码实现public void removeAllOccurrences(T targetElement)throws ElementNotFoundException {removeElement(targetElement);try{while (contains((T)targetElement))removeElement(targetElement);}catch (Exception ElementNotFoundException){}} 8.removeMin操作 ①如果树根没有左孩子则树根就是最小元素而树根的右孩子会变成新的根结点。 ②如果树的最左侧结点是一片叶子则这片叶子就是最小元素这时只需设置其父结点的左孩子引用为null即可。 ③如果树的最左侧结点是一个内部结点则需要设置其父结点的左孩子引用指向这个将删除结点的右孩子。代码实现 public T removeMin() throws EmptyCollectionException {T result null;if (isEmpty())throw new EmptyCollectionException(LinkedBinarySearchTree);else {if (root.left null) {result root.element;root root.right;}else {BinaryTreeNodeT parent root;BinaryTreeNodeT current root.left;while (current.left ! null) {parent current;current current.left;}result current.element;parent.left current.right;}modCount--;}return result;} 9.用有序列表实现二叉查找树实现ListADT接口和OrderedListADT接口。10.BinarySearchTreeList实现的分析add操作与remove操作都要求重新平衡化树。11.树实现中的有些操作更为有效有些操作更为低效。12.蜕化树无分支的树效率比链表还低13.平衡树的方法 1右旋左子树长①使树根的左孩子元素成为新的根元素。②使原根元素成为这个新树根的右孩子元素。③使原树根的左孩子的右孩子成为原树根的新的左孩子。2左旋右子树长①使树根的右孩子元素成为新的根元素。②使原根元素成为这个新树根的左孩子元素。③使原树根右孩子结点的左孩子成为原树根的新的右孩子。3右左旋树根右孩子的左子树长①让树根右孩子的左孩子绕着树根的右孩子进行一次右旋。②让所得的树根右孩子绕着树根进行一次左旋。4左右旋树根左孩子的右子树长①让树根左孩子的右孩子绕着树根的左孩子进行一次左旋。②让所得的树根左孩子绕着树根进行一次右旋。14.实现二叉查找树①AVL树。②红黑树。自树根而下的路径最大长度必须不超过log2 n而且自树根而下的路径最小长度必须不小于log2 n -115.平衡因子右子树的高度减去左子树的高度16.使树变得不平衡有两种方法①插入结点。②删除结点。17.AVL树的右旋由下图可知我们是在结点T的左结点的左子树上做了插入元素的操作我们称这种情况为左左情况我们应该进行右旋转(只需旋转一次故是单旋转)【步骤与右旋步骤一样】 过程 18.AVL树的左旋由下图可知我们是在结点T的右结点的右子树上做了插入元素的操作我们称这种情况为右右情况我们应该进行左旋转(只需旋转一次故是单旋转)【步骤与左旋步骤一样】 过程 19.AVL树的左右(先左后右)旋如下图只是单纯的进行一次旋转得到的树仍然是不平衡的。所以应该进行二次旋转。 20.AVL树的右左(先右后左)旋如下图只是单纯的进行一次旋转得到的树仍然是不平衡的。所以应该进行二次旋转。 21.红黑树每个结点存出一种颜色(红色或黑色通常用一个布尔值来实现false等价于红色) 红黑树的特性:(1) 每个节点或者是黑色或者是红色。(2) 根节点是黑色。(3) 每个叶子节点是黑色。 [注意这里叶子节点是指为空的叶子节点](4) 如果一个节点是红色的则它的子节点必须是黑色的。(5) 从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。22.红黑树的元素添加及删除。教材学习中的问题和解决过程 问题1replacement会返回中序后继者的中序后继者是什么东西问题1解决方案从被删除的结点出发经过它的右结点然后右结点最左边的叶子结点就是中序后继结点。 public Node getSuccessor(Node delNode){ //参数为被删除的节点 //定义一个当前节点的引用直接让往下走一步走到被删除节点的右节点 Node currdelNode.right; Node successorcurr; //用来指向中级后续节点 Node sucParentnull; //用来指向中级后续节点的父节点 while(curr!null){ sucParentsuccessor; successorcurr; currcurr.left; } //循环停止中级后续节点被找出 if(successor!delNode.right){ //将后继节点的子节点只可能有右节点替补到后继节点的位置上 sucParent.leftsuccessor.right; //将被删除的右孩子连接到后继节点的右节点上 successor.rightdelNode.right; //将被删除的左孩子连接到后继节点的右节点上就是用后继节点替换掉被删除的节点 } return successor; } 问题引申为什么要找中序后继者作为代替删除结点的位置。问题引申解决方案如果直接删结点整个树的大小顺序就乱了所以需要考虑在树中找到一个合适的节点来把这个结点给替换掉用这种方法来保持整个树的稳定。需要在树中找出所有比被删除节点的值大的所有数并在这些数中找出一个最小的数来。问题2AVL树的作用。问题2解决方案删除时树的平衡性受到破坏提高它的操作的时间复杂度。而AVL树就不会出现这种情况树的高度始终是O(lgN).高度越小对树的一些基本操作的时间复杂度就会越小。代码调试中的问题和解决过程 问题1红黑树的元素添加。问题1解决方案 步骤1将红黑树当作一颗二叉查找树将节点插入。步骤2将插入的节点着色为红色。步骤3通过一系列的旋转或着色等操作使之重新成为一颗红黑树。 private void insert(RBTNodeT node) {int cmp;RBTNodeT y null;RBTNodeT x this.mRoot;// 1. 将红黑树当作一颗二叉查找树将节点添加到二叉查找树中。while (x ! null) {y x;cmp node.key.compareTo(x.key);if (cmp 0)x x.left;elsex x.right;}node.parent y;if (y!null) {cmp node.key.compareTo(y.key);if (cmp 0)y.left node;elsey.right node;} else {this.mRoot node;}// 2. 设置节点的颜色为红色node.color RED;// 3. 将它重新修正为一颗二叉查找树insertFixUp(node);}/* * 新建结点(key)并将其插入到红黑树中** 参数说明* key 插入结点的键值*/public void insert(T key) {RBTNodeT nodenew RBTNodeT(key,BLACK,null,null,null);// 如果新建结点失败则返回。if (node ! null)insert(node);}问题2红黑树的元素删除。问题2解决方案 步骤1将红黑树当作一颗二叉查找树将节点删除。步骤2通过旋转和重新着色等一系列来修正该树使之重新成为一棵红黑树。 /* * 删除结点(node)并返回被删除的结点** 参数说明* node 删除的结点*/private void remove(RBTNodeT node) {RBTNodeT child, parent;boolean color;// 被删除节点的左右孩子都不为空的情况。if ( (node.left!null) (node.right!null) ) {// 被删节点的后继节点。(称为取代节点)// 用它来取代被删节点的位置然后再将被删节点去掉。RBTNodeT replace node;// 获取后继节点replace replace.right;while (replace.left ! null)replace replace.left;// node节点不是根节点(只有根节点不存在父节点)if (parentOf(node)!null) {if (parentOf(node).left node)parentOf(node).left replace;elseparentOf(node).right replace;} else {// node节点是根节点更新根节点。this.mRoot replace;}// child是取代节点的右孩子也是需要调整的节点。// 取代节点肯定不存在左孩子因为它是一个后继节点。child replace.right;parent parentOf(replace);// 保存取代节点的颜色color colorOf(replace);// 被删除节点是它的后继节点的父节点if (parent node) {parent replace;} else {// child不为空if (child!null)setParent(child, parent);parent.left child;replace.right node.right;setParent(node.right, replace);}replace.parent node.parent;replace.color node.color;replace.left node.left;node.left.parent replace;if (color BLACK)removeFixUp(child, parent);node null;return ;}if (node.left !null) {child node.left;} else {child node.right;}parent node.parent;// 保存取代节点的颜色color node.color;if (child!null)child.parent parent;// node节点不是根节点if (parent!null) {if (parent.left node)parent.left child;elseparent.right child;} else {this.mRoot child;}if (color BLACK)removeFixUp(child, parent);node null;}/* * 删除结点(z)并返回被删除的结点** 参数说明* tree 红黑树的根结点* z 删除的结点*/public void remove(T key) {RBTNodeT node; if ((node search(mRoot, key)) ! null)remove(node); }问题3按着书上讲的左旋右旋步骤来做会出现错误 问题3解决方案问题代码的过程为下图很显然出现了覆盖结点导致丢失结点的问题。 改正 过程 代码托管 上周考试错题总结 无。点评过的同学博客和代码 本周结对学习情况 2017232620172313结对学习内容 教材第11章上周博客互评情况 2017232620172313其他感悟、思考等可选 查找二叉树是二叉树的引申学习难度真的很大学习进度条 代码行数新增/累积博客量新增/累积学习时间新增/累积重要成长目标5000行30篇400小时第一周0/01/12/2第二周1010/10101/210/12第三周651/16611/313/25第四周2205/38661/415/40第五周967/48332/622/62第六周1680/65131/734/96第七周2196/87091/835/131计划学习时间:30小时实际学习时间:35小时改进情况AVL树和红黑树真的耗费了大量的时间参考资料 Java软件结构与数据结构(第4版)图解数据结构树之AVL树红黑树(五)之 Java的实现平衡二叉搜索树AVL树的原理及实现源代码有图文详解和C、Java实现代码转载于:https://www.cnblogs.com/yu757503836/p/9873494.html
