數(shù)據(jù)結(jié)構(gòu)及算法基礎(chǔ)樹(Tree)基礎(chǔ)詳解

1、數(shù)據(jù)結(jié)構(gòu)及算法基礎(chǔ)-樹（Tree）（）基礎(chǔ)詳解我們在前面介紹了很多典型的線性結(jié)構(gòu)，如隊列，堆棧，數(shù)組，她們至多只有一個尾節(jié)點。這是非常容易理解的。下面我們要來介紹一個非線性結(jié)構(gòu)，樹（tree）:樹不在是一對一的數(shù)據(jù)結(jié)構(gòu)，而是一對多的非線性連接：leafparent這里有幾個規(guī)定：圖中的結(jié)構(gòu)就像一棵倒過來的樹，最頂部的節(jié)點就是“根節(jié)點（root節(jié)點）”每棵樹至多只有一個根節(jié)點根節(jié)點生出多個孩子節(jié)點，每個孩子節(jié)點只有一個父節(jié)點，每個孩子節(jié)點又生出多個孩子父親節(jié)點（parent）和孩子節(jié)點（child）是相對的沒有孩子節(jié)點的節(jié)點成為葉子節(jié)點（leaf）樹的相關(guān)術(shù)語：1）節(jié)點的度：個節(jié)點直接含有的子樹

2、個數(shù)，上圖中3的度為2,10的度為1;2）樹的度：個樹里面節(jié)點的度的最大值。例如上圖的樹的度為2;3）節(jié)點的層次：從根節(jié)點開始算起，根節(jié)點算第一層，上圖中3為第二層，13為第四層;4）樹的高度:從葉節(jié)點開始，從下往上增加；樹的深度：從根節(jié)點開始，從上往下增加；上看給出的信息是非常非常重要的，一定要熟練掌握。由上述描述，我們一般可以通過兩種方式實現(xiàn)一棵簡單的樹:1)數(shù)組實現(xiàn)。packagetreeTest;publicclassTreeNodebyArrayprivateitemmData;privateintmParent;publicTreeNodebyArray(itemdata,intp

3、arent)mData=data;mParent=parent;publicitemgetData()returnmData;publicintgetMParent()returnmParent;publicvoidsetData(itemdata)mData=data;publicvoidsetParent(intparent)mParent=parent;publicstaticvoidmain(Stringargs)TreeNodearrayTree=newTreeNode10;2）鏈表實現(xiàn)：packagetreeTest;publicclassTreeNodebyLinkListpri

4、vateitemmData;privateTreeNodebyLinkListparent;privateTreeNodebyLinkListkid;publicTreeNodebyLinkList(itemdata,TreeNodebyLinkListparent)mData=data;this.parent=parent;publicitemgetData()returnmData;publicvoidsetData(itemdata)mData=data;publicTreeNodebyLinkListgetParent()returnparent;publicvoidsetParent(TreeNodebyLinkListparent)this.parent=parent;publicTreeNodebyLinkListgetChild()returnkid;publicvoidsetChild(TreeNodebyLinkListkid)this.kid=kid;publicstaticvoidmain(Stringargs)LinkedListlinkedTree=