數(shù)據(jù)結(jié)構(gòu)課件：二叉樹的存儲(chǔ)與基本操作

二叉樹的

存儲(chǔ)與基本操作

本講要點(diǎn)二叉樹的存儲(chǔ)

二叉樹的基本操作問題如何表示（抽象）邏輯結(jié)構(gòu)如何存儲(chǔ)？物理結(jié)構(gòu)如何操作？操作算法1.二叉樹的存儲(chǔ)二叉樹的順序存儲(chǔ)結(jié)構(gòu)用一維數(shù)組存儲(chǔ)二叉樹中的結(jié)點(diǎn)，并且結(jié)點(diǎn)的存儲(chǔ)位置（下標(biāo)）應(yīng)能體現(xiàn)結(jié)點(diǎn)之間的邏輯關(guān)系——父子關(guān)系。如何利用數(shù)組下標(biāo)來反映結(jié)點(diǎn)之間的邏輯關(guān)系?二叉樹的性質(zhì)5為二叉樹的順序存儲(chǔ)指明了存儲(chǔ)規(guī)則：依照完全二叉樹的結(jié)點(diǎn)編號(hào)次序，依次存放各個(gè)結(jié)點(diǎn)。完全二叉樹和滿二叉樹中結(jié)點(diǎn)的序號(hào)可以唯一地反映出結(jié)點(diǎn)之間的邏輯關(guān)系。注意：C/C++中數(shù)組的起始地址為0，編號(hào)為i的結(jié)點(diǎn)存儲(chǔ)在下標(biāo)為i的單元內(nèi)。1.二叉樹的存儲(chǔ)二叉樹的順序存儲(chǔ)結(jié)構(gòu)對(duì)于一般二叉樹而言，如何利用完全二叉樹的編碼規(guī)則來存儲(chǔ)數(shù)據(jù)呢？ABCDEGFABC∧DE∧∧∧F∧∧G數(shù)組下標(biāo)12345678910111213以編號(hào)為下標(biāo)ABCDEGF123561013按照完全二叉樹編號(hào)1.二叉樹的存儲(chǔ)二叉樹的順序存儲(chǔ)結(jié)構(gòu)優(yōu)點(diǎn)？對(duì)于滿二叉樹、完全二叉樹來說，順序存儲(chǔ)結(jié)構(gòu)的存儲(chǔ)效率極高。所有的空間僅僅用來存儲(chǔ)數(shù)據(jù)元素的值，結(jié)點(diǎn)之間關(guān)系的存儲(chǔ)未占用任何空間?？梢灾苯哟嫒《鏄渲械娜我饨Y(jié)點(diǎn)的數(shù)據(jù)信息，且雙親與孩子關(guān)系計(jì)算也非常簡單。由于每個(gè)數(shù)據(jù)元素的存儲(chǔ)位置暗藏彼此之間的關(guān)系，可以根據(jù)結(jié)點(diǎn)的編號(hào)，直接計(jì)算出它的父結(jié)點(diǎn)、左/右孩子結(jié)點(diǎn)的位置。1.二叉樹的存儲(chǔ)二叉樹的順序存儲(chǔ)結(jié)構(gòu)缺點(diǎn)？一棵斜樹的順序存儲(chǔ)會(huì)怎樣呢？高度為k的右斜樹，k個(gè)結(jié)點(diǎn)需分配2k－1個(gè)存儲(chǔ)單元。一棵二叉樹改造后成完全二叉樹形態(tài)，需增加很多空結(jié)點(diǎn)，造成存儲(chǔ)空間的浪費(fèi)。二叉樹的順序存儲(chǔ)結(jié)構(gòu)一般僅存儲(chǔ)完全二叉樹ABC137D151.二叉樹的存儲(chǔ)二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)基本思想：令二叉樹的每個(gè)結(jié)點(diǎn)對(duì)應(yīng)一個(gè)鏈表結(jié)點(diǎn)，鏈表結(jié)點(diǎn)除了存放與二叉樹結(jié)點(diǎn)有關(guān)的數(shù)據(jù)信息外，還要設(shè)置指示左右孩子的指針。1.二叉樹的存儲(chǔ)二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)結(jié)點(diǎn)結(jié)構(gòu)：

lchild

data

rchild其中，data：數(shù)據(jù)域，存放該結(jié)點(diǎn)的數(shù)據(jù)信息；lchild：左指針域，存放指向左孩子的指針；rchild：右指針域，存放指向右孩子的指針。1.二叉樹的存儲(chǔ)二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)具有n個(gè)結(jié)點(diǎn)的二叉鏈表中，有多少個(gè)空指針？2.二叉樹的基本操作二叉樹的遍歷二叉樹的建立二叉樹的銷毀2.二叉樹的基本操作（1）二叉樹的遍歷從根結(jié)點(diǎn)出發(fā)，按照某種次序訪問二叉樹中的所有結(jié)點(diǎn)，使得每個(gè)結(jié)點(diǎn)被訪問一次且僅被訪問一次。如果限定先左后右，則遍歷方式有三種：先序：DLR中序：LDR后序：LRD層序遍歷：按二叉樹的層序編號(hào)的次序訪問各結(jié)點(diǎn)。考慮二叉樹的組成：根結(jié)點(diǎn)D左子樹L右子樹R二叉樹什么次序？二叉樹遍歷操作的結(jié)果非線性結(jié)構(gòu)線性化2.二叉樹的基本操作（1）二叉樹的遍歷從根結(jié)點(diǎn)出發(fā)，按照某種次序訪問二叉樹中的所有結(jié)點(diǎn)，使得每個(gè)結(jié)點(diǎn)被訪問一次且僅被訪問一次。抽象操作，可以是對(duì)結(jié)點(diǎn)進(jìn)行的各種處理，這里簡化為輸出結(jié)點(diǎn)的數(shù)據(jù)。訪問是什么意思？2.二叉樹的基本操作（1）二叉樹的遍歷先序遍歷①若二叉樹為空，則空操作返回。（否則）②訪問根結(jié)點(diǎn)。③先序遍歷根結(jié)點(diǎn)的左子樹。④先序遍歷根結(jié)點(diǎn)的右子樹。先序遍歷序列：ABDGCEFABCDEFG2.二叉樹的基本操作（1）二叉樹的遍歷中序遍歷①若二叉樹為空，則空操作返回。（否則）②中序遍歷根結(jié)點(diǎn)的左子樹。③訪問根結(jié)點(diǎn)。④中序遍歷根結(jié)點(diǎn)的右子樹。ABCDEFG中序遍歷序列：DGBAECF2.二叉樹的基本操作（1）二叉樹的遍歷后序遍歷①若二叉樹為空，則空操作返回。（否則）②后序遍歷根結(jié)點(diǎn)的左子樹。③后序遍歷根結(jié)點(diǎn)的右子樹。④訪問根結(jié)點(diǎn)。ABCDEFG后序遍歷序列：GDBEFCA練一練--/+*abcdef二叉樹遍歷操作練習(xí)先序遍歷結(jié)果：中序遍歷結(jié)果：后序遍歷結(jié)果：-+a*b-cd/efa+b*c-d-e/fabcd-*+ef/-2.二叉樹的基本操作（1）二叉樹的遍歷層次遍歷從二叉樹的第一層（即根結(jié)點(diǎn)）開始，從上至下逐層遍歷，在同一層中，則按從左到右的順序?qū)Y(jié)點(diǎn)逐個(gè)訪問。ABCDEFG層次遍歷序列：ABCDEFG2.二叉樹的基本操作（2）二叉樹的建立能不能根據(jù)輸入的線性序列唯一確定一棵二叉樹？例如，輸入先序序列abc解決？在輸出遍歷序列時(shí)，忽略了空結(jié)點(diǎn)，從而導(dǎo)致無法確定在遍歷序列中的后繼結(jié)點(diǎn)是左孩子還是右孩子。如果將“若二叉樹為空，則遍歷結(jié)束”改為“若二叉樹為空，則輸出字符#”2.二叉樹的基本操作（2）二叉樹的建立擴(kuò)展二叉樹的先序遍歷序列：AB#D##C##DBAC#DBAC####2.二叉樹的基本操作（2）二叉樹的建立先序遍歷①若二叉樹為空，則空操作返回；（否則）②訪問根結(jié)點(diǎn)；③先序遍歷根結(jié)點(diǎn)的左子樹；④先序遍歷根結(jié)點(diǎn)的右子樹。先序創(chuàng)建①若輸入為#(空)，則root=NULL（否則）②創(chuàng)建根結(jié)點(diǎn)；③先序創(chuàng)建根結(jié)點(diǎn)的左子樹；④先序創(chuàng)建根結(jié)點(diǎn)的右子樹。由帶空指針標(biāo)記的先序序列構(gòu)造二叉樹的算法

DBAC#DBAC####2.二叉樹的基本操作（3）二叉樹的銷毀什么是二叉樹的銷毀？為什么要專門進(jìn)行銷毀？二叉樹的銷毀即釋放二叉鏈表中的所有結(jié)點(diǎn)。二叉鏈表對(duì)象的建立是一個(gè)動(dòng)態(tài)申請(qǐng)空間的過程，因此，當(dāng)程序結(jié)束時(shí)需要釋放二叉鏈表中的所有結(jié)點(diǎn)。每個(gè)結(jié)點(diǎn)必須被釋放，且只能被釋