學號 20172326 《程序設計與數據結構》第六周學習總結

教材學習內容總結

非線性數據結構——樹

• 結點：結點分為根節點，內部結點。根據結點分為parent和children,結點之上為parent，之下為children。位于同一結點的下的結點為sibling。
• order（度）：每個結點所擁有的最大children數，根據此定義，較為常見的二叉樹得以命名。

• 分類：1.平衡樹，所有葉子位于同一層或者至少彼此相差不超過一層。2.完全樹，在平衡的基礎上，底層所有葉子位于樹的左邊。3.滿樹，對于一個n元樹，每層葉子都是滿的，且均在同一層。

  實現樹的方法。

• 1.使用鏈表。
• 因為樹的數據結構，每個結點指向其孩子，因此使用鏈表較為簡單。
• 2.使用數組。
• • 根據二叉樹的特殊性質，將左孩子存在數組（2 * n - 1 ） 索引值處，右孩子在（2 * n+1））處。但問題在于，當出現非滿樹的情況時，數組中的某些位置就必須空下以表示某parent只有一個孩子，當一個樹大量存在這種情況時，將浪費大量的空間。

• • 模擬鏈接法。創建一個node型數組，使得每個元素存儲下一個children的地址。問題，當刪除一個結點時，如果不保留原結點位置，子結點移動時將會非常麻煩。如果只將其內部元素刪除，保留內部結點的引用關系，又會占用空間。

    樹的遍歷

• 前序遍歷，中序遍歷，后序遍歷，層序遍歷
• 前序遍歷。從根節點開始，依次遍歷至葉子處的左孩子，再依次由下至上返回由孩子。直到將整個樹遍歷完成。
  
• 中序遍歷。從根結點開始。（注意，此時的從根節點開始并不是說第一個也就是根節點開始，而是從根節點到最后一個最左葉結點方向）從最左葉節點開始，至其parent結點，再至其右孩子。以此為規律，遍歷整個樹。
  
• 后序遍歷。和中序遍歷相同，從最左葉結點開始，然后至其兄弟結點。再至其parent結點。以此為規律，遞歸。
  

• 層序遍歷。顧名思義，一層一層的遍歷。從根節點開始。直到最后一層。
  

二叉樹

• 二叉樹。一個結點最多只有兩個孩子。
• 二叉查找樹。左孩子始終小于雙親，而雙親始終小于等于右孩子
• 二叉樹的性質。
• • 若根結點的層次為1，則二叉樹第i層最多有
    2^(i-1)(i>=1)個結點。
• • 在高度為h的二叉樹中，最多有

2^h-1

個結點

教材學習中的問題和解決過程

• 問題1：對平衡二叉查找樹的理解探究
• 問題1理解：
• 平衡樹的定義：它是一 棵空樹或它的左右兩個子樹的高度差的絕對值不超過1，并且左右兩個子樹都是一棵平衡二叉樹。從這定義就可以看出具有遞歸的思想。
• 為什么需要使用二叉樹？樹作為一種非線性結構，并不以線性方式存儲數據，這樣一來，尤其是對于查找效率，將大大提高（從O(n)到O(logn)）。但當出現一些極端例子時，樹的優勢將不復存在，如圖。

此時將一個順序列表存入其中，樹變為了右單子樹或左單子樹。問題出現了，此時的樹直接變成了列表，查找效率也從O(logn)變為O(n)。為了解決這個問題，我們引入了平衡樹的概念。如此，對于以無論何種順序存入樹的元素，不至于存的太深。在各個子樹最多只能相差一的限制下，樹的優勢得以保留。

• 問題2：本章內容出現許多的迭代器與迭代器方法，對迭代器的探究。
• 問題2理解：
• 首先明確迭代的意義是什么。迭代是重復反饋過程的活動，其目的通常是為了逼近所需目標或結果。每一次對過程的重復稱為一次“迭代”，而每一次迭代得到的結果會作為下一次迭代的初始值。
• 從概念上來看，迭代似乎與遞歸十分相似，都有著重復的過程。那么區別在哪呢？遞歸，簡單的來說，就是自己調用自己，直到到達限制條件。遞歸并不是這樣，遞歸通常有一個計數器，也就是通過循環不斷進行計算，循環什么時候截止呢？在達到計數器時，結束循環。通過之前的代碼可以知道，同一問題，遞歸實現的代碼十分簡潔可讀。但循環體則較為復雜，對于一個復雜問題，短時間不易理解。但遞歸在帶來代碼簡潔的同時，執行代碼時將占用大量內存，稍有不慎會使得棧溢出，拋出異常。迭代則不會這樣。
• 現在回到迭代器（Iterator）。內部有三個方法。hasnext，next，remove通過重寫這三個方法，使得在不破壞內部結構的情況下，返回出內部的數據。

代碼調試中的問題和解決過程

• 問題1：對于樹中removeSubtree的方法
• 問題1解決方案：首先，明確要求，刪除某一個右子樹，直接將其設為null即可。問題在于，如何找到對應的右子樹。是根據對應的那個元素判定還是對應的結點？其實都可以，代碼如下：

if (next == null)return null;if (next.getElement().equals(targetElement))return next;BinaryTreeNode<T> temp = findNode(targetElement, next.getLeft());if (temp == null)temp = findNode(targetElement, next.getRight());return temp; BinaryTreeNode<T> current = findNode(targetElement, root);if (current == null)throw new ElementNotFoundException("LinkedBinaryTree");return (current.getElement());

分別鎖定了對應的位置和結點。因此任意調用這兩個方法之一，即可找出相應的右子樹。從而將其刪除。刪除時，將對應結點視為樹的根，直接將根所在的LinkedBinary樹等于null即可。

• 問題2：在測試contain方法時出現了異常的問題
• 問題2解決方案：測試之前，還出現了一段小插曲。如圖，
  

顯示了報錯，同時無法執行代碼。反復嘗試無果后，發現之前使用棧實現了一個Postfixtest，而本章也有一個使用數實現的計算后綴表達式的程序，在將其重名的改名后，重啟了幾次idea后，如愿恢復了正常。我的理解是，首先idea必須保證所有程序不出錯，否則其他程序編譯將無法通過，同時，對于兩個同名程序，無法判斷執行哪個，因此選擇不執行，知道將其改變。

• 根據拋出異常顯示的位置，發現是removeSubRighttree出了問題，

可是，拋出的是空指針異常，也就是并未找到所要刪除的結點。所以問題不在這里。在于findnode方法，在方法體，我設置傳入了一個的LinkedBinary的參數，但是，該樹此時為空，自然將導致其為空指針。

• 解決了這個問題，再到contain方法，又出現了問題。依舊為空，仔細比對，發現了問題。在方法頭，重新實例化了一個LinkedBinary對象，但是，其實樹已經在之前方法確定，重新實例化反而相當于將其清空，造成空指針的情況。

  代碼托管

結對及互評

• 博客中值得學習的或問題：
  排版精美，對于問題研究得很細致，解答也很周全。
• 代碼中值得學習的或問題：
  代碼寫的很規范，思路很清晰，繼續加油！

點評過的同學博客和代碼

• 本周結對學習情況
• 20172313

• 20172332

  結對學習內容

• 第十章 樹

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

• 第一次學習非線性數據結構，對于某些知識還不是很了解，將繼續對這些展開學習

  學習進度條

  代碼行數（新增/累積）博客量（新增/累積）學習時間（新增/累積）重要成長

  目標	5000行	30篇	400小時
  第一周	0/0	1/1	3/3
  第二周	409/409	1/2	5/8
  第三周	1174/1583	1/3	10/18
  第四周	1843/3426	2/5	10/28
  第五周	539/3965	2/7	20/48
  第六周	965/4936	1/8	20/68

參考資料

• 二叉查找樹的刪除算法的設計與實現遞歸與非遞歸
• 圖解數據結構二叉樹遍歷

轉載于:https://www.cnblogs.com/326477465-a/p/9853406.html

總結

以上是生活随笔為你收集整理的20172326 《程序设计与数据结构》第六周学习总结的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。