一、數(shù)組實(shí)現(xiàn)二叉樹(下標(biāo)從0開始)
#include <stdio.h> typedef struct _TreeNode{ int data; bool IsEmpty; //結(jié)點(diǎn)是否為空 // 因?yàn)槲覀兊亩鏄洳灰欢ㄊ菨M二叉樹，中間可能有一些節(jié)點(diǎn)不存在 // 值為1代表空 }TreeNode; // 初始化 void InitTreeNode(TreeNode t[],int len){ for(int i=0;i<len;i++) t[i].IsEmpty = 1; } bool IsEmpty(TreeNode t[],int len,int idx){ if(idx >= len || idx < 0) return 1; // 修改為0 return t[idx].IsEmpty; } // father = (child-1)/2 or father = child/2 - 1 int findFather(TreeNode t[],int len,int idx){ if(idx == 0) return -1; //特判根節(jié)點(diǎn)沒(méi)有父節(jié)點(diǎn) // 特判也修改為0 int fatheridx = (idx-1) / 2; if(IsEmpty(t,len,fatheridx)) return -1; return fatheridx; } // lchild = father*2 + 1 int findLchild(TreeNode t[],int len,int idx){ int lchild = idx*2 + 1; if(IsEmpty(t,len,lchild)) return -1; return lchild; } // rchild = father*2+2 int findRchild(TreeNode t[],int len,int idx){ int rchild = idx*2 + 2; if(IsEmpty(t,len,rchild)) return -1; return rchild; } //實(shí)現(xiàn)前序遍歷, 從下表為idx的節(jié)點(diǎn)開始前序遍歷 int PreorderTree(TreeNode t[],int len,int idx){ if(IsEmpty(t,len,idx)) return 0; printf("%d\n",t[idx].data); PreorderTree(t,len,findLchild(t,len,idx)); PreorderTree(t,len,findRchild(t,len,idx)); return 0; } int InorderTree(TreeNode t[],int len,int idx){ if(IsEmpty(t,len,idx)) return 0; InorderTree(t,len,findLchild(t,len,idx)); printf("%d\n",t[idx].data); InorderTree(t,len,findRchild(t,len,idx)); return 0; } int PostorderTree(TreeNode t[],int len,int idx){ if(IsEmpty(t,len,idx)) return 0; PostorderTree(t,len,findLchild(t,len,idx)); PostorderTree(t,len,findRchild(t,len,idx)); printf("%d\n",t[idx].data); return 0; } int main(){ TreeNode Td[100]; // 這里的二叉樹節(jié)點(diǎn)要從0開始 int fatheridx; int testLen = 7; // IsEmpty 的判斷是 >=Len 所以這里加一個(gè)1 for(int i=0;i<=testLen;i++){ Td[i].data = i+1; Td[i].IsEmpty = 0; } PreorderTree(Td,testLen,0); // InorderTree(Td,testLen,0); // PostorderTree(Td,testLen,0); return 0; }
二、數(shù)組實(shí)現(xiàn)二叉樹(下標(biāo)從1開始)
#include <stdio.h> typedef struct _TreeNode{ int data; bool IsEmpty; //結(jié)點(diǎn)是否為空 // 因?yàn)槲覀兊亩鏄洳灰欢ㄊ菨M二叉樹，中間可能有一些節(jié)點(diǎn)不存在 // 值為1代表空 }TreeNode; // 初始化 void InitTreeNode(TreeNode t[],int len){ for(int i=0;i<len;i++) t[i].IsEmpty = 1; } bool IsEmpty(TreeNode t[],int len,int idx){ if(idx >= len || idx < 1) return 1; return t[idx].IsEmpty; } // father = child / 2 int findFather(TreeNode t[],int len,int idx){ // if(idx == 1) return -1; //特判根節(jié)點(diǎn)沒(méi)有父節(jié)點(diǎn) ，不加也沒(méi)事，但下表從0開始的時(shí)候必須加 int fatheridx = idx / 2; if(IsEmpty(t,len,fatheridx)) return -1; return fatheridx; } // lchild = father*2 int findLchild(TreeNode t[],int len,int idx){ int lchild = idx*2; if(IsEmpty(t,len,lchild)) return -1; return lchild; } // rchild = father*2+1 int findRchild(TreeNode t[],int len,int idx){ int rchild = idx*2+1; if(IsEmpty(t,len,rchild)) return -1; return rchild; } //實(shí)現(xiàn)前序遍歷, 從下表為idx的節(jié)點(diǎn)開始前序遍歷 int PreorderTree(TreeNode t[],int len,int idx){ if(IsEmpty(t,len,idx)) return 0; printf("%d\n",t[idx].data); PreorderTree(t,len,findLchild(t,len,idx)); PreorderTree(t,len,findRchild(t,len,idx)); return 0; } int InorderTree(TreeNode t[],int len,int idx){ if(IsEmpty(t,len,idx)) return 0; InorderTree(t,len,findLchild(t,len,idx)); printf("%d\n",t[idx].data); InorderTree(t,len,findRchild(t,len,idx)); return 0; } int PostorderTree(TreeNode t[],int len,int idx){ if(IsEmpty(t,len,idx)) return 0; PostorderTree(t,len,findLchild(t,len,idx)); PostorderTree(t,len,findRchild(t,len,idx)); printf("%d\n",t[idx].data); return 0; } int main(){ TreeNode Td[100]; // 這里的二叉樹節(jié)點(diǎn)要從一開始 int fatheridx; int testLen = 7+1; // IsEmpty 的判斷是 >=Len 所以這里加一個(gè)1 for(int i=1;i<=testLen;i++){ Td[i].data = i; Td[i].IsEmpty = 0; } PreorderTree(Td,testLen,1); // InorderTree(Td,testLen,1); // PostorderTree(Td,testLen,1); return 0; }
三、并查集及其優(yōu)化思路
#include <stdio.h> #define MAXSIZE 50 int UFSets[MAXSIZE]; void InitUFSets(int S[]){ for(int i=0;i<MAXSIZE;i++){ S[i] = -1; } } int find(int S[],int x){ if(S[x] == -1) return x; // -1說(shuō)明到底了 return find(S,S[x]); } int pathCompFind(int S[],int x){ // 路徑壓縮策略優(yōu)化Find 操作 if(S[x] >= 0){ S[x] = find(S,S[x]); return S[x]; } return x; } bool UnionElem(int S[],int elem1,int elem2){ //王道書上是直接合并的root，而不是元素成員 int first = find(S,elem1); int second = find(S,elem2); if(first != second){ printf("%d -- %d\n",first,second); S[second] = first; return 1; } return 0; } bool UnionRoot(int S[],int Root1,int Root2){ if(Root1 == Root2) return 0; //比較兩個(gè)根是否來(lái)自同一集合 S[Root2] = Root1; // 將根Root2連接到Root1上 return 1; } bool optUnionRoot(int S[],int Root1,int Root2){ if(Root1 == Root2) return 0; if(S[Root2] > S[Root1]){ // Root2 結(jié)點(diǎn)數(shù)更少 // 因?yàn)槌跏蓟臅r(shí)候S的值全為 -1 所以 若S[Root1]與S[Root2]相加后為更小的負(fù)數(shù) //較小的樹，樹較大，這也是為什么 S[Root1] >= S[Root2]時(shí) 卻把Root2合并到Root1中的原因 S[Root1] += S[Root2]; // 累加節(jié)點(diǎn)個(gè)數(shù) S[Root2] = Root1; }else{ S[Root2] += S[Root1]; S[Root1] = Root2; } return 1; } void debug(){ for(int i=0;i<MAXSIZE;i++){ printf("%d ",UFSets[i]); } puts(""); } int main(){ InitUFSets(UFSets); int arr[100] = {0,1,2,3,4,5,6,7,8,9}; for(int i=0;i<=10;i++){ UnionElem(UFSets,arr[i*2],arr[i*2+1]); // 0 -- 1 // 2 -- 3 // 4 -- 5 // 6 -- 7 // 8 -- 9 } UnionElem(UFSets,1,3); UnionElem(UFSets,5,7); // 0 -- 1 // 2 -- 3 // 4 -- 5 // 6 -- 7 // 8 -- 9 // 0 -- 2 // 4 -- 6 UnionElem(UFSets,1,6); UnionElem(UFSets,2,7); // debug(); return 0; }
?文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-631037.html
?
文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-631037.html
到了這里，關(guān)于王道408---數(shù)據(jù)結(jié)構(gòu)--用數(shù)組實(shí)現(xiàn)二叉樹--并查集及其優(yōu)化代碼的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
