當(dāng)前位置：首頁(yè) > 编程资源 > 编程问答 >内容正文

编程问答

20172332 2017-2018-2 《程序设计与数据结构》第七周学习总结

發(fā)布時(shí)間：2025/3/15 编程问答 15 豆豆

生活随笔收集整理的這篇文章主要介紹了 20172332 2017-2018-2 《程序设计与数据结构》第七周学习总结小編覺得挺不錯(cuò)的,現(xiàn)在分享給大家,幫大家做個(gè)參考.

20172332 2017-2018-2 《程序設(shè)計(jì)與數(shù)據(jù)結(jié)構(gòu)》第七周學(xué)習(xí)總結(jié)

教材學(xué)習(xí)內(nèi)容總結(jié)

第十一章二叉查找樹

1.二叉查找樹：一種帶有附加屬性的二叉樹。即每個(gè)結(jié)點(diǎn)其左孩子都要小于其父結(jié)點(diǎn)，而父結(jié)點(diǎn)又小于或等于其右孩子。（左孩子<父結(jié)點(diǎn)<=右孩子）
2.二叉查找樹不僅具有二叉樹的操作，還具有以下的特殊操作：
3.用鏈表實(shí)現(xiàn)二叉查找樹：每個(gè)BinaryTreeNode對(duì)象要維護(hù)一個(gè)指向結(jié)點(diǎn)所存儲(chǔ)元素的引用，另外還要維護(hù)指向結(jié)點(diǎn)的每個(gè)孩子的引用。
4.二叉查找樹的構(gòu)造函數(shù)代碼（引用了父類的兩個(gè)構(gòu)造函數(shù)）：

public LinkedBinarySearchTree() {super();}public LinkedBinarySearchTree(T element) {super(element);if (!(element instanceof Comparable))throw new NonComparableElementException("LinkedBinarySearchTree");}

5.addElement操作：
①如果這個(gè)元素不是Comparable，則該方法會(huì)拋出NoComparableElementException異常；
②如果樹為空，則這個(gè)新元素成為根結(jié)點(diǎn)；
③如果樹非空，這個(gè)新元素會(huì)與樹根元素進(jìn)行比較，
- （1）如果小于根結(jié)點(diǎn)中存儲(chǔ)的元素且根的左孩子為null，則這個(gè)元素成為根的左孩子。
- （2）如果這個(gè)新元素小于根結(jié)點(diǎn)中存儲(chǔ)的那個(gè)元素且根的左孩子不是null，則會(huì)遍歷根的左孩子并再次進(jìn)行比較操作。
- （3）如果這個(gè)新元素大于或等于樹根存儲(chǔ)的那個(gè)元素且根的右孩子為null，則這個(gè)新元素會(huì)成為根的右孩子。
- （4）如果這個(gè)新元素大于或等于樹根處存儲(chǔ)的那個(gè)元素且根的右孩子不是null，則會(huì)遍歷根的右孩子，并再次進(jìn)行比較操作。
代碼實(shí)現(xiàn)：

public void addElement(T element) {if (!(element instanceof Comparable))throw new NonComparableElementException("LinkedBinarySearchTree");Comparable<T> comparableElement = (Comparable<T>)element;if (isEmpty())root = new BinaryTreeNode<T>(element);else {if (comparableElement.compareTo(root.getElement()) < 0){if (root.getLeft() == null) this.getRootNode().setLeft(new BinaryTreeNode<T>(element));elseaddElement(element, root.getLeft());}else{if (root.getRight() == null) this.getRootNode().setRight(new BinaryTreeNode<T>(element));elseaddElement(element, root.getRight());}}modCount++;}private void addElement(T element, BinaryTreeNode<T> node) {Comparable<T> comparableElement = (Comparable<T>)element;if (comparableElement.compareTo(node.getElement()) < 0){if (node.getLeft() == null) node.setLeft(new BinaryTreeNode<T>(element));elseaddElement(element, node.getLeft());}else{if (node.getRight() == null) node.setRight(new BinaryTreeNode<T>(element));elseaddElement(element, node.getRight());}}

6.removeElement操作：（必須推選出另一個(gè)結(jié)點(diǎn)來(lái)代替要被刪除的那個(gè)結(jié)點(diǎn)）
①找不到給定目標(biāo)元素時(shí)，拋出ElementNotFoundException異常。
②如果被刪除結(jié)點(diǎn)沒有孩子，則replacement返回null。
③如果被刪除結(jié)點(diǎn)只有一個(gè)孩子，則replacement返回這個(gè)孩子。
④如果被刪除結(jié)點(diǎn)有兩個(gè)孩子，則replacement會(huì)返回中序后繼者（因?yàn)橄嗟仍貢?huì)放到右邊）
代碼實(shí)現(xiàn)：

public T removeElement(T targetElement) throws ElementNotFoundException {T result = null;if (isEmpty())throw new ElementNotFoundException("LinkedBinarySearchTree");else{BinaryTreeNode<T> parent = null;if (((Comparable<T>)targetElement).equals(root.element)) {result = root.element;BinaryTreeNode<T> 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, BinaryTreeNode<T> node, BinaryTreeNode<T> parent) throws ElementNotFoundException {T result = null;if (node == null)throw new ElementNotFoundException("LinkedBinarySearchTree");else{if (((Comparable<T>)targetElement).equals(node.element)) {result = node.element;BinaryTreeNode<T> 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 BinaryTreeNode<T> replacement(BinaryTreeNode<T> node) {BinaryTreeNode<T> 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{BinaryTreeNode<T> current = node.right;BinaryTreeNode<T> 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方法被重載以便利用二叉查找樹的有序?qū)傩浴?#xff09;
①當(dāng)在樹中找不到指定元素時(shí)，則拋出ElementNotFoundException異常
②如果指定的元素不是Comparable，則該方法也會(huì)拋出ClassCastException異常。
③只要樹中還含有目標(biāo)元素，就會(huì)再次調(diào)用removeElement方法。
代碼實(shí)現(xiàn)：

public void removeAllOccurrences(T targetElement)throws ElementNotFoundException {removeElement(targetElement);try{while (contains((T)targetElement))removeElement(targetElement);}catch (Exception ElementNotFoundException){}}

8.removeMin操作：
①如果樹根沒有左孩子，則樹根就是最小元素，而樹根的右孩子會(huì)變成新的根結(jié)點(diǎn)。
②如果樹的最左側(cè)結(jié)點(diǎn)是一片葉子，則這片葉子就是最小元素，這時(shí)只需設(shè)置其父結(jié)點(diǎn)的左孩子引用為null即可。
③如果樹的最左側(cè)結(jié)點(diǎn)是一個(gè)內(nèi)部結(jié)點(diǎn)，則需要設(shè)置其父結(jié)點(diǎn)的左孩子引用指向這個(gè)將刪除結(jié)點(diǎn)的右孩子。
代碼實(shí)現(xiàn)：

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 {BinaryTreeNode<T> parent = root;BinaryTreeNode<T> current = root.left;while (current.left != null) {parent = current;current = current.left;}result = current.element;parent.left = current.right;}modCount--;}return result;}

9.用有序列表實(shí)現(xiàn)二叉查找樹：實(shí)現(xiàn)ListADT接口和OrderedListADT接口。
10.BinarySearchTreeList實(shí)現(xiàn)的分析：add操作與remove操作都要求重新平衡化樹。
11.樹實(shí)現(xiàn)中的有些操作更為有效，有些操作更為低效。
12.蛻化樹：無(wú)分支的樹（效率比鏈表還低）
13.平衡樹的方法：
- （1）右旋（左子樹長(zhǎng)）：①使樹根的左孩子元素成為新的根元素。②使原根元素成為這個(gè)新樹根的右孩子元素。③使原樹根的左孩子的右孩子，成為原樹根的新的左孩子。
- （2）左旋（右子樹長(zhǎng)）：①使樹根的右孩子元素成為新的根元素。②使原根元素成為這個(gè)新樹根的左孩子元素。③使原樹根右孩子結(jié)點(diǎn)的左孩子，成為原樹根的新的右孩子。
- （3）右左旋（樹根右孩子的左子樹長(zhǎng)）：①讓樹根右孩子的左孩子，繞著樹根的右孩子進(jìn)行一次右旋。②讓所得的樹根右孩子繞著樹根進(jìn)行一次左旋。
- （4）左右旋（樹根左孩子的右子樹長(zhǎng)）：①讓樹根左孩子的右孩子繞著樹根的左孩子進(jìn)行一次左旋。②讓所得的樹根左孩子繞著樹根進(jìn)行一次右旋。
14.實(shí)現(xiàn)二叉查找樹：①AVL樹。②紅黑樹。（自樹根而下的路徑最大長(zhǎng)度必須不超過log2 n，而且自樹根而下的路徑最小長(zhǎng)度必須不小于log2 n -1）
15.平衡因子：右子樹的高度減去左子樹的高度
16.使樹變得不平衡有兩種方法：①插入結(jié)點(diǎn)。②刪除結(jié)點(diǎn)。
17.AVL樹的右旋：由下圖可知我們是在結(jié)點(diǎn)T的左結(jié)點(diǎn)的左子樹上做了插入元素的操作，我們稱這種情況為左左情況，我們應(yīng)該進(jìn)行右旋轉(zhuǎn)(只需旋轉(zhuǎn)一次，故是單旋轉(zhuǎn))【步驟與右旋步驟一樣】
- 過程：
18.AVL樹的左旋：由下圖可知我們是在結(jié)點(diǎn)T的右結(jié)點(diǎn)的右子樹上做了插入元素的操作，我們稱這種情況為右右情況，我們應(yīng)該進(jìn)行左旋轉(zhuǎn)(只需旋轉(zhuǎn)一次，故是單旋轉(zhuǎn))【步驟與左旋步驟一樣】
- 過程：
19.AVL樹的左右(先左后右)旋：如下圖，只是單純的進(jìn)行一次旋轉(zhuǎn)，得到的樹仍然是不平衡的。所以應(yīng)該進(jìn)行二次旋轉(zhuǎn)。
20.AVL樹的右左(先右后左)旋：如下圖，只是單純的進(jìn)行一次旋轉(zhuǎn)，得到的樹仍然是不平衡的。所以應(yīng)該進(jìn)行二次旋轉(zhuǎn)。
21.紅黑樹：每個(gè)結(jié)點(diǎn)存出一種顏色(紅色或黑色，通常用一個(gè)布爾值來(lái)實(shí)現(xiàn)，false等價(jià)于紅色)
- 紅黑樹的特性:
- (1) 每個(gè)節(jié)點(diǎn)或者是黑色，或者是紅色。
- (2) 根節(jié)點(diǎn)是黑色。
- (3) 每個(gè)葉子節(jié)點(diǎn)是黑色。 [注意：這里葉子節(jié)點(diǎn)，是指為空的葉子節(jié)點(diǎn)！]
- (4) 如果一個(gè)節(jié)點(diǎn)是紅色的，則它的子節(jié)點(diǎn)必須是黑色的。
- (5) 從一個(gè)節(jié)點(diǎn)到該節(jié)點(diǎn)的子孫節(jié)點(diǎn)的所有路徑上包含相同數(shù)目的黑節(jié)點(diǎn)。
22.紅黑樹的元素添加及刪除。

教材學(xué)習(xí)中的問題和解決過程

問題1：replacement會(huì)返回中序后繼者的中序后繼者是什么東西？
問題1解決方案：從被刪除的結(jié)點(diǎn)出發(fā)經(jīng)過它的右結(jié)點(diǎn)，然后右結(jié)點(diǎn)最左邊的葉子結(jié)點(diǎn)就是中序后繼結(jié)點(diǎn)。

public Node getSuccessor(Node delNode){ //參數(shù)為被刪除的節(jié)點(diǎn) //定義一個(gè)當(dāng)前節(jié)點(diǎn)的引用，直接讓往下走一步，走到被刪除節(jié)點(diǎn)的右節(jié)點(diǎn) Node curr=delNode.right; Node successor=curr; //用來(lái)指向中級(jí)后續(xù)節(jié)點(diǎn) Node sucParent=null; //用來(lái)指向中級(jí)后續(xù)節(jié)點(diǎn)的父節(jié)點(diǎn) while(curr!=null){ sucParent=successor; successor=curr; curr=curr.left; } //循環(huán)停止，中級(jí)后續(xù)節(jié)點(diǎn)被找出 if(successor!=delNode.right){ //將后繼節(jié)點(diǎn)的子節(jié)點(diǎn)（只可能有右節(jié)點(diǎn)）替補(bǔ)到后繼節(jié)點(diǎn)的位置上 sucParent.left=successor.right; //將被刪除的右孩子連接到后繼節(jié)點(diǎn)的右節(jié)點(diǎn)上 successor.right=delNode.right; //將被刪除的左孩子連接到后繼節(jié)點(diǎn)的右節(jié)點(diǎn)上（就是用后繼節(jié)點(diǎn)替換掉被刪除的節(jié)點(diǎn)） } return successor; }

問題引申：為什么要找中序后繼者作為代替刪除結(jié)點(diǎn)的位置。
問題引申解決方案：如果直接刪結(jié)點(diǎn)，整個(gè)樹的大小順序就亂了，所以需要考慮，在樹中找到一個(gè)合適的節(jié)點(diǎn)來(lái)把這個(gè)結(jié)點(diǎn)給替換掉，用這種方法來(lái)保持整個(gè)樹的穩(wěn)定。需要在樹中找出所有比被刪除節(jié)點(diǎn)的值大的所有數(shù)，并在這些數(shù)中找出一個(gè)最小的數(shù)來(lái)。
問題2：AVL樹的作用。
問題2解決方案：刪除時(shí)樹的平衡性受到破壞，提高它的操作的時(shí)間復(fù)雜度。而AVL樹就不會(huì)出現(xiàn)這種情況，樹的高度始終是O(lgN).高度越小，對(duì)樹的一些基本操作的時(shí)間復(fù)雜度就會(huì)越小。

代碼調(diào)試中的問題和解決過程

問題1：紅黑樹的元素添加。
問題1解決方案：
- 步驟1：將紅黑樹當(dāng)作一顆二叉查找樹，將節(jié)點(diǎn)插入。
- 步驟2：將插入的節(jié)點(diǎn)著色為"紅色"。
- 步驟3：通過一系列的旋轉(zhuǎn)或著色等操作，使之重新成為一顆紅黑樹。
private void insert(RBTNode<T> node) {int cmp;RBTNode<T> y = null;RBTNode<T> x = this.mRoot;// 1. 將紅黑樹當(dāng)作一顆二叉查找樹，將節(jié)點(diǎn)添加到二叉查找樹中。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. 設(shè)置節(jié)點(diǎn)的顏色為紅色node.color = RED;// 3. 將它重新修正為一顆二叉查找樹insertFixUp(node);}/* * 新建結(jié)點(diǎn)(key)，并將其插入到紅黑樹中** 參數(shù)說明：* key 插入結(jié)點(diǎn)的鍵值*/public void insert(T key) {RBTNode<T> node=new RBTNode<T>(key,BLACK,null,null,null);// 如果新建結(jié)點(diǎn)失敗，則返回。if (node != null)insert(node);}
問題2：紅黑樹的元素刪除。
問題2解決方案：
- 步驟1：將紅黑樹當(dāng)作一顆二叉查找樹，將節(jié)點(diǎn)刪除。
- 步驟2：通過"旋轉(zhuǎn)和重新著色"等一系列來(lái)修正該樹，使之重新成為一棵紅黑樹。
/* * 刪除結(jié)點(diǎn)(node)，并返回被刪除的結(jié)點(diǎn)** 參數(shù)說明：* node 刪除的結(jié)點(diǎn)*/private void remove(RBTNode<T> node) {RBTNode<T> child, parent;boolean color;// 被刪除節(jié)點(diǎn)的"左右孩子都不為空"的情況。if ( (node.left!=null) && (node.right!=null) ) {// 被刪節(jié)點(diǎn)的后繼節(jié)點(diǎn)。(稱為"取代節(jié)點(diǎn)")// 用它來(lái)取代"被刪節(jié)點(diǎn)"的位置，然后再將"被刪節(jié)點(diǎn)"去掉。RBTNode<T> replace = node;// 獲取后繼節(jié)點(diǎn)replace = replace.right;while (replace.left != null)replace = replace.left;// "node節(jié)點(diǎn)"不是根節(jié)點(diǎn)(只有根節(jié)點(diǎn)不存在父節(jié)點(diǎn))if (parentOf(node)!=null) {if (parentOf(node).left == node)parentOf(node).left = replace;elseparentOf(node).right = replace;} else {// "node節(jié)點(diǎn)"是根節(jié)點(diǎn)，更新根節(jié)點(diǎn)。this.mRoot = replace;}// child是"取代節(jié)點(diǎn)"的右孩子，也是需要"調(diào)整的節(jié)點(diǎn)"。// "取代節(jié)點(diǎn)"肯定不存在左孩子！因?yàn)樗且粋€(gè)后繼節(jié)點(diǎn)。child = replace.right;parent = parentOf(replace);// 保存"取代節(jié)點(diǎn)"的顏色color = colorOf(replace);// "被刪除節(jié)點(diǎn)"是"它的后繼節(jié)點(diǎn)的父節(jié)點(diǎn)"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;// 保存"取代節(jié)點(diǎn)"的顏色color = node.color;if (child!=null)child.parent = parent;// "node節(jié)點(diǎn)"不是根節(jié)點(diǎn)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;}/* * 刪除結(jié)點(diǎn)(z)，并返回被刪除的結(jié)點(diǎn)** 參數(shù)說明：* tree 紅黑樹的根結(jié)點(diǎn)* z 刪除的結(jié)點(diǎn)*/public void remove(T key) {RBTNode<T> node; if ((node = search(mRoot, key)) != null)remove(node); }
問題3：按著書上講的左旋右旋步驟來(lái)做，會(huì)出現(xiàn)錯(cuò)誤
問題3解決方案：
問題代碼的過程為下圖，很顯然出現(xiàn)了覆蓋結(jié)點(diǎn)，導(dǎo)致丟失結(jié)點(diǎn)的問題。
改正：
過程：

代碼托管

上周考試錯(cuò)題總結(jié)

無(wú)。

點(diǎn)評(píng)過的同學(xué)博客和代碼

本周結(jié)對(duì)學(xué)習(xí)情況
- 20172326
- 20172313
- 結(jié)對(duì)學(xué)習(xí)內(nèi)容
  - 教材第11章
上周博客互評(píng)情況
- 20172326
- 20172313

其他（感悟、思考等，可選）

查找二叉樹是二叉樹的引申學(xué)習(xí)，難度真的很大！

學(xué)習(xí)進(jìn)度條

代碼行數(shù)（新增/累積）博客量（新增/累積）學(xué)習(xí)時(shí)間（新增/累積）重要成長(zhǎng)

目標(biāo)	5000行	30篇	400小時(shí)
第一周	0/0	1/1	2/2
第二周	1010/1010	1/2	10/12
第三周	651/1661	1/3	13/25
第四周	2205/3866	1/4	15/40
第五周	967/4833	2/6	22/62
第六周	1680/6513	1/7	34/96
第七周	2196/8709	1/8	35/131

計(jì)劃學(xué)習(xí)時(shí)間:30小時(shí)
實(shí)際學(xué)習(xí)時(shí)間:35小時(shí)
改進(jìn)情況：AVL樹和紅黑樹真的耗費(fèi)了大量的時(shí)間！

參考資料

Java軟件結(jié)構(gòu)與數(shù)據(jù)結(jié)構(gòu)(第4版)
圖解數(shù)據(jù)結(jié)構(gòu)樹之AVL樹
紅黑樹(五)之 Java的實(shí)現(xiàn)
平衡二叉搜索樹（AVL樹）的原理及實(shí)現(xiàn)源代碼（有圖文詳解和C++、Java實(shí)現(xiàn)代碼）

轉(zhuǎn)載于:https://www.cnblogs.com/yu757503836/p/9873494.html

總結(jié)

以上是生活随笔為你收集整理的20172332 2017-2018-2 《程序设计与数据结构》第七周学习总结的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。

上一篇： Page9：结构分解以及系统内部稳定和B
下一篇： Chrome Extension Da