一、什么是樹(shù)
樹(shù)是一種類(lèi)似鏈表的數(shù)據(jù)結(jié)構(gòu),不過(guò)鏈表的結(jié)點(diǎn)是以線(xiàn)性方式簡(jiǎn)單地指向其后繼指點(diǎn),而樹(shù)的一個(gè)結(jié)點(diǎn)可以指向許多個(gè)結(jié)點(diǎn)。樹(shù)是一種典型的非線(xiàn)性結(jié)構(gòu)。樹(shù)結(jié)構(gòu)是表達(dá)具有層次特性的圖結(jié)構(gòu)的一種方法。
二、相關(guān)術(shù)語(yǔ)
● 根結(jié)點(diǎn):根結(jié)點(diǎn)就是一個(gè)沒(méi)有雙親結(jié)點(diǎn)的結(jié)點(diǎn)。一棵樹(shù)中最多有一個(gè)根結(jié)點(diǎn)(如圖2-1的結(jié)點(diǎn)A就是根結(jié)點(diǎn))。
● 邊:邊表示從雙親結(jié)點(diǎn)到孩子結(jié)點(diǎn)的鏈接(如圖2-1的所有鏈接)。
● 葉子結(jié)點(diǎn):沒(méi)有孩子結(jié)點(diǎn)的結(jié)點(diǎn)叫做葉子結(jié)點(diǎn)(如圖2-1中的E、J、K、H、I )。
● 兄弟結(jié)點(diǎn):擁有相同的雙親結(jié)點(diǎn)的所有孩子結(jié)點(diǎn)叫做兄弟結(jié)點(diǎn)(如圖2-1中的B、C、D是A的兄弟結(jié)點(diǎn))。
● 祖先結(jié)點(diǎn):如果存在一條從根結(jié)點(diǎn)到q的路徑,且結(jié)點(diǎn)p出現(xiàn)在這條路徑上,那么就可以把p叫做q的祖先結(jié)點(diǎn)(如圖2-1中A、C、G是K的祖先結(jié)點(diǎn))。
● 結(jié)點(diǎn)的大?。航Y(jié)點(diǎn)的大小是指子孫的個(gè)數(shù),包括其自身(如圖2-1中子樹(shù)C的大小為3)。
● 樹(shù)的層:位于相同深度的所有結(jié)點(diǎn)的集合叫做樹(shù)的層(如圖2-2中的1和4具有相同的層)。
● 結(jié)點(diǎn)的深度:是指從根結(jié)點(diǎn)到該結(jié)點(diǎn)的路徑長(zhǎng)度(如圖2-2中的5深度為2,3-4-5)。
● 結(jié)點(diǎn)的高度:是指從結(jié)點(diǎn)到最深結(jié)點(diǎn)的路徑長(zhǎng)度。樹(shù)的高度是指根結(jié)點(diǎn)到樹(shù)中最深結(jié)點(diǎn)的路徑長(zhǎng)度。只含有根結(jié)點(diǎn)的樹(shù)的高度是0(如圖2-2樹(shù)的高度為2)。
● 斜樹(shù):如果樹(shù)中除了葉子結(jié)點(diǎn)外,其余每個(gè)結(jié)點(diǎn)都只有一個(gè)孩子結(jié)點(diǎn),則這種樹(shù)稱(chēng)為斜樹(shù)(如圖2-3)。
三、二叉樹(shù)
如果一棵樹(shù)中的每個(gè)結(jié)點(diǎn)有0、1或2個(gè)孩子結(jié)點(diǎn),那么這個(gè)樹(shù)就稱(chēng)為二叉樹(shù)??諛?shù)也是一棵有效的二叉樹(shù)。一棵二叉樹(shù)可以看作由根結(jié)點(diǎn)和兩棵不相交的子樹(shù)組成,如圖3-1所示。
1. 二叉樹(shù)的類(lèi)型
(1)嚴(yán)格二叉樹(shù):二叉樹(shù)中的每個(gè)結(jié)點(diǎn)要么有兩個(gè)孩子結(jié)點(diǎn),要么沒(méi)有孩子結(jié)點(diǎn)(如圖3-2所示)。
(2)滿(mǎn)二叉樹(shù):二叉樹(shù)的每個(gè)結(jié)點(diǎn)恰好有兩個(gè)孩子結(jié)點(diǎn)且所有葉子結(jié)點(diǎn)在同一層(如圖3-3所示)。
(3)完全二叉樹(shù):假定二叉樹(shù)的高度為h。對(duì)于完全二叉樹(shù),如果將所有結(jié)點(diǎn)從根結(jié)點(diǎn)開(kāi)始從左至右,從上至下,依次編號(hào)(假定根結(jié)點(diǎn)編號(hào)為1),那么將得到從1~n(n為結(jié)點(diǎn)總數(shù))的完整序列。如果所有葉子結(jié)點(diǎn)的深度為h或者h(yuǎn)-1,且結(jié)點(diǎn)在編號(hào)過(guò)程中沒(méi)有漏掉任何數(shù)字,那么就叫做完全二叉樹(shù)(如圖3-4所示)。
2. 二叉樹(shù)的性質(zhì)
假定樹(shù)的高度為h,且根結(jié)點(diǎn)的深度為0。
從圖3-5可得出如下性質(zhì):
(1)滿(mǎn)二叉樹(shù)的結(jié)點(diǎn)個(gè)數(shù)n為[2^(h+1)] -1。因?yàn)樵摌?shù)總共有h層,每一層結(jié)點(diǎn)都是滿(mǎn)的。
(2)滿(mǎn)二叉樹(shù)的葉子結(jié)點(diǎn)個(gè)數(shù)是2^h。
3. 二叉樹(shù)的結(jié)構(gòu)
表示一個(gè)結(jié)點(diǎn)的方法之一是定義兩個(gè)指針,一個(gè)指向左孩子結(jié)點(diǎn),另一個(gè)指向右孩子結(jié)點(diǎn),中間為數(shù)據(jù)字段(如圖3-6所示)。
代碼實(shí)現(xiàn):
public class BinaryTreeNode { private int data; private BinaryTreeNode left; private BinaryTreeNode right; public int getData(){ return data; } public void setData(int data) { this.data = data; } public BinaryTreeNode getLeft() { return left; } public void setLeft(BinaryTreeNode left) { this.left = left; } public BinaryTreeNode getRight() { return right; } public void setRight(BinaryTreeNode right) { this.right = right; }}
4. 二叉樹(shù)的遍歷
訪(fǎng)問(wèn)樹(shù)中所有結(jié)點(diǎn)的過(guò)程叫做遍歷,遍歷的目標(biāo)是按照某種特定的順序訪(fǎng)問(wèn)樹(shù)的所有結(jié)點(diǎn)。
(1)遍歷的分類(lèi)
● 前序遍歷(DLR):訪(fǎng)問(wèn)當(dāng)前結(jié)點(diǎn),遍歷左子樹(shù),再遍歷右子樹(shù)。
● 中序遍歷(LDR):先遍歷左子樹(shù),訪(fǎng)問(wèn)當(dāng)前結(jié)點(diǎn),再遍歷右子樹(shù)。
● 后序遍歷(LRD):先遍歷左子樹(shù),再遍歷右子樹(shù),訪(fǎng)問(wèn)當(dāng)前結(jié)點(diǎn)。
● 層次遍歷。
以下圖所示的樹(shù)為例。
①前序遍歷
● 基于前序遍歷,圖3-7所示樹(shù)的前序遍歷結(jié)果如下:
前序遍歷結(jié)果: 1 2 4 5 3 6 7 Process finished with exit code 0
● 遞歸前序遍歷,代碼實(shí)現(xiàn)如下:
public void PreOrder(BinaryTreeNode root){ if(root!=null){ System.out.print(root.getData()); PreOrder(root.getLeft()); PreOrder(root.getRight()); } }
● 非遞歸前序遍歷,需要采用一個(gè)棧來(lái)記錄當(dāng)前結(jié)點(diǎn),以便在完成左子樹(shù)遍歷后能返回到右子樹(shù)進(jìn)行遍歷。首先處理當(dāng)前結(jié)點(diǎn),在遍歷左子樹(shù)之前,把當(dāng)前結(jié)點(diǎn)保留到棧中,當(dāng)遍歷完左子樹(shù)之后,該元素出棧,然后找到其右子樹(shù)進(jìn)行遍歷,直至???。代碼實(shí)現(xiàn)如下:
public void PreOrderNonRecursive(BinaryTreeNode root){ if(root==null){ return; } Stack s=new Stack(); while (true){ while (root!=null){ System.out.print(root.getData()); s.push(root); root=root.getLeft(); } if(s.isEmpty()){ break; } root=(BinaryTreeNode) s.pop(); root=root.getRight(); } }
②中序遍歷
● 基于中序遍歷,圖3-7所示樹(shù)的中序遍歷結(jié)果如下:
中序遍歷結(jié)果: 4 2 5 1 6 3 7 Process finished with exit code 0
● 遞歸中序遍歷,代碼實(shí)現(xiàn)如下:
public void InOrder(BinaryTreeNode root){ if(root!=null){ InOrder(root.getLeft()); System.out.print(root.getData()); InOrder(root.getRight()); } }
● 非遞歸中序遍歷,與前序遍歷的區(qū)別是,首先要移動(dòng)到結(jié)點(diǎn)的左子樹(shù),完成左子樹(shù)的遍歷后,再將當(dāng)前結(jié)點(diǎn)出棧進(jìn)行處理。
public void InOrderNonRecursive(BinaryTreeNode root){ if(root==null){ return; } Stack s=new Stack(); while (true){ while (root!=null){ s.push(root); root=root.getLeft(); } if(s.isEmpty()){ break; } root=(BinaryTreeNode)s.pop(); System.out.print(root.getData()+"\n"); root=root.getRight(); } }
③后序遍歷
● 基于后序遍歷,圖3-7所示樹(shù)的后序遍歷結(jié)果如下:
后序遍歷結(jié)果: 4 5 2 6 7 3 1 Process finished with exit code 0
● 遞歸后序遍歷,代碼實(shí)現(xiàn)如下:
public void PostOrder(BinaryTreeNode root){ if(root!=null){ PostOrder(root.getLeft()); PostOrder(root.getRight()); System.out.print(root.getData()); } }
● 非遞歸后序遍歷,在前序和中序遍歷中,當(dāng)元素出棧后就不需要再訪(fǎng)問(wèn)這個(gè)結(jié)點(diǎn)了。但是后序遍歷中,每個(gè)結(jié)點(diǎn)需要訪(fǎng)問(wèn)兩次。這意味著,在遍歷完左子樹(shù)后,需要訪(fǎng)問(wèn)當(dāng)前結(jié)點(diǎn),之后遍歷完右子樹(shù)時(shí),還需要訪(fǎng)問(wèn)當(dāng)前結(jié)點(diǎn)。但只有在第二次訪(fǎng)問(wèn)時(shí)才處理該結(jié)點(diǎn)。
● 解決辦法是,當(dāng)從棧中出棧一個(gè)元素時(shí),檢查這個(gè)元素與棧頂元素的右子結(jié)點(diǎn)是否相同。如果相同,則說(shuō)明已經(jīng)完成了左右子樹(shù)的遍歷。此時(shí)只要再將棧頂元素出棧并輸出該結(jié)點(diǎn)元素。
public void PostOrderNonRecursive(BinaryTreeNode root){ Stack stack=new Stack(); while (true){ if(root!=null){ //尋找最左葉子結(jié)點(diǎn) stack.push(root); root=root.getLeft(); }else { if(stack.isEmpty()){ return; }else { //判斷當(dāng)前結(jié)點(diǎn)是否有右子節(jié)點(diǎn) if(stack.top().getRight==null){ root=stack.pop(); System.out.print(root.getData()+"\n"); //判斷該結(jié)點(diǎn)是否為棧頂右子節(jié)點(diǎn) while(root==stack.top().getRight()){ System.out.print(stack.top().getData()+"\n"); root=stack.pop(); if(stack.isEmpty()){ return; } } } } if(!stack.isEmpty()){ //遍歷結(jié)點(diǎn)右子樹(shù) root=stack.top().getRight(); }else { root=null; } } } }
④層次遍歷
● 基于層次遍歷,圖3-7所示樹(shù)的層次遍歷結(jié)果如下:
層次遍歷結(jié)果: 1 2 3 4 5 6 7 Process finished with exit code 0
層次遍歷,代碼實(shí)現(xiàn)如下:
public void LevelOrder(BinaryTreeNode root){ BinaryTreeNode temp; LLBinaryTreeQueue queue=LLBinaryTreeQueue.creteQueue(); if(root==null){ return; } queue.enQueue(root); while (!queue.isEmpty()){ temp=queue.deQueue(); //處理當(dāng)前結(jié)點(diǎn) System.out.print(temp.getData()+"\n"); if(temp.getLeft()!=null){ queue.enQueue(temp.getLeft()); } if(temp.getRight()!=null){ queue.enQueue(temp.getRight()); } } }
C語(yǔ)言網(wǎng)提供由在職研發(fā)工程師或ACM藍(lán)橋杯競(jìng)賽優(yōu)秀選手錄制的視頻教程,并配有習(xí)題和答疑,點(diǎn)擊了解:
一點(diǎn)編程也不會(huì)寫(xiě)的:零基礎(chǔ)C語(yǔ)言學(xué)練課程
解決困擾你多年的C語(yǔ)言疑難雜癥特性的C語(yǔ)言進(jìn)階課程
從零到寫(xiě)出一個(gè)爬蟲(chóng)的Python編程課程
只會(huì)語(yǔ)法寫(xiě)不出代碼?手把手帶你寫(xiě)100個(gè)編程真題的編程百練課程
信息學(xué)奧賽或C++選手的 必學(xué)C++課程
藍(lán)橋杯ACM、信息學(xué)奧賽的必學(xué)課程:算法競(jìng)賽課入門(mén)課程
手把手講解近五年真題的藍(lán)橋杯輔導(dǎo)課程