2016考研計算機：數據結構核心考點之二叉樹_跨考網

　　計算機一直是現在的熱門專業(yè)，每年都有很多從事這方便工作的人，也有很多考研的人?？佳杏嬎銠C的專業(yè)課是全國統考科目，包括四個科目，知識點還是很多的，下面一起來看一下考研計算機數據結構核心考點之二叉樹。

　　?二叉樹的遍歷

　　遍歷的過程就是把非線性結構的二叉樹中的結點排成一個線性序列的過程。

　　二叉樹遍歷方法可分為兩大類，一類是“寬度優(yōu)先”法，即從根結點開始，由上到下，從左往右一層一層的遍歷;另一類是“深度優(yōu)先法”，即一棵子樹一棵子樹的遍歷。

　　從二叉樹結構的整體看，二叉樹可以分為根結點，左子樹和右子樹三部分，只要遍歷了這三部分，就算遍歷了二叉樹。設D表示根結點，L表示左子樹，R表示右子樹，則DLR的組合共有6種，即DLR，DRL，LDR，LRD，RDL，RLD。若限定先左后右，則只有DLR，LDR，LRD三種，分別稱為先(前)序法(先根次序法)，中序法(中根次序法，對稱法)，后序法(后根次序法)。三種遍歷的遞歸算法如下：

　　1.先序法(DLR)

　　若二叉樹為空，則空操作，否則：訪問根結點，先序遍歷左子樹，先序遍歷右子樹。

　　2.中序法(LDR)

　　若二叉樹為空，則空操作，否則：中序遍歷左子樹，訪問根結點，中序遍歷右子樹.

　　3.后序法(LRD)

　　若二叉樹為空，則空操作，否則：后序遍歷左子樹，后序遍歷右子樹，訪問根結點。

　　?完全二叉樹中有關結點個數計算

　　完全二叉樹的定義：深度為k，有n個結點的二叉樹當且僅當其每一個結點都與深度為k的滿二叉樹中編號從1至n的結點一一對應時，稱為完全二叉樹。

　　完全二叉樹的葉子數為(n + 1) / 2取下整。

　　?森林與二叉樹之間的轉換以及轉換過程中結點之間的關系

　　將一棵樹轉換為二叉樹的方法是：

　　1.樹中所有相鄰兄弟之間加一條連線。

　　2.對樹中的每個結點，只保留其與第一個孩子結點之間的連線，刪去其與其它孩子結點之間的連線。

　　3.以樹的根結點為軸心，將整棵樹順時針旋轉一定的角度，使之結構層次分明。

　　森林轉換為二叉樹的方法如下：

　　1.將森林中的每棵樹轉換成相應的二叉樹。

　　2.第一棵二叉樹不動，從第二棵二叉樹開始，依次把后一棵二叉樹的根結點作為前一棵二叉樹根結點的右孩子，當所有二叉樹連在一起后，所得到的二叉樹就是由森林轉換得到的二叉樹。

　　樹和森林都可以轉換為二叉樹，二者的不同是:樹轉換成的二叉樹,其根結點必然無右孩子，而森林轉換后的二叉樹，其根結點有右孩子。將一棵二叉樹還原為樹或森林，具體方法如下：

　　1.若某結點是其雙親的左孩子，則把該結點的右孩子、右孩子的右孩子、……都與該結點 的雙親結點用線連起來。

　　2.刪掉原二叉樹中所有雙親結點與右孩子結點的連線。

　　3.整理由1、2兩步所得到的樹或森林，使之結構層次分明。

　　計算機是一門很博大精深的科目，包含的內容千變萬化，能學的東西也數不勝數。二叉樹是重要的考點，考生應該牢牢掌握。