葉老師版數(shù)據(jù)結(jié)構(gòu)二叉樹各種函數(shù).doc

/二叉樹類#include BinaryNode.h /二叉樹的二叉鏈表結(jié)點(diǎn)類#include SeqStack.h /順序棧#include LinkedStack.h /鏈?zhǔn)綏?include SeqQueue.h /順序循環(huán)隊(duì)列/#include LinkedQueue.h /鏈?zhǔn)疥?duì)列 template class BinaryTree /二叉樹類 public: BinaryNode *root; /指向根結(jié)點(diǎn) BinaryTree(); /構(gòu)造空二叉樹 BinaryTree(T prelist, int n); /以標(biāo)明空子樹的先根序列構(gòu)造一棵二叉樹 BinaryTree(T prelist, T inlist, int n); /以先根和中根序列構(gòu)造二叉樹 BinaryTree(); /析構(gòu)函數(shù) bool isEmpty(); /判斷是否空二叉樹 void preOrder(); /先根次序遍歷二叉樹 void inOrder(); /中根次序遍歷二叉樹 void postOrder(); /后根次序遍歷二叉樹 int count(); /返回二叉樹的結(jié)點(diǎn)個(gè)數(shù) int height(); /返回二叉樹的高度 BinaryNode* search(T value); /查找首次出現(xiàn)的值為value的結(jié)點(diǎn) BinaryNode* getParent(BinaryNode *node); /返回node結(jié)點(diǎn)的父母結(jié)點(diǎn) BinaryNode* insert(BinaryNode *p, T value, bool leftChild=true); /插入value作為p結(jié)點(diǎn)的孩子 void remove(BinaryNode *p, bool leftChild=true); /刪除p結(jié)點(diǎn)的左或右子樹 void printGList(); /以廣義表表示輸出二叉樹 void inOrderTraverse(); /中根次序遍歷二叉樹的非遞歸算法 void levelOrder(); /按層次遍歷二叉樹 private: void preOrder(BinaryNode *p); /先根次序遍歷以p結(jié)點(diǎn)為根的子樹 void inOrder(BinaryNode *p); /中根次序遍歷以p結(jié)點(diǎn)為根的子樹 void postOrder(BinaryNode *p); /后根次序遍歷以p結(jié)點(diǎn)為根的子樹 void destroy(BinaryNode *p); /撤銷二叉樹 BinaryNode* create(T prelist, int n, int &i); /以標(biāo)明空子樹的先根遍歷序列創(chuàng)建子樹 BinaryNode* create(T prelist, T inlist, int preStart, int inStart, int n); /以先根和中根序列創(chuàng)建一棵子樹 int count(BinaryNode *p); /返回以p結(jié)點(diǎn)為根的子樹結(jié)點(diǎn)個(gè)數(shù) int height(BinaryNode *p); /返回以p結(jié)點(diǎn)為根的子樹高度 BinaryNode* search(BinaryNode *p, T value); /在以p為根的子樹中查找首次出現(xiàn)的值為value的結(jié)點(diǎn) BinaryNode* getParent(BinaryNode *p, BinaryNode *node); void printGList(BinaryNode *p); /以廣義表表示輸出以p結(jié)點(diǎn)為根的子樹/第6章習(xí)題 public: void leaf(); /遍歷輸出葉子結(jié)點(diǎn) int countLeaf(); /返回二叉樹的葉子結(jié)點(diǎn)數(shù) bool replace(T old, T value); /將首次出現(xiàn)的值為old結(jié)點(diǎn)值替換為value void replaceAll(T old, T value); /將值為old的結(jié)點(diǎn)全部替換為value int operator=(BinaryTree &bitree); /比較兩棵二叉樹是否相等，重載運(yùn)算符= BinaryTree(BinaryTree &bitree); /由已知的bitree構(gòu)造二叉樹 void preOrderTraverse(); /先根次序遍歷二叉樹的非遞歸算法 bool isSorted(); /判斷一棵二叉樹是否為二叉排序樹 private: void leaf(BinaryNode *p); /輸出以p結(jié)點(diǎn)為根的子樹的所有葉子結(jié)點(diǎn) int countLeaf(BinaryNode *p); /返回以p結(jié)點(diǎn)為根的子樹的葉子結(jié)點(diǎn)個(gè)數(shù) void replaceAll(BinaryNode *p, T old, T value); /在以p為根的子樹中實(shí)現(xiàn)全部替換 bool equals(BinaryNode *p, BinaryNode *q); /判斷以p和q結(jié)點(diǎn)為根的兩棵子樹是否相等 BinaryNode* copy(BinaryNode *p); /復(fù)制以p根的子二叉樹 /第8章習(xí)題 bool isSorted(BinaryNode* p);template BinaryTree:BinaryTree() /構(gòu)造空二叉樹 root = NULL;template bool BinaryTree:isEmpty() /判斷是否空二叉樹 return root=NULL;/3. 二叉樹的先根、中根和后根次序遍歷算法template void BinaryTree:preOrder() /先根次序遍歷二叉樹 cout先根次序遍歷二叉樹: ; preOrder(root); /調(diào)用先根次序遍歷二叉樹的遞歸函數(shù) coutendl; template void BinaryTree:preOrder(BinaryNode *p) /先根次序遍歷以p結(jié)點(diǎn)為根的子樹，遞歸函數(shù) if (p!=NULL) /若二叉樹不空 coutdataleft); /按先根次序遍歷當(dāng)前結(jié)點(diǎn)的左子樹，遞歸調(diào)用 preOrder(p-right); /按先根次序遍歷當(dāng)前結(jié)點(diǎn)的右子樹，遞歸調(diào)用 template void BinaryTree:inOrder() /中根次序遍歷二叉樹 cout中根次序遍歷二叉樹: ; inOrder(root); /調(diào)用中根次序遍歷二叉樹的遞歸函數(shù) coutendl; template void BinaryTree:inOrder(BinaryNode *p) /中根次序遍歷以p結(jié)點(diǎn)為根的子樹，遞歸函數(shù) if (p!=NULL) inOrder(p-left); coutdataright); template void BinaryTree:postOrder() /后根次序遍歷二叉樹 cout后根次序遍歷二叉樹: ; postOrder(root); /調(diào)用后根次序遍歷二叉樹的遞歸函數(shù) coutendl; template void BinaryTree:postOrder(BinaryNode *p) /后根次序遍歷以p結(jié)點(diǎn)為根的子樹，遞歸函數(shù) if (p!=NULL) postOrder(p-left); postOrder(p-right); coutdata ; /4. 基于遍歷的操作template BinaryTree:BinaryTree() /析構(gòu)函數(shù) cout撤銷二叉樹: ; destroy(root); coutendl;template void BinaryTree:destroy(BinaryNode *p) /撤銷以p結(jié)點(diǎn)為根的子樹，后根次序遍歷 if (p!=NULL) destroy(p-left); destroy(p-right); coutdata ; /顯示撤銷結(jié)點(diǎn)的次序 delete p; /【例6.1】 構(gòu)造并遍歷二叉樹。template int BinaryTree:count() /返回二叉樹的結(jié)點(diǎn)個(gè)數(shù) return count(root);template int BinaryTree:count(BinaryNode *p) /返回以p結(jié)點(diǎn)為根的子樹結(jié)點(diǎn)個(gè)數(shù) if (p=NULL) return 0; else return 1+count(p-left)+count(p-right);template int BinaryTree:height() /返回二叉樹的高度 return height(root);template int BinaryTree:height(BinaryNode *p) /返回以p結(jié)點(diǎn)為根的子樹高度，后根次序遍歷 if (p!=NULL) int lh = height(p-left); /求左子樹的高度 int rh = height(p-right); return (lh=rh) ? lh+1 : rh+1; return 0;template BinaryNode* BinaryTree:search(T value) /查找首次出現(xiàn)的值為value結(jié)點(diǎn) return search(root, value);template BinaryNode* BinaryTree:search(BinaryNode *p, T value) /在以p為根的子樹中查找 /先根次序遍歷查找值為value的結(jié)點(diǎn)，返回首次出現(xiàn)結(jié)點(diǎn)指針，若未找到返回NULL BinaryNode *find=NULL; /記載找到結(jié)點(diǎn) if (p!=NULL) if (p-data=value) return p; /查找成功，返回結(jié)點(diǎn)指針 find = search(p-left, value); /在左子樹中查找，find指向找到結(jié)點(diǎn)，遞歸調(diào)用 if (find=NULL) /若在左子樹中未找到 find = search(p-right, value); /則繼續(xù)在右子樹中查找，遞歸調(diào)用 return find; /返回查找結(jié)果template BinaryNode* BinaryTree:getParent(BinaryNode *node) /返回node結(jié)點(diǎn)的父母結(jié)點(diǎn)指針 /若空樹、未找到或node為根，返回NULL if (root=NULL | node=NULL | node=root) return NULL; return getParent(root, node);template BinaryNode* BinaryTree:getParent(BinaryNode *p, BinaryNode *node) /在以p為根的子樹中查找并返回node結(jié)點(diǎn)的父母結(jié)點(diǎn)指針 BinaryNode *find=NULL; if (p!=NULL) if (p-left=node | p-right=node) return p; find = getParent(p-left, node); if (find=NULL) find = getParent(p-right, node); return find;/5. 構(gòu)造二叉樹template BinaryTree:BinaryTree(T prelist, T inlist, int n) /以先根和中根序列構(gòu)造二叉樹 /n指定序列長(zhǎng)度 root = create(prelist, inlist, 0, 0, n);template BinaryNode* BinaryTree:create(T prelist, T inlist, int preStart,int inStart, int n) /以先根和中根序列創(chuàng)建一棵子樹，子樹根結(jié)點(diǎn)是prelisti，返回根結(jié)點(diǎn)指針 BinaryNode *p=NULL; if (n0) T elem=prelistpreStart; /根結(jié)點(diǎn)值 p = new BinaryNode(elem); /創(chuàng)建結(jié)點(diǎn) int i=0; while (ileft = create(prelist, inlist, preStart+1, inStart, i); /創(chuàng)建左子樹 p-right = create(prelist, inlist, preStart+i+1, inStart+i+1, n-1-i);/創(chuàng)建右子樹 return p;template BinaryTree:BinaryTree(T prelist, int n) /以標(biāo)明空子樹的先根序列構(gòu)造二叉樹 int i=0; root=create(prelist, n, i);template BinaryNode* BinaryTree:create(T prelist, int n, int &i) /以標(biāo)明空子樹的先根次序遍歷序列創(chuàng)建一棵子樹，子樹根結(jié)點(diǎn)是prelisti，返回根結(jié)點(diǎn)指針 BinaryNode *p=NULL; if (in) T elem = prelisti; i+; if (elem!=NULL) /不能elem!=，因?yàn)門不一定是char p = new BinaryNode(elem); /創(chuàng)建結(jié)點(diǎn) p-left = create(prelist, n, i); /創(chuàng)建左子樹 p-right = create(prelist, n, i); /創(chuàng)建右子樹 return p;/【例6.2】 輸出二叉樹中指定結(jié)點(diǎn)的所有祖先結(jié)點(diǎn)。/【例6.3】 二叉樹的廣義表表示。template void BinaryTree:printGList() /以廣義表表示輸出二叉樹 printGList(root); coutendl;template void BinaryTree:printGList(BinaryNode *p) /以廣義表表示輸出以p結(jié)點(diǎn)為根的子樹 if (p=NULL) cout; else coutdata; if (p-left!=NULL | p-right!=NULL) coutleft); coutright); cout); /6. 二叉樹的插入和刪除操作template BinaryNode* BinaryTree:insert(BinaryNode *p, T value, bool leftChild) /插入value作為p結(jié)點(diǎn)的孩子 /若leftChild=true，插入結(jié)點(diǎn)作為左孩子，否則作為右孩子 BinaryNode *q=NULL; if (p!=NULL) if (leftChild) q = new BinaryNode(value, p-left, NULL); p-left = q; else q = new BinaryNode(value, NULL, p-right); p-right = q; return q; template void BinaryTree:remove(BinaryNode *p, bool leftChild) /刪除p結(jié)點(diǎn)的左或右子樹 /若leftChild為true，刪除左子樹，否則刪除右子樹 if (p!=NULL) if (leftChild) destroy(p-left); /撤銷左子樹 p-left = NULL; else destroy(p-right); /撤銷右子樹 p-right = NULL; /7. 二叉樹遍歷的非遞歸算法template void BinaryTree:preOrderTraverse() /先根次序遍歷二叉樹的非遞歸算法 cout先根次序遍歷（非遞歸）： ; SeqStackBinaryNode* stack; /創(chuàng)建一個(gè)空棧 BinaryNode *p = root; while (p!=NULL | !stack.isEmpty() /p非空或棧非空時(shí) if (p!=NULL) coutdataleft; /進(jìn)入左子樹 else /p為空且棧非空時(shí) p = stack.pop(); /p指向出棧結(jié)點(diǎn) p = p-right; /進(jìn)入右子樹 coutendl; template void BinaryTree:inOrderTraverse() /中根次序遍歷二叉樹的非遞歸算法 cout中根次序遍歷（非遞歸）： ; LinkedStackBinaryNode* stack; /創(chuàng)建一個(gè)空棧 BinaryNode *p = root; while (p!=NULL | !stack.isEmpty() /p非空或棧非空時(shí) if (p!=NULL) stack.push(p); /p結(jié)點(diǎn)入棧 p = p-left; /進(jìn)入左子樹 else /p為空且棧非空時(shí) p = stack.pop(); /p指向出棧結(jié)點(diǎn) coutdataright; /進(jìn)入右子樹 coutendl; /后根次序未寫/8. 二叉樹的層次遍歷template void BinaryTree:levelOrder() /按層次遍歷二叉樹 cout層次遍歷： ; SeqQueueBinaryNode* que; /創(chuàng)建一個(gè)空隊(duì)列/ LinkedQueueBinaryNode* que; /創(chuàng)建一個(gè)空隊(duì)列 BinaryNode *p=root; while (p!=NULL) coutdataleft!=NULL) que.enqueue(p-left); /p的左孩子結(jié)點(diǎn)入隊(duì) if (p-right!=NULL) que.enqueue(p-right); /p的右孩子結(jié)點(diǎn)入隊(duì) if (!que.isEmpty() p = que.dequeue(); /p指向出隊(duì)結(jié)點(diǎn) else p = NULL; coutendl;/第6章習(xí)題template void BinaryTree:leaf() /遍歷輸出葉子結(jié)點(diǎn) leaf(root);template void BinaryTree:leaf(BinaryNode *p) /輸出以p結(jié)點(diǎn)為根的子樹的所有葉子結(jié)點(diǎn) /先根次序遍歷算法，中根、后根次序遍歷算法也可，結(jié)果一樣 if (p!=NULL) if (p-left=NULL & p-right=NULL) coutdataleft); leaf(p-right); template int BinaryTree:countLeaf() /返回二叉樹的葉子結(jié)點(diǎn)數(shù) return countLeaf(root);template int BinaryTree:countLeaf(BinaryNode *p) /返回以p結(jié)點(diǎn)為根的子樹的葉子結(jié)點(diǎn)個(gè)數(shù) if (p=NULL) return 0; if (p-left=NULL & p-right=NULL) return 1; return countLeaf(p-left)+countLeaf(p-right);template bool BinaryTree:replace(T old, T value) /將首次出現(xiàn)的值為old結(jié)點(diǎn)值替換為value BinaryNode *find = search(old); /查找值為old的結(jié)點(diǎn) if (find!=NULL) find-data = value; /替換結(jié)點(diǎn)元素值 return find!=NULL; template void BinaryTree:replaceAll(T old, T value) /將值為old的結(jié)點(diǎn)全部替換為value replaceAll(root, old, value);template void BinaryTree:replaceAll(BinaryNode *p, T old, T value) /在以p為根的子樹中實(shí)現(xiàn)全部替換 if (p!=NULL) if(p-data=old) p-data = value; /替換 replaceAll(p-left, old, value); replaceAll(p-right, old, value); template int BinaryTree:operator=(BinaryTree &bitree) /比較兩棵二叉樹是否相等，重載運(yùn)算符= return equals(this