《數(shù)據(jù)結構》 (java版) 課件 6樹、二叉樹的性質(zhì)和遍歷

樹和二叉樹樹的概念和常用術語遞歸、二叉樹及其特性完全二叉樹及其特性二叉樹的存儲二叉樹的基本操作：遍歷遍歷的執(zhí)行過程二叉樹的其它操作樹(Tree)離散數(shù)學有多種等價的定義，其中之一：

n個結點n-1條邊的連通圖。數(shù)據(jù)結構的定義同上，但選定一個結點作為“根(root)”，因此又叫做有根樹。樹用于表示有層次的數(shù)據(jù)，層次由數(shù)據(jù)之間的父子關系(一父多子)描述ACGBDEFHJACGBDEFHJ0層1層2層樹是結點的有限集合，如果不為空集，其中，有一個特殊的結點叫做根，其他的結點劃分為m個不相交的子集T1、T2、Tm，每個子集是一棵樹，T1、T2、Tm叫做根的子樹樹中任何一個結點是整棵樹的某棵子樹的根結點樹-目錄基本術語DHIJM結點的度(degree):子樹的個數(shù)終端/葉子結點(terminalnode/leaf):度為零的結點分支結點(branchnode):度大于零的結點ABCDEFGHIJMKL路徑(path)：由從根到該結點所經(jīng)邊和結點構成：A-C-G路徑長度(pathlength)：邊的條數(shù)雙親結點孩子結點兄弟結點堂兄弟祖先結點子孫結點基本術語結點的層次(level):根結點0層、其孩子結點1層...(根到結點路徑的長度)樹的深度(depth):最大層次+1，或最長路徑長度+1基本術語ABCDEFGHIJMKL0123有序樹(orderedtree)：子樹之間存在次序關系無序???樹(orientedtree)：子樹之間不存在次序關系基本術語PABCPBAC≠PABCPBAC=ArootBEFKLCGDHIJMF基本術語森林：是m（m≥0）棵互不相交的樹的集合線性結構樹型結構根結點無前驅第一個數(shù)據(jù)元素無前驅最后一個數(shù)據(jù)元素無后繼葉子結點無后繼其它結點一個前驅、多個后繼其它數(shù)據(jù)元素一個前驅、一個后繼樹型結構和線性結構特點的對比一對一一對多遞歸定義：基礎：空樹是二叉樹歸納：二叉樹由根結點、左子樹、右子樹構成；并且左、右子樹也是二叉樹。二叉樹(binarytree)RRLRRR1）空樹2）

只含根結點4）左子樹為空RRL3）

右子樹為空RL5）左右子樹都不為空二叉樹從最基本的元素開始，重復使用簡單的規(guī)則，就能構造出復雜的東西。復雜的東西有簡單的構造原理。例如：算術表達式等遞歸(recursion)(a+b)/(c-d)+e+g*h/aaeab+cd-gh*//++ACGBDEFKLHJIMNOABCDEFGHKABCDEFGHK二叉樹形態(tài)各異，但是，結構一樣。二叉樹擴展的二叉樹(extendedbinarytree)ABECDABECD擴展的二叉樹用方框表示空樹，方框叫做外部結點性質(zhì)1：二叉樹的第i層上至多有2i個結點。(i≥0)二叉樹具有以下五條重要性質(zhì)：二叉樹的特性層號ACGBDEFKLHJIMNO0123i=0時，只有一個根結點，滿足2i=20=1；假設第i-1層上至多有2i-1個結點;二叉樹上每個結點至多有兩棵子樹，則第i層的結點數(shù)=2i-1×2=2i。二叉樹的特性用歸納法證明歸納基礎：歸納假設：歸納：性質(zhì)2：深度為k的二叉樹上至多含2k-1個結點（k≥0）二叉樹的特性證明：≤20+21+??????+2k-1=2k-1第0層:≤20第1層:≤21……第k-1層:≤2k-1深度為k，即有k-1層性質(zhì)3：任何一棵二叉樹，若它含有n0個葉子結點、n2個度為2的結點，則必存在關系式：n0=n2+1二叉樹的特性ACGBDEFHJI設二叉樹上邊數(shù)為b，由樹的性質(zhì)：b=n-1又因為度為1的點引出一條邊度為2的點引出2條邊，所以：b=n1+2n2所以：n=n1+2n2+1公式(2)證明：設二叉樹上結點總數(shù)n=n0+n1+n2公式(1)由式1和2得到：n0+n1+n2=n1+2n2+1整理后n0=n2+1給定n個(n≥0)結點，如何能得到深度最小的二叉樹？先把第0層填滿如果還有余下的結點，則把第1層填滿如果還有余下的結點，則把第2層填滿...，依次類推。填最后一層，按照從左往右的次序填，并且中間沒有空隙完全二叉樹(completebinarytree)ACGBDEFHJIACGBDEFHJI完全二叉樹非完全二叉樹擴展的完全二叉樹(completebinarytree)ACGBDEFHJIACGBDEFHI取整函數(shù)的定義?x?=mifm≤x<m+1Math.floor(x)?x?=mifm-1<x≤mMath.ceil(x)設x是任意的實數(shù)，m是一個整數(shù)：?2.1?=2?-2.1?=-3?2.1?=3?-2.1?=-20123-1-2-3取整函數(shù)的性質(zhì)?x?=?x?x是整數(shù)?x?=?x?+1x不是整數(shù)?-x?=-?x?x?x??x?x+1x-1n是整數(shù)：??+??=n??=??證明：假設完全二叉樹的深度為k。由定義：0-->k-2層構成的樹一定是滿二叉樹由性質(zhì)2：0-->k-2層結點數(shù)為：2k-1-1由性質(zhì)2，0至k-1層結點數(shù)最多為：2k-1完全二叉樹的特性性質(zhì)4：具有n個結點的完全二叉樹的深度為?log2(n+1)

?所以：2k-1-1<n≤2k-12k-1<n＋1≤2k

于是：k-1<log2(n+1)≤kk=?log2(n+1)

?所以：2k-1-1<n≤2k-12k-1≤n<2k

于是：k-1≤log2(n)<kk-1=?log2(n)?k=?log2(n)?+1按照從上往下，從左往右，從0開始連續(xù)對完全二叉樹的結點編號：0123456789完全二叉樹ACGBDEFHJI若i=0，則該結點是二叉樹的根，無雙親。否則，編號為??的結點為其雙親結點。性質(zhì)5：結點的編號之間具有關系：完全二叉樹的特性0123456789(2)若2i+1≥n，則編號為i的結點無左孩子,否則，編號為2i+1的結點為其左孩子結點。若2i+2≥n，則編號為i的結點無右孩子結點，否則，編號為2i+2的結點為其右孩子結點。完全二叉樹的特性01234567891.具有1025個結點的二叉樹的深度為____A.11B.10C.11至1025之間D.10至1024之間課堂練習2、有n個結點的滿二叉樹的葉子結點有多少？3、完全二叉樹的度為1的結點有多少？5、有n個結點的二叉樹最大深度是多少？最少深度是多少？4、一棵完全二叉樹上有1001個結點，其中葉子結點的個數(shù)是____A.250B.500C.254D.505E.以上答案都不對ACGBDEFHJI0123456789

0123456789ABCEFDGHIJ完全二叉樹的順序存儲二叉樹的鏈式存儲：二叉鏈AF∧∧E∧C∧D∧∧B∧rootABDCEF思考n個結點的鏈式表示中有多少個引用變量的值為null?由性質(zhì)3:n0=n2+1設總的結點數(shù)為n，n=n0+n1+n2=n0+n1+n0-12n0+n1=n+1

從上往下看(top-down):葉子結點(n0)有2個null，度為1的結點(n1)有1個null，度為2的結點(n2)有0個null，2n0+n1?AF∧∧E∧C∧D∧∧B∧root思考n個結點的二叉鏈中有多少個引用變量的值為null?從下往上看(bottom-up):每個結點有2個引用變量，n個結點共2n個引用變量結點的孩子占用1個引用變量，每個結點(除根結點)都是某個結點的孩子，共有n-1個孩子結點，占用了n-1個引用變量所以null的個數(shù)為2n-(n-1)=n+1AF∧∧E∧C∧D∧∧B∧root∧鏈式存儲：三叉鏈表二叉樹的多數(shù)應用一般從root入手，采用top-down處理方式；有些應用需要采用bottom-up處理方式，為了方便找到父結點，也可以采用三叉鏈表像平衡樹需要結合top-down和bottom-up2種方式，使用二叉鏈+棧AF∧∧E∧C∧D∧∧B∧root二叉樹的操作二叉樹是一種很重要的數(shù)據(jù)結構，但不如棧、隊列和線性表那樣基礎，有公認的基本操作(接口)。二叉樹作為數(shù)據(jù)的集合，其最基本的操作就是遍歷。即枚舉二叉樹中的結點，從根結點開始，一個不多，一個不少的給出所有的結點。

線性結構的遍歷：因為每個結點均只有一個后繼，

所以只有一條搜索路徑。二叉樹的遍歷：二叉樹是非線性結構，每個結點有兩個后繼，則存在如何遍歷，即按什么樣的搜索路徑進行遍歷的問題。二叉樹的遍歷二叉樹存在下述三條搜索路徑：1．先上后下的按層次遍歷；2．先左（子樹）后右（子樹）的遍歷；DLR，LDR，LRD3．先右（子樹）后左（子樹）的遍歷。DRL，RDL，RLD二叉樹的遍歷左子樹右子樹根根左子樹右子樹若二叉樹為空樹，則空操作；否則：（1）訪問根結點（2）先序遍歷左子樹（3）先序遍歷右子樹先序遍歷ABCDEFGHKABCDEFGHKABCDEFGHK先序遍歷ABDCEFABC先序遍歷練習左子樹右子樹根根左子樹右子樹若二叉樹為空樹，則空操作；否則：（1）中序遍歷左子樹；（2）訪問根結點；（3）中序遍歷右子樹中序遍歷ABCDEFGHKABCDEFGHKABDCEHGKF中序遍歷ABDCEFABC中序遍歷練習后序遍歷左子樹右子樹根根左子樹右子樹若二叉樹為空樹，則空操作；否則：（1）后序遍歷左子樹；（2）后序遍歷右子樹；（3）訪問根結點。ABCDEFGHKABCDEFGHKADCBHKGFE后序遍歷ABECD后序遍歷練習層次遍歷ACGBDEFKLHJIMNO0123層號從0層開始，逐層遍歷，同一層，從左往右遍歷遍歷練習ABCDEFGHK寫出下列二叉樹的前序、中序、后序和層次遍歷的結果。二叉樹的結點

private

static

classNode<T>{ Tdata; Node<T>left; Node<T>right; Node(Tdata,Node<T>left,Node<T>right){

this.data=data;

this.left=left;

this.right=right; } }e二叉樹public

classBiTree<T>{

privateNode<T>root;AF∧∧E∧C∧D∧∧B∧由兩棵二叉樹構造新的二叉樹rootABCDEABCEFNrootABCDErootABCEF二叉樹的構造器

publicBiTree(){//建立空樹

}

publicBiTree(Tdata,BiTree<T>leftBiTree,BiTree<T>rightBiTree){

root=newNode<>(data,leftBiTree.root,rightBiTree.root);

leftBiTree.root=rightBiTree.root=null; } BiTree<String>btnull=newBiTree<>(); BiTree<String>btl=newBiTree<>("D",btnull,btnull);

btl=newBiTree<>("B",btl,btnull);

BiTree<String>btr=newBiTree<>("E",btnull,btnull);

btr=newBiTree<>("C",btr,btnull);

btl=newBiTree<>("A",btl,btr);二叉樹的構造器

//使用前序和中序遍歷的結果，構造一顆數(shù)據(jù)為Character的二叉樹，用于構造測試用的二叉樹

@SuppressWarnings("unchecked")

publicBiTree(StringpreString,StringinString){

if(preString.length()==0){//如果不特殊處理，makeBitree將崩潰

root=null; }else{

root=(Node<T>)makeBitree(preString,inString); } } BiTree<Character>btString=newBiTree<>("ABCDEFGHK","BDCAEHGKF");前序遍歷

public

voidpreRootTraversal(){ preRootTraversal(root); }

private

voidpreRootTraversal(Node<T>t){

if(t==null)

return;

//對結點的數(shù)據(jù)進行處理，例如：輸出結點t的數(shù)據(jù) System.out.println(t.data); preRootTraversal(t.left); preRootTraversal(t.right); }∧AF∧∧E∧C∧D∧∧B注意：不是必須要println!!!中序遍歷

public

voidinRootTraversal(){ inRootTraversal(root); }

private

voidinRootTraversal(Node<T>t){

if(t==null)

return; inRootTraversal(t.left);

//對結點的數(shù)據(jù)進行處理，例如：輸出結點t的數(shù)據(jù) System.out.println(t.data); inRootTraversal(t.right); }后序遍歷

public

voidpostRootTraversal(){ postRootTraversal(root); }

private

voidpostRootTraversal(Node<T>t){

if(t==null)

return; postRootTraversal(t.left); postRootTraversal(t.right);

//對結點的數(shù)據(jù)進行處理，例如：輸出結點t的數(shù)據(jù) System.out.println(t.data); }層次遍歷

public

voidlevelTraverse(){

if(root==null)

return; Deque<Node<T>>queue=newLinkedList<>();

queue.offer(root);

while(!queue.isEmpty()){ Node<T>t=queue.poll();

//對結點的數(shù)據(jù)進行處理，例如：輸出結點t的數(shù)據(jù) System.out.println(t.data);

if(t.left!=null)

queue.offer(t.left);

if(t.right!=null)

queue.offer(t.right); } }ABECD階乘-遞歸定義1ifn=02!=2×1!1!=1×0!0!=1n!=n!=n*(n-1)!ifn≥1階乘-遞歸的執(zhí)行過程public

classFactorial{

public

static

longfact(int

n){

if(n==0)

return1;

return

n*fact(n-1); }

public

static

voidmain(String[]args){

long

result=fact(2); System.out.println(result); }}fact(2)fact(1)fact0)遞歸的執(zhí)行過程：同一個方法，多次執(zhí)行，但每次執(zhí)行傳入的參數(shù)不同前序遍歷－執(zhí)行過程

private

voidpreRootTraversal(A){

if(t==null)

return; System.out.println(t.data); preRootTraversal(t.left); preRootTraversal(t.right); }

private

voidpreRootTraversal(B){

if(t==null)

return; System.out.println(t.data); preRootTraversal(t.left); preRootTraversal(t.right); }

private

voidpreRootTraversal(null){

if(t==null)

return; System.out.println(t.data); preRootTraversal(t.left); preRootTraversal(t.right); }

private

voidpreRootTraversal(C){

if(t==null)

return; System.out.println(t.data); preRootTraversal(t.left); preRootTraversal(t.right); }ABDC部分執(zhí)行過程示例：前序遍歷－執(zhí)行過程ABDCpre(A)pre(B)處理Apre(D)pre(null)處理Bpre(C)pre(null)處理Cpre(null)pre(null)處理Dpre(null)pre:preRootTraversal圖中省略了if(t==null)前序遍歷－執(zhí)行過程ABDCt:At:Bt:0t:Ct:0t:0t:Dt:0t:0ABCD可以使用Debug功能觀察函數(shù)的調(diào)用過程

public

voidpreRootTraversal(){ preRootTraversal(root); }

private

voidpreRootTraversal(Node<T>t){

if(t==null)

return;

//對結點的數(shù)據(jù)進行處理，例如：輸出結點t的數(shù)據(jù) System.out.println(t.data); preRootTraversal(t.left); preRootTraversal(t.right); }java的函數(shù)接口高階函數(shù)：函數(shù)的參數(shù)或返回值是函數(shù)的函數(shù)。即函數(shù)也是數(shù)據(jù)。為了能將函數(shù)像數(shù)據(jù)那樣傳遞，javase8提出了函數(shù)接口的概念：

只有1個抽象函數(shù)的接口1、javase8在包java.util.function定義了一系列的函數(shù)接口2、如果方法的參數(shù)的類型是函數(shù)接口，實參可以是函數(shù)引用或Lambda表達式或對象(引用)(這個對象所屬的類實現(xiàn)了函數(shù)接口)。java的函數(shù)接口@FunctionalInterfacepublic

interfaceConsumer<T>{

voidaccept(Tt);

defaultConsumer<T>andThen(Consumer<?superT>after){Objects.requireNonNull(after);

return(Tt)->{accept(t);after.accept(t);};}}、前序遍歷

public

voidpreRootTraversal(Consumer<T>fun){ preRootTraversal(root,fun); }

private

voidpreRootTraversal(Node<T>t,Consumer<T>fun){

if(t==null)

return;

//處理結點t

fun.accept(t.data); preRootTraversal(t.left,fun); preRootTraversal(t.right,fun); }傳入函數(shù)btl.preRootTraversal(System.out::println);//函數(shù)引用 btl.preRootTraversal(x->System.out.println(x));//Lambda表達式btl.preRootTraversal(newTest());//對象publicclassTestimplementsConsumer<Test>{...}遍歷小結1、時間復雜度為O(n)：因為訪問每個結點用的時間是常數(shù)2、空間復雜度O(logn)：因為遞歸要用到系統(tǒng)棧，非遞歸的算法也要用到棧，極端情況會達到O(n)3、1979年，JosephMorris發(fā)明了空間復雜度為O(1)的遍歷算法，利用了二叉鏈中大量的null引用變量非遞歸的遍歷

public

voidinOrderNonRecursively(){

if(root==null)

return; Deque<Node<T>>stackNode=newLinkedList<>(); Node<T>p=root;

for(;;){//對變量p代表的每棵二叉樹做相同的操作

while(p!=null){//向左不斷的分解二叉樹，將以后要訪問的各子二叉樹逐次入棧

stackNode.push(p);

p=p.left; }

//到此，p代表的二叉樹分解到空二叉樹，處理完畢

if(stackNode.isEmpty())

return;

p=stackNode.pop();//從棧中取出下1棵待處理的二叉樹 System.out.println(p.data);//做處理，例如，輸出根結點的值

p=p.right;//繼續(xù)處理它的右子樹 } }中序遍歷如下，其它的見工程結點個數(shù)左子樹右子樹根根左子樹右子樹ABCDEFGHK

public

intcountNode(){

returncountNode(root); }

private

intcountNode(Node<T>t){

if(t==null)

return0;

returncountNode(t.left)+countNode(t.right)+1; }葉子結點個數(shù)ABCDEFGHK

public

intcountLeafNode(){

returncountLeafNode(root); }

private

intcountLeafNode(Node<T>t){

if(t==null)

return0;

if(t.left==null&&t.right==null)

return1;

returncountLeafNode(t.left)+countLeafNode(t.right); }左子樹右子樹根根左子樹右子樹ABCDEFGHK求樹的深度

public

intdepth(){

returndepth(root); }

private

intdepth(Node<T>t){

if(t==null)

return0;

int

left=depth(t.left);

int

right=depth(t.right);

return

left>right?left+1:right+1; }左子樹右子樹根根左子樹右子樹查找二叉樹中的某個結點在樹中查找數(shù)據(jù)元素的值等于x的結點，如果找到，則返回這個結點，否則，返回null。ABECDrootX="C"查找二叉樹中的某個結點

publicNode<T>search(Tx){

returnsearch(root,x); }

privateNode<T>search(Node<T>t,Tx){

if(t==null)

return

null;

if(t.data.equals(x))

return

t; Node<T>result=search(t.left,x);

if(result!=null)

return

result;

returnsearch(t.right,x); }判斷二棵二叉樹相等

public

booleanisEqual(BiTree<T>rhd){

if(this==rhd)return

true;

returnisEqual(this.root,rhd.root); }

private

booleanisEqual(Node<T>t1,Node<T>t2){

if(t1==null&&t2==null)return

true;

if(t1==null&&t2!=null||t1!=null&&t2==null)

return

false;

if(!t1.data.equals(t2.data))

return

false;

returnisEqual(t1.left,t2.left)&&isEqual(t1.right,t2.right); }左子樹右子樹根根左子樹右子樹左子樹右子樹根根左子樹右子樹二叉樹轉換為數(shù)組

//將先序遍歷的結果存入數(shù)組

publicObject[]toArray(){

int

n=countNode();//因為沒有size變量，只能笨辦法 Object[]elements=newObject[n]; toArray(root,elements,0);

return

elements; }二叉樹轉換為數(shù)組

//pos：將以t為根的二叉樹的第1個結點放入數(shù)組array的位置

//方法的返回值：以t為根的樹的結點數(shù),//或者說將t為根的二叉樹向數(shù)組中放入了幾個數(shù)據(jù)

private

inttoArray(Node<T>t,Object[]array,int

pos){

if(t==null)

return0;

array[pos++]=t.data;

int

countLeft=toArray(t.left,array,pos);

int

countRight=toArray(t.right,array,pos+countLeft);

return

countLeft+countRight+1; }poscountLeft右子樹的第1個位置=？根左子樹pos+1二叉樹轉換為數(shù)組

private

inttoArray0(Object[]array){

classState{

int

pos;

voidpreOrder(Node<T>s){

if(s==null)

return;

array[pos++]=s.data; preOrder(s.left); preOrder(s.right); } } States=newState();

s.preOrder(root);

return

s.pos; }使用局部類記錄下一個存放位置

//這里傳入數(shù)組a的主要目的：因為java的語法要求：不能寫newT[]

//所以，傳入a是為了獲取數(shù)組元素的類型

//通過Java的反射機制，Array.newInstance//在運行時，new一個任意類型(不包括基本數(shù)據(jù)類型)的數(shù)組

publicT[]toArrayIn(T[]a){//將前序遍歷結果存入指定的數(shù)組a中

int

size=countNode();

if(a.length<size)

a=(T[])Array.newInstance(a.getClass().getComponentType(),size);

int

n=toArrayIn(root,a,0);

assert(n==size);

if(a.length>size)//因為a的數(shù)組元素個數(shù)多余結點的個數(shù)，為了識別存儲了多少個結點

a[size]=null;

return

a; }二叉樹轉換為數(shù)組copyAF∧∧E∧C∧D∧∧B∧tAF∧∧E∧C∧D∧∧B∧p先復制t的左子樹，再復制t的右子樹，然后生成新的根結點。根元素t右子樹根元素p左子樹右子樹左子樹copycopy

privateNode<T>copy(Node<T>t){//返回復制得到的二叉樹的根結點

if(t==null)

return

null; Node<T>left=copy(t.left); Node<T>right=copy(t.right);

return

newNode<>(t.data,left,right);}復制以t為根的二叉樹clone

publicObjectclone(){

try{ BiTree<T>v=(BiTree<T>)super.clone();

v.root=copy(root);//clone后二者的root引用了相同的node，不行

return

v;}catch(CloneNotSupportedExceptione){

//thisshouldn'thappen,sinceweareCloneable

throw

newInternalError(e);}}輸出根結點到所有葉子結點的路徑ABCDEFGHKABCDABCIAEFGHAEFGKAEFJIJ使用先序遍歷，將先序遍歷的結果保存于棧遇到葉子結點，從棧底到棧頂輸出棧中的數(shù)據(jù)以結點x為根的子樹完成了先序遍歷，將結點x出棧輸出根結點到所有葉子結點的路徑

public

voidpath(){

if(root==null)

return; Deque<Node<T>>stack=newArrayDeque<>(); path(root,stack); }

private

voidpath(Node<T>t,Deque<Node<T>>stack){

if(t==null)

return;

if(t.left==null&&t.right==null){

for(Node<T>p:stack) System.out.print(p.data+""); System.out.println(t.data);

return; }

stack.offerLast(t); path(t.left,stack); path(t.right,stack);

stack.pollLast(); }根據(jù)先序和中序遍歷結果構造二叉樹ABCDEFGHK中序序列：先序序列：BDCAEHGKFABCDEFGHK

BDC

BCD左子樹的中序和先序序列右子樹的中序和先序序列EHGKFEFGHK根據(jù)先序和中序遍歷結果構造二叉樹

publicBiTree(StringpreString,StringinString){

root=(Node<T>)makeBitree(preString,inString); }根據(jù)先序和中序遍歷結果構造二叉樹

publicNode<String>makeBitree(StringpreString,StringinString){ Node<String>left=null,right=null;

if(preString.length()!=1){

//假設各個結點的值不一樣，使用indexOf代替了書上的循環(huán)查找，

int

rootPos=inString.indexOf(preString.charAt(0));

if(roo