二叉樹的遍歷講稿

單位：大連海洋大學(xué)應(yīng)用技術(shù)學(xué)院主講教師：文繼權(quán)本節(jié)主要內(nèi)容二、二叉樹遍歷定義與算法描述

一、問(wèn)題的提出

三、應(yīng)用實(shí)例四、小結(jié)

一.問(wèn)題的提出問(wèn)題：如何找到小明的“外祖母”這個(gè)節(jié)點(diǎn)，并打印節(jié)點(diǎn)信息。小明家三代家族譜系二叉樹一、問(wèn)題的提出線性結(jié)構(gòu)：非線性結(jié)構(gòu)：線性結(jié)構(gòu)與非線性結(jié)構(gòu)的對(duì)比二、遍歷定義與算法描述定義：二叉樹的遍歷，即按某條搜索路徑巡訪樹中每個(gè)結(jié)點(diǎn)，使得每個(gè)結(jié)點(diǎn)均被

訪問(wèn)一次，而且僅被訪問(wèn)一次。這里的“訪問(wèn)”含義十分廣泛，包括按問(wèn)題需求對(duì)節(jié)點(diǎn)所進(jìn)行的任意存取操作或其他加工任務(wù)。遍歷是二叉樹一切運(yùn)算或操作的基礎(chǔ)和核心。二叉樹的遍歷定義二、遍歷定義與算法描述二叉樹的遍歷算法描述二叉樹：二叉樹是n個(gè)數(shù)據(jù)元素的有限集，它或?yàn)榭占╪=0），或者含有唯一稱為根的元素，且其余元素分成兩個(gè)互補(bǔ)相交的子集，每個(gè)子集自身是一顆二叉樹，分別稱為根的左子樹和右子樹。根左子樹右子樹左子樹二、遍歷定義與算法描述二叉樹的遍歷算法描述根左子樹右子樹左子樹D:訪問(wèn)根節(jié)點(diǎn)L:遍歷左子樹R:遍歷右子樹注：限定先左后右的進(jìn)行遍歷DLRLDRLRD二、遍歷定義與算法描述二叉樹的遍歷算法描述先（根）序遍歷-DLR中（根）序遍歷-LDR后（根）序遍歷-LRD若二叉樹為空，則空操作；否則(1)訪問(wèn)根結(jié)點(diǎn)；(2)先序遍歷左子樹；(3)先序遍歷右子樹。若二叉樹為空，則空操作；否則

(1)中序遍歷左子樹；

(2)訪問(wèn)根結(jié)點(diǎn)；

(3)中序遍歷右子樹。若二叉樹為空，則空操作；否則(1)后序遍歷左子樹；(2)后序遍歷右子樹；(3)訪問(wèn)根結(jié)點(diǎn)。二、遍歷定義與算法描述ABCEDGF二叉樹的遍歷算法演示實(shí)例應(yīng)用三種算法分別對(duì)該二叉樹進(jìn)行遍歷二、遍歷定義與算法描述先（根）序遍歷-DLR：ABCEDGFD

L

RAD

LRBCD

LRD

LR>>D前序遍歷序列：ＡＢＤＥＣＦＧD

LR>>ＥD

LR>>ＦD

LR>>Ｇ二、遍歷定義與算法描述中（根）序遍歷-LD

R：BL

DRL

DRA>>DCL

DRL

DR>>ＥL

DR>>ＦL

DR>>Ｇ中序遍歷序列：ＤＢＥＡＦＣＧABCEDGFL

D

R二、遍歷定義與算法描述后（根）序遍歷-LRD

：LRDLRDDLRDBLRD>ＥLRD>>ＦLRD>>ＧＣA后序遍歷序列：ＤＥＢＦＧＣＡABCEDGF

LRD>>>三、應(yīng)用實(shí)例已知：

一棵二叉樹的先（根）序遍歷序列為：ABCDEFG中（根）序遍歷序列為：CBEDAFG試構(gòu)建該二叉樹。三、應(yīng)用實(shí)例

先（根）序遍歷序列為：A

BCDEFG

中（根）序遍歷序列為：CBEDAFGACＢＥＤＦＧ先序：ＢCＤＥ先序：ＦＧDCGEBFＥＤ中序：CＢＥＤ中序：ＦＧ三、應(yīng)用實(shí)例

先（根）序遍歷序列為：A

BCDEFG

中（根）序遍歷序列為：CBEDAFGADCGEBF三、應(yīng)用實(shí)例已知：

一棵二叉樹的后（根）序遍歷序列為：C

E

D

BG

FA中（根）序遍歷序列為：CBEDAFG試構(gòu)建該二叉樹。思考