數(shù)據(jù)結(jié)構(gòu)樹、圖、查找、排序數(shù)據(jù)結(jié)構(gòu)中的樹圖查找排序數(shù)據(jù)結(jié)構(gòu)樹、圖、查找、排序樹的定義樹:是n(n≥0)個(gè)結(jié)點(diǎn)的有限集合。如果該集合為空,稱為空樹。在任意一棵非空樹中1)有且僅有一個(gè)特定的稱為根結(jié)點(diǎn)(root)的結(jié)點(diǎn)其他結(jié)點(diǎn)可分為若干個(gè)互不相交的子集,而且每一個(gè)子集本身又是一棵樹,稱為根的子樹。遞歸定義基本術(shù)語結(jié)點(diǎn):數(shù)據(jù)元素+若干指向子樹的分支結(jié)點(diǎn)的度:結(jié)點(diǎn)分支的個(gè)數(shù),即子樹的數(shù)目如:A的度-3;B的度-2;K的度-0;樹的度:樹中所有結(jié)點(diǎn)的度的最大值如:樹的度為3;葉子結(jié)點(diǎn):度為零的結(jié)點(diǎn),也稱終端結(jié)點(diǎn)如例:K,L,F,G,M,I,J為終端結(jié)點(diǎn)分支結(jié)點(diǎn):度大于零的結(jié)點(diǎn)如例:A,B,C,D,E樹的定義樹:是n(n≥0)個(gè)結(jié)點(diǎn)的有限集合。如果該集合為空,稱為空樹。在任意一棵非空樹中1)有且僅有一個(gè)特定的稱為根結(jié)點(diǎn)(root)的結(jié)點(diǎn)其他結(jié)點(diǎn)可分為若干個(gè)互不相交的子集,而且每一個(gè)子集本身又是一棵樹,稱為根的子樹。遞歸定義基本術(shù)語結(jié)點(diǎn):數(shù)據(jù)元素+若干指向子樹的分支結(jié)點(diǎn)的度:結(jié)點(diǎn)分支的個(gè)數(shù),即子樹的數(shù)目如:A的度-3;B的度-2;K的度-0;樹的度:樹中所有結(jié)點(diǎn)的度的最大值如:樹的度為3;葉子結(jié)點(diǎn):度為零的結(jié)點(diǎn),也稱終端結(jié)點(diǎn)如例:K,L,F,G,M,I,J為終端結(jié)點(diǎn)分支結(jié)點(diǎn):度大于零的結(jié)點(diǎn)如例:A,B,C,D,E線性結(jié)構(gòu)樹型結(jié)構(gòu)第一個(gè)數(shù)據(jù)元素根結(jié)點(diǎn)(無前驅(qū)(無前驅(qū))最后一個(gè)數(shù)據(jù)元素≈多個(gè)葉子結(jié)點(diǎn)(無后繼)(無后繼)其它數(shù)據(jù)元素其它數(shù)據(jù)元素(一個(gè)前驅(qū)、(一個(gè)前驅(qū)個(gè)后繼多個(gè)后繼)7.2二叉樹匚二叉樹的五種基本形態(tài):空樹只含根結(jié)點(diǎn)左右子樹均不右子樹為空樹左子樹為空樹為空樹NRR特殊的二叉樹:滿二叉樹滿二叉樹:指的是深度為k且含有2k-1個(gè)結(jié)點(diǎn)的二叉樹。24(5(6(78(910①①213145深度為3,節(jié)點(diǎn)數(shù)=23-1=7深度為4,節(jié)點(diǎn)數(shù)=24-1=15特點(diǎn):1)每一層上的結(jié)點(diǎn)數(shù)都是最大結(jié)點(diǎn)數(shù)2)葉子結(jié)點(diǎn)都在最后一層。特殊的二叉樹:完全二叉樹完全二叉樹:樹中所含的n個(gè)結(jié)點(diǎn)和滿二叉樹中編號為1至n的結(jié)點(diǎn)一一對應(yīng)