2016考研計(jì)算機(jī)：數(shù)據(jù)結(jié)構(gòu)核心考點(diǎn)之二叉樹_跨考網(wǎng)

　　計(jì)算機(jī)一直是現(xiàn)在的熱門專業(yè)，每年都有很多從事這方便工作的人，也有很多考研的人?？佳杏?jì)算機(jī)的專業(yè)課是全國(guó)統(tǒng)考科目，包括四個(gè)科目，知識(shí)點(diǎn)還是很多的，下面一起來看一下考研計(jì)算機(jī)數(shù)據(jù)結(jié)構(gòu)核心考點(diǎn)之二叉樹。

　　?二叉樹的遍歷

　　遍歷的過程就是把非線性結(jié)構(gòu)的二叉樹中的結(jié)點(diǎn)排成一個(gè)線性序列的過程。

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

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

　　1.先序法(DLR)

　　若二叉樹為空，則空操作，否則：訪問根結(jié)點(diǎn)，先序遍歷左子樹，先序遍歷右子樹。

　　2.中序法(LDR)

　　若二叉樹為空，則空操作，否則：中序遍歷左子樹，訪問根結(jié)點(diǎn)，中序遍歷右子樹.

　　3.后序法(LRD)

　　若二叉樹為空，則空操作，否則：后序遍歷左子樹，后序遍歷右子樹，訪問根結(jié)點(diǎn)。

　　?完全二叉樹中有關(guān)結(jié)點(diǎn)個(gè)數(shù)計(jì)算

　　完全二叉樹的定義：深度為k，有n個(gè)結(jié)點(diǎn)的二叉樹當(dāng)且僅當(dāng)其每一個(gè)結(jié)點(diǎn)都與深度為k的滿二叉樹中編號(hào)從1至n的結(jié)點(diǎn)一一對(duì)應(yīng)時(shí)，稱為完全二叉樹。

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

　　?森林與二叉樹之間的轉(zhuǎn)換以及轉(zhuǎn)換過程中結(jié)點(diǎn)之間的關(guān)系

　　將一棵樹轉(zhuǎn)換為二叉樹的方法是：

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

　　2.對(duì)樹中的每個(gè)結(jié)點(diǎn)，只保留其與第一個(gè)孩子結(jié)點(diǎn)之間的連線，刪去其與其它孩子結(jié)點(diǎn)之間的連線。

　　3.以樹的根結(jié)點(diǎn)為軸心，將整棵樹順時(shí)針旋轉(zhuǎn)一定的角度，使之結(jié)構(gòu)層次分明。

　　森林轉(zhuǎn)換為二叉樹的方法如下：

　　1.將森林中的每棵樹轉(zhuǎn)換成相應(yīng)的二叉樹。

　　2.第一棵二叉樹不動(dòng)，從第二棵二叉樹開始，依次把后一棵二叉樹的根結(jié)點(diǎn)作為前一棵二叉樹根結(jié)點(diǎn)的右孩子，當(dāng)所有二叉樹連在一起后，所得到的二叉樹就是由森林轉(zhuǎn)換得到的二叉樹。

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

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

　　2.刪掉原二叉樹中所有雙親結(jié)點(diǎn)與右孩子結(jié)點(diǎn)的連線。

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

　　計(jì)算機(jī)是一門很博大精深的科目，包含的內(nèi)容千變?nèi)f化，能學(xué)的東西也數(shù)不勝數(shù)。二叉樹是重要的考點(diǎn)，考生應(yīng)該牢牢掌握。