各種基本算法實現小結（三）—— 樹與二叉樹

各種基本算法實現小結（三）—— 樹與二叉樹

各種基本算法實現小結（三）—— 樹與二叉樹

（均已測試通過）

===================================================================

二叉樹——先序

測試環境：VC 6.0 (C)

#include #include #include struct_node { chardata; struct_node*lchild; struct_node*rchild; }; typedefstruct_nodenode,*pnode; pnodecreate_tree() { pnodept; chardata; scanf("%c",&data); getchar(); if(data=='') pt=NULL; else { pt=(pnode)malloc(sizeof(node)); pt->data=data; pt->lchild=create_tree(); pt->rchild=create_tree(); } return(pt); } voidprint_pretree(pnodeps) { if(ps!=NULL) { printf("%3c",ps->data); print_pretree(ps->lchild); print_pretree(ps->rchild); } } voidmain() { pnodeps; ps=create_tree(); print_pretree(ps); printf("/n"); }

運行結果：

===========================================================

二叉樹——各種操作

測試環境：VC 6.0 (C)

#include #include struct_node { chardata; struct_node*lchild; struct_node*rchild; }; typedefstruct_nodenode,*pnode; intcount_l=0;/*countleaf*/ intcount_n=0;/*countnode*/ pnodecreate_tree() { pnodept; chardata; scanf("%c",&data); getchar(); if(data=='') pt=NULL; else { pt=(pnode)malloc(sizeof(node)); pt->data=data; pt->lchild=create_tree(); pt->rchild=create_tree(); } return(pt); } voidprint_pretree(pnodeps) { if(ps!=NULL) { printf("%3c",ps->data); print_pretree(ps->lchild); print_pretree(ps->rchild); } } voidprint_midtree(pnodeps) { if(ps!=NULL) { print_midtree(ps->lchild);   printf("%3c",ps->data); print_midtree(ps->rchild); } } voidprint_posttree(pnodeps) { if(ps!=NULL) { print_posttree(ps->lchild); print_posttree(ps->rchild); printf("%3c",ps->data); } } intcount_leaf(pnodeps) { if(ps!=NULL) { if(ps->lchild==NULL&&ps->rchild==NULL) count_l++; count_leaf(ps->lchild); count_leaf(ps->rchild); } returncount_l; } intcount_node(pnodeps) { if(ps!=NULL) { count_n++; count_node(ps->lchild); count_node(ps->rchild); } returncount_n; } intcount_depth(pnodeps) { intldep,rdep; if(ps==NULL) return0; else { ldep=count_depth(ps->lchild); rdep=count_depth(ps->rchild);   returnldep>rdep?(ldep+1):(rdep+1); } } voidmain() { pnodeps; ps=create_tree();   printf("preorder.../n"); print_pretree(ps); printf("/n"); printf("midorder.../n"); print_midtree(ps); printf("/n"); printf("postorder.../n"); print_posttree(ps); printf("/n"); printf("numberofleafis:%d/n",count_leaf(ps)); printf("numberofnodeis:%d/n",count_node(ps)); printf("maxofdepthis:%d/n",count_depth(ps)); }

運行結果：

===========================================================

二叉樹——先序、中序、後序的遞歸與非遞歸實現

測試環境：VS2008 (C)

#include"stdafx.h" #include #include #defineDataTypechar /**************************************/ /********樹的結構定義********/ /**************************************/ struct_tree { DataTypedata; struct_tree*lchild; struct_tree*rchild; }; typedefstruct_treetree,*ptree; /**************************************/ /********棧的結構定義********/ /**************************************/ struct_node { ptreept; struct_node*next; }; typedefstruct_nodenode,*pnode; struct_stack { intsize; pnodeptop; }; typedefstruct_stackstack,*pstack; /**************************************/ /********堆的結構定義********/ /**************************************/ struct_queue { pnodefront; pnoderear; }; typedefstruct_queuequeue,*pqueue; /**************************************/ /********棧的數據操作********/ /**************************************/ pstackinit_stack() { pnodepn=NULL; pstackps=NULL; pn=(pnode)malloc(sizeof(node)); ps=(pstack)malloc(sizeof(stack)); pn->pt=NULL; pn->next=NULL; ps->ptop=pn; returnps; } intempty_stack(pstackps) { if(ps->ptop->next==NULL) return1; else return0; } voidpush_stack(pstackps,ptreept)/*flagforposttree:0forlchild;1forrchild*/ { pnodepn=NULL; pn=(pnode)malloc(sizeof(node)); pn->pt=pt; pn->next=ps->ptop; ps->ptop=pn; } ptreepop_stack(pstackps) { ptreept=NULL; pnodepn=NULL; if(!empty_stack(ps)) { pn=ps->ptop; ps->ptop=ps->ptop->next; pt=pn->pt; free(pn); } returnpt; } ptreegettop_stack(pstackps) { if(!empty_stack(ps)) returnps->ptop->pt; } /**************************************/ /********堆的數據操作********/ /**************************************/ queueinit_queue() { pnodepn=NULL; queuequ; pn=(pnode)malloc(sizeof(node)); pn->pt=NULL; pn->next=NULL; qu.front=qu.rear=pn; returnqu; } intempty_queue(queuequ) { if(qu.front==qu.rear) return1; else return0; } voiden_queue(queuequ,ptreept) { pnodepn=NULL; pn=(pnode)malloc(sizeof(node)); pn->pt; pn->next=qu.rear->next; qu.rear=pn; } ptreede_queue(queuequ) { ptreept=NULL; pnodepn=NULL; if(!empty_queue(qu)) { pn=qu.front; qu.front=qu.front->next; pt=pn->pt; free(pn); } returnpt; } /**************************************/ /********堆的數據操作********/ /**************************************/ ptreeinit_tree() { ptreept=NULL; pt=(ptree)malloc(sizeof(tree)); pt->data='0'; pt->lchild=NULL; pt->rchild=NULL; returnpt; } ptreecreate_tree() { charch; ptreept=NULL;   scanf("%c",&ch); getchar(); if(ch=='') returnNULL; else { pt=(ptree)malloc(sizeof(tree)); pt->data=ch; pt->lchild=create_tree(); pt->rchild=create_tree(); } returnpt; } voidprint_pretree(ptreept) { if(pt!=NULL) { printf("%3c",pt->data); print_pretree(pt->lchild); print_pretree(pt->rchild); } } voidprint_pretree2(ptreept) { pstackps=NULL; ptreep=NULL; ps=init_stack(); p=pt; while(p!=NULL||!empty_stack(ps)) { while(p!=NULL) { printf("%3c",p->data); push_stack(ps,p); p=p->lchild; } if(!empty_stack(ps)) { p=pop_stack(ps); p=p->rchild; } } } voidprint_midtree(ptreept) { if(pt!=NULL) { print_midtree(pt->lchild); printf("%3c",pt->data); print_midtree(pt->rchild); } } voidprint_midtree2(ptreept) { pstackps=NULL; ptreep=NULL; ps=init_stack(); p=pt; while(p!=NULL||!empty_stack(ps)) { while(p!=NULL) { push_stack(ps,p); p=p->lchild; } if(!empty_stack(ps)) { p=pop_stack(ps); printf("%3c",p->data); p=p->rchild; } } } voidprint_posttree(ptreept) { if(pt!=NULL) { print_posttree(pt->lchild); print_posttree(pt->rchild); printf("%3c",pt->data); } } voidprint_posttree2(ptreept) { pstackps=NULL; ptreep=NULL; ptreep2=NULL; ptreelastvisit=NULL; ps=init_stack(); p=pt; while(p!=NULL||!empty_stack(ps)) { while(p!=NULL) { push_stack(ps,p); p=p->lchild; } p2=gettop_stack(ps);/*top:rchild==nullorsub_root*/ if(p2->rchild==NULL||p2->rchild==lastvisit) { printf("%3c",p2->data); lastvisit=pop_stack(ps);/*pop*/ } else p=p2->rchild; } } int_tmain(intargc,_TCHAR*argv[]) { ptreept=NULL; /*pt=init_tree();*/   printf("Createrecursiontree.../n"); pt=create_tree(); /************recursion************/ printf("/n/nrecursion..."); printf("/npretree.../n"); print_pretree(pt); printf("/nmidtree.../n"); print_midtree(pt); printf("/nposttree.../n"); print_posttree(pt); /************stack************/ printf("/n/nstack,nonrecursion..."); printf("/npretree.../n"); print_pretree2(pt); printf("/nmidtree.../n"); print_midtree2(pt); printf("/nposttree.../n"); print_posttree2(pt); printf("/n"); return0; }

 

運行結果：

===========================================================

二叉樹——學習交流與修正改進

在網上看到了好多人轉載這段代碼，我也復制、粘貼下來學習

但在VC6.0編譯器上運行並未通過，於是調試修正了幾個小bug

測試運行通過後的代碼粘貼如下，希望對大家學習有所幫助，謝謝！

本算法源碼引用網址：http://www.ccrun.com/article.asp?i=292&d=y6y12h （二叉樹實現源代碼）

測試環境：VC 6.0 (C)

#include #include #include #defineOK1 #defineERROR0 #defineTRUE1 #defineFALSE0 #defineOVERFLOW-2 typedefintstatus; typedefstructBiNode { charData; structBiNode*lChild; structBiNode*rChild; }BiNode,*pBiNode; statusCreateTree(BiNode**pTree); statusPreOrderTraval(BiNode*pTree); statusInOrderTraval(BiNode*pTree); statusPostOrderTraval(BiNode*pTree); statusVisit(charData); statusShowLeaves(BiNode*pTree); statusDelTree(BiNode*pTree); statusDisplay(BiNode*pTree,intLevel); statusClear(BiNode*pTree); BiNode*pRoot=NULL; voidmain() { CreateTree(&pRoot); printf("/nPreOrder:"); PreOrderTraval(pRoot); printf("/n"); printf("/nInOrder:"); InOrderTraval(pRoot); printf("/n"); printf("/nPostOrder:"); PostOrderTraval(pRoot); printf("/n"); printf("/nShowLeaves:"); ShowLeaves(pRoot); printf("/n-----------------------/n"); printf("/n"); Display(pRoot,0); printf("/n"); printf("/nDeletingTree:/n"); DelTree(pRoot); printf("BiTreeDeleted."); } statusCreateTree(BiNode**pTree) { charch; scanf("%c",&ch); getchar();   if(ch=='')/*NOTE:enterspace,example:[abcde]*/ { (*pTree)=NULL; } else { if(!((*pTree)=(BiNode*)malloc(sizeof(BiNode)))) { exit(OVERFLOW); } (*pTree)->Data=ch; CreateTree(&((*pTree)->lChild)); CreateTree(&((*pTree)->rChild)); } returnOK; } statusPreOrderTraval(BiNode*pTree) { if(pTree) { if(Visit(pTree->Data)) { if(PreOrderTraval(pTree->lChild)) { if(PreOrderTraval(pTree->rChild)) { returnOK; } } } returnERROR; } else { returnOK; } } statusInOrderTraval(BiNode*pTree) { if(pTree) { if(InOrderTraval(pTree->lChild)) { if(Visit(pTree->Data)) { if(InOrderTraval(pTree->rChild)) { returnOK; } } returnERROR; } returnERROR; } else returnOK; } statusPostOrderTraval(BiNode*pTree) { if(pTree) { if(PostOrderTraval(pTree->lChild)) { if(PostOrderTraval(pTree->rChild)) { if(Visit(pTree->Data)) { returnOK; } returnERROR; } } returnERROR; } else { returnOK; } } statusVisit(charData) { printf("%c",Data); returnOK; } statusDisplay(BiNode*pTree,intLevel) { inti; if(pTree==NULL) returnFALSE; Display(pTree->lChild,Level+1); for(i=0;i 

運行結果：

===========================================================

上述代碼改進後，邏輯更清晰，並添加了計算二叉樹層次的函數 ShowDepth(BiNode* pTree)

具體代碼如下：

#include #include #include #defineOK1 #defineERROR0 #defineTRUE1 #defineFALSE0 #defineOVERFLOW-2 typedefintstatus; typedefstructBiNode { charData; structBiNode*lChild; structBiNode*rChild; }BiNode,*pBiNode; statusCreateTree(BiNode**pTree); statusPreOrderTraval(BiNode*pTree); statusInOrderTraval(BiNode*pTree); statusPostOrderTraval(BiNode*pTree); statusVisit(charData); statusShowLeaves(BiNode*pTree); statusShowDepth(BiNode*pTree); statusDelTree(BiNode*pTree); statusDisplay(BiNode*pTree,intLevel); statusClear(BiNode*pTree); BiNode*pRoot=NULL; voidmain() { CreateTree(&pRoot); printf("/nPreOrder:"); PreOrderTraval(pRoot); printf("/n"); printf("/nInOrder:"); InOrderTraval(pRoot); printf("/n"); printf("/nPostOrder:"); PostOrderTraval(pRoot); printf("/n"); printf("/nShowLeaves:"); ShowLeaves(pRoot); printf("/nShowDepth:%d/n",ShowDepth(pRoot)); printf("/n------------------/n"); printf("/n"); Display(pRoot,0); printf("/n"); printf("/nDeletingTree:/n"); DelTree(pRoot); printf("BiTreeDeleted."); } statusCreateTree(BiNode**pTree) { charch; scanf("%c",&ch); getchar();   if(ch=='')/*NOTE:enterspace,example:[abcde]*/ (*pTree)=NULL; else { if(!((*pTree)=(BiNode*)malloc(sizeof(BiNode)))) exit(OVERFLOW); (*pTree)->Data=ch; CreateTree(&((*pTree)->lChild)); CreateTree(&((*pTree)->rChild)); } returnOK; } statusPreOrderTraval(BiNode*pTree) { if(pTree) { Visit(pTree->Data); PreOrderTraval(pTree->lChild); PreOrderTraval(pTree->rChild); } returnOK; } statusInOrderTraval(BiNode*pTree) { if(pTree) { InOrderTraval(pTree->lChild); Visit(pTree->Data); InOrderTraval(pTree->rChild); }   returnOK; } statusPostOrderTraval(BiNode*pTree) { if(pTree) { PostOrderTraval(pTree->lChild); PostOrderTraval(pTree->rChild); Visit(pTree->Data); }   returnOK; } statusVisit(charData) { printf("%c",Data); returnOK; } statusDisplay(BiNode*pTree,intLevel) { inti; if(pTree==NULL) returnFALSE; Display(pTree->lChild,Level+1); for(i=0;i運行結果：

===========================================================