常用的數(shù)據(jù)結(jié)構(gòu)和算法(6)

1、專業(yè)教程理論講解部分ver3.1第025課 算法及數(shù)據(jù)結(jié)構(gòu)概述： 二叉樹的相關(guān)概念 二叉樹的實(shí)現(xiàn) 重點(diǎn)： 難點(diǎn)： 二叉樹的實(shí)現(xiàn) 二叉樹的實(shí)現(xiàn)6 二叉樹第025課 算法及數(shù)據(jù)結(jié)構(gòu)二叉樹綜合了有序數(shù)組與鏈表得優(yōu)點(diǎn).有序數(shù)組具有較快得查找速度,鏈表具有非常好得插入刪除效率.樹結(jié)合了兩者得有點(diǎn),使得它具有很高得插入 刪除及查找得效率.它得實(shí)現(xiàn)與其結(jié)構(gòu)密切相關(guān),下面我們來看看它的結(jié)構(gòu).第025課 算法及數(shù)據(jù)結(jié)構(gòu)12345678這是一棵很簡單的樹.樹主要是由結(jié)點(diǎn)及結(jié)點(diǎn)之間得關(guān)系組成的下面給出一些相關(guān)得概念6 二叉樹第025課 算法及數(shù)據(jù)結(jié)構(gòu)二叉樹或者是一棵 空樹空樹 ，或者是一棵由一個(gè) 根結(jié)根結(jié) 點(diǎn)和兩棵

2、互不相交的分別稱根的 左子樹左子樹 和 右子樹右子樹 所組成的 非空樹非空樹 ，左子樹和右子樹又同樣都是一棵二叉樹. 右圖為一棵二叉樹6.1 樹的相關(guān)概念二叉樹二叉樹:1234566 二叉樹第025課 算法及數(shù)據(jù)結(jié)構(gòu)路徑:順著連接節(jié)點(diǎn)的邊從一個(gè)節(jié)點(diǎn)走到另一個(gè)節(jié)點(diǎn)，所經(jīng)過的節(jié)點(diǎn)的順序排列就稱為“路徑”。123456其中橙色得線就代表一條路徑6.1 樹的相關(guān)概念6 二叉樹第025課 算法及數(shù)據(jù)結(jié)構(gòu)根:樹得頂端稱為根.每棵樹只有一個(gè)根.123456右圖中 1 為根父結(jié)點(diǎn)與子結(jié)點(diǎn):除根結(jié)點(diǎn)外,其余結(jié)點(diǎn)都有另外一個(gè)結(jié)點(diǎn)指向它.那么指向其它結(jié)點(diǎn)的結(jié)點(diǎn)稱為父結(jié)點(diǎn).被指向的結(jié)點(diǎn)稱為子結(jié)點(diǎn).右圖中3為6的父結(jié)點(diǎn)

3、,6為3的子結(jié)點(diǎn)6.1 樹的相關(guān)概念6 二叉樹第025課 算法及數(shù)據(jù)結(jié)構(gòu)123456葉結(jié)點(diǎn): 沒有子結(jié)點(diǎn)的結(jié)點(diǎn)稱為葉結(jié)點(diǎn).圖中4,5,6均為葉結(jié)點(diǎn).子樹: 每一個(gè)結(jié)點(diǎn)都可以看作是其子孫結(jié)點(diǎn)的根.這樣將其與其子孫結(jié)點(diǎn)的集合稱為子樹圖中2,4,5可以看作是一棵子樹.6.1 樹的相關(guān)概念6 二叉樹第025課 算法及數(shù)據(jù)結(jié)構(gòu)123456遍歷:根據(jù)某種規(guī)則,對(duì)樹中所有的結(jié)點(diǎn)全部訪問一次稱作一次遍歷.例如:1,2,3,4,5,6 就是一次遍歷.它是按照由高到低的順序遍歷的.或者稱為廣度優(yōu)先遍歷.層:樹中從根開始計(jì)算的 “輩分”.0126.1 樹的相關(guān)概念6 二叉樹第025課 算法及數(shù)據(jù)結(jié)構(gòu)6.2 二叉樹的

4、建立實(shí)現(xiàn)二叉樹首先就要實(shí)現(xiàn)它的結(jié)點(diǎn).它的每一個(gè)結(jié)點(diǎn)除了要保存相應(yīng)的數(shù)據(jù)之外,還要保存其子結(jié)點(diǎn)的引用.其數(shù)據(jù)需要兩個(gè)域,一個(gè)保存鍵值,另一個(gè)保存該鍵值所對(duì)應(yīng)的數(shù)據(jù).private class nodeint key;int value;node left;node right;6 二叉樹第025課 算法及數(shù)據(jù)結(jié)構(gòu)當(dāng)我們擁有了結(jié)點(diǎn)以后,就可以著手創(chuàng)建我們的樹了.一顆數(shù)最特殊的結(jié)點(diǎn)就是它的根結(jié)點(diǎn),當(dāng)擁有了根結(jié)點(diǎn)就意味著你擁有了整棵樹.所以我們要用一個(gè)變量來保存這個(gè)非常重要的根.private node root;6.2 二叉樹的建立6 二叉樹第025課 算法及數(shù)據(jù)結(jié)構(gòu)二叉樹的初始化非常的簡單.只需要

5、有個(gè)根就可以了,而且樹是空的.所以甚至連根的初始化都可以省略.public mytree() super();root = null;這里唯一的一句root = null;都可以省略.因?yàn)閷?duì)象在初始化時(shí),其成員變量自動(dòng)是空.為了清晰,還是把它加上.6.2 二叉樹的建立6 二叉樹第025課 算法及數(shù)據(jù)結(jié)構(gòu)6.3 二叉樹的插入 二叉樹的插入是保證起有序性的重要環(huán)節(jié).如果隨意的插入則無法保證其有序性.二叉樹的順序一棵有序的二叉樹叫搜索二叉樹.其定義是根要大于左子樹所有結(jié)點(diǎn),小于右子樹所有結(jié)點(diǎn).其子樹仍然遵循這個(gè)規(guī)律.我們要建立的便是一棵這樣的搜索二叉樹.6 二叉樹第025課 算法及數(shù)據(jù)結(jié)構(gòu)10213

6、1516如圖,該樹便是一棵搜索二叉樹.下面我們要討論如何將7插入該樹.首先我們要訪問根結(jié)點(diǎn),判斷這個(gè)7應(yīng)該放在其左子樹還是右子樹.710 ,所以 7 應(yīng)該放在左子樹中.6.3 二叉樹的插入6 二叉樹第025課 算法及數(shù)據(jù)結(jié)構(gòu)102131516然后,對(duì)根的左子樹進(jìn)行檢查.判斷該子樹是否為空,若空則將7加入.非空則繼續(xù)判斷在該子樹中的位置.根的左子樹非空且值為2,后判斷27,則7應(yīng)該在該子樹的右子樹中.6.3 二叉樹的插入6 二叉樹第025課 算法及數(shù)據(jù)結(jié)構(gòu)102131516以次繼續(xù),直到判斷到5后,7應(yīng)該在5的右子樹中,且5的右子樹為空.于是將7加入5的右子樹中76.3 二叉樹的插入6 二叉樹第025課 算法及數(shù)據(jù)結(jié)構(gòu)private void insertnode(node subtreeroot,node newnode) node current = subtreeroot; while(true) if(newnode.key右子樹根 b)左子樹右子樹根 c)左子樹根右子樹 d)左子樹右子樹3、在樹的插入中,我們使用的是非遞歸方法.考慮如何使用非遞歸方法實(shí)現(xiàn)小測驗(yàn)（單選題）：第025課 算法及數(shù)據(jù)結(jié)構(gòu)1、樹集成了哪兩種結(jié)構(gòu)的優(yōu)點(diǎn)(bd) a) 隊(duì)列 b)有序數(shù)組 c)棧 d)鏈表2、搜索樹的規(guī)則是(c) a)左子樹右子樹根 b)左子樹右子樹根 c)左子樹根右子樹 d)左