樹和二叉樹二叉樹遍歷線索二叉樹二叉搜索樹二叉樹的計數-資料下載頁

　　

【正文】 e *next。 }。 template class T struct CTNode { T data。 ChildNode *firstChild。}。 template class T class CTree { CTNodeT node[MAX_TREE_SIZE]。 int n。 ……}。 帶雙親的 A B C D E F G H I 0 1 2 3 4 5 6 7 8 A B C ^ D E ^ F ^ G H ^ I ^ 1 2 3 7 8 4 5 6 0 1 2 3 4 5 6 7 8 1 0 0 0 1 1 3 5 5 孩子表示法 孩子兄弟表示法（ 二叉樹表示法 ） 結點 : 數據 孩子 兄弟 A B C D E F G H I data firstchild nextsibling A B C D E F G H I 孩子兄弟表示法（ 二叉樹表示法 ） 結點 : 數據 孩子 兄弟 A B C D E F G H I data firstchild nextsibling A B C D E F G H I //孩子兄弟表示 結點類的定義 template class T CSTree。 template class T class CSNode { public: T data。 CSNodeT *firstChild, *nextSibling。 CSNode( T item=0, CSNodeT*fc=NULL, CSNodeT*ns=NULL)。 friend class T CSTree。 }。 //孩子兄弟表示 類的定義 template class T class CSTree { CSNodeT *root, *current。 int size。 CSNodeT *GetCSNode(const Tamp。 item, CSNodeT *fcptr,CSNodeT *nsptr)。 void FreeCSNode(CSNodeT *p)。 CSNodeT *CopyTree(CSNodeT *t)。 void DeleteTree(CSNodeT *t)。 CSNodeT *FindNode(const Tamp。 item, CSNodeT* amp。 pre) const。 public: CSTree(void)。 CSTree(const CSTreeTamp。 tree)。 ~CSTree(void)。 CSTreeTamp。 operator= (const CSTreeTamp。 rhs)。 int Find(Tamp。 item)。 void Insert(const Tamp。 item)。 void Delete(const Tamp。 item)。 void ClearList(void)。 int ListEmpty(void) const。 int ListSize(void) const。 void Update(const Tamp。 item)。 CSNodeT *GetRoot(void) const。 }。 森林與二叉樹的轉換 A B C D E F G H I J A B C D E F G H I J 森林與二叉樹的轉換的形式定義 ?森林 轉換成 二叉樹 的 規則： 設 F={T1,T2,Tm}是森林， 可以轉換成二叉樹 B={root, LB, RB} (1) F空， m=0, 則 B是空樹； (2) F非空， m≠0, 則 root=T1的根， LB是 T1去掉根后的子樹組成的森林 F1={T11,T12,,T1m}轉換成的二叉樹； RB是森林 F’={T2,T3,,Tm}轉換成的二叉樹。 二叉樹 轉換成 森林 的規則： （遞歸定義） 設 B={root, LB, RB}是二叉樹 可以轉換成森林 F={T1,T2,Tm}， (1) B是空樹，則 F空； (2) B非空， 則 m≠0, T1的根 =root ， T1去掉根后的子樹組成的 森林 F1={T11,T12,,T1m} 是 LB轉換成的； 森林 F’={T2,T3,,Tm} 是 RB轉換成的。 樹的遍歷 （與二叉樹不同） 深度優先 1。 先根遍歷 先訪問根結點， 再先根遍歷根的每一棵子樹。 2。 后根遍歷 先后根遍歷根的每一棵子樹， 再訪問根。 二叉樹的先根遍歷就是先序遍歷 后根遍歷就是后序遍歷 廣度優先 ?先訪問根結點 ?再依次訪問第一層所有結點 ?再依次訪問第二層所有結點 直到訪問完所有結點 先根遍歷 ABEFCDGHI A B C D E F G H I 后根遍歷 EFBCHIGDA 廣度優先 ABCDEFGHI 先根遍歷的算法 void PreOrderTraverse(CSNodeT*t,void visit(T item)) { if(t!=NULL) { visit(tdata)。 PreOrderTraverse(tfirstChild,visit)。 PreOrderTraverse(tnextSibling,visit)。 } } 森林的遍歷 先序遍歷森林 若森林非空 先訪問第一棵樹的根結點， 再先序遍歷第一棵樹根的子森林， 再先序遍歷除去第一棵樹后剩余 的子森林。 轉換成二叉樹后 與二叉樹的先序遍歷相同 中序遍歷森林 若森林非空 中序遍歷第一棵樹根的子森林 訪問第一棵樹的根 中序遍歷去掉第一棵樹后剩余的子森林 轉換成二叉樹后與二叉樹的中序遍歷相同 后序遍歷森林 若森林非空 后序遍歷第一棵樹根的子森林 后序遍歷去掉第一棵樹后剩余的子森林 訪問第一棵樹的根 轉換成二叉樹后與二叉樹的后序遍歷相同 先序遍歷 A B C D E F G H I J ABCDEFGHIJ 中序遍歷 BCDAFEHJIG 后序遍歷 DCBFJIHGEA A B C D E F G H I J 先序遍歷 ABCDEFGHIJ 中序遍歷 BCDAFEHJIG 后序遍歷 DCBFJIHGEA 七、堆 Heap (改進了的樹型排序） （極小） 堆的定義： n個元素的完全二叉樹，每個結點都小于其子結點。 13 49 27 97 65 76 38 用一維數組表示極小堆 0 1 2 3 4 5 6 13 49 27 97 65 38 76 13 49 27 97 65 76 38 A[i] ≤A[2i+1], A[i] ≤A[2i+1+1], 堆排序 堆排序的過程 ， 2. 輸出頂點元素后，調整并重建堆， 3. 重復 。 先作第二步：輸出并調整重建堆 13 49 27 97 65 76 38 輸出堆頂元素 13，用堆末元素取代， 將元素 76下移與子結點中較小的一個交換， 向下過濾， 直至葉結點，重復第 2步直至全部輸出。 76 13 76 76 7627 27 76 76 76 38 7638第一步 建堆 從最末一個非葉結點 A[n1/2]開始 向下過濾 直至堆頂 49 38 65 97 76 27 13 49 49971365 13 494927include include template class T class Heap {private: T *hlist。 int inArray。 // max number allowed and current size of heap int maxheapsize。 int heapsize。 // identifies end of list // error message utility function void error(char errmsg[])。 // utility functions for Delete/Insert to restore heap void FilterDown(int i)。 void FilterUp(int i)。 public: Heap(int maxsize)。 // create empty heap Heap(T arr[],int n)。 // heapify arr Heap(const HeapTamp。 H)。 // copy constructor ~Heap(void)。 // destructor // overloaded operators: =, [], T* HeapTamp。 operator= (const HeapTamp。 rhs)。 const Tamp。 operator[](int i)。 // list methods int ListSize(void) const。 int ListEmpty(void) const。 int ListFull(void) const。 void Insert(const Tamp。 item)。 T Delete(void)。 void ClearList(void)。 }。 // print error message and terminate the program template class T void HeapT::error(char errmsg[]) { cerr errmsg endl。 exit(1)。 } template class T void HeapT::FilterDown (int i) { int currentpos, childpos。 T target。 // start at i and set its value as the target currentpos = i。 target = hlist[i]。 childpos = 2 * i + 1。 while (childpos heapsize) // check for end of list { if ((childpos+1 heapsize) amp。amp。 (hlist[childpos+1] = hlist