本文总结二叉树的各种操作与C语言的实现
头文件
#include <stdio.h> #include <stdlib.h> #include <time.h> #include <queue> using namespace std ;
数据结构
typedef struct Node{ char data ; struct Node * rchild ; struct Node * lchild ; }Node,*pNode;
随机创建二叉树的数据
void CreateRandChar(char *const a,int len){ /*随机生成一个长度为len的字符串*/ int i; srand((unsigned int)time(NULL)); for(i=0;len--;) a[i++]='A'+(int)(1.0*rand()/(RAND_MAX)*26); a[i]=0; return ; }
创建二叉树
#define LCHILD(i) (2*i+1) #define RCHILD(i) (2*i+2) pNode CreateTree(char * a,int len){ /*创建一棵二叉树*/ int i = 0,r,l; pNode p; p = (Node*)malloc(len*sizeof(Node)); if(!p) return NULL ; for (i=0;i<len;i++){ p[i].data = a[i]; r = RCHILD(i); l = LCHILD(i); if(l<len) p[i].lchild = &p[l] ; else p[i].lchild = NULL ; if(r<len) p[i].rchild = &p[r] ; else p[i].rchild = NULL; } return p ; }
二叉树访问函数
typedef void (*pVisit)(void *arg) ; void VisitFun (void *arg)/*访问函数*/{ pNode p = (pNode)arg ; printf("%c,",p->data); }
三种递归遍历(前、中、后序)算法
void PreOrderTraverse(pNode head ,pVisit fun){/*递归先序遍历*/ if(!head) return ; fun((void*)head); if(head->lchild) PreOrderTraverse(head->lchild,fun); if(head->rchild) PreOrderTraverse(head->rchild,fun); } void InOrderTraverse(pNode head ,pVisit fun){/*递归中序遍历*/ if(!head) return ; if(head->lchild) PreOrderTraverse(head->lchild,fun); fun((void*)head); if(head->rchild) PreOrderTraverse(head->rchild,fun); } void AfterOrderTraverse(pNode head ,pVisit fun){ /*递归中序遍历*/ if(!head) return ; if(head->lchild) PreOrderTraverse(head->lchild,fun); if(head->rchild) PreOrderTraverse(head->rchild,fun); fun((void*)head); }
遍历二叉树的某一层
int OneLevelTraverse(pNode head,int level ,pVisit fun) {/*递归遍历某一层*/ if(!head || level <=0) return 0; if( 1==level){ fun(head); return 1 ; } return OneLevelTraverse(head->lchild,level-1,fun ) + OneLevelTraverse(head->rchild,level-1,fun) ; }
获得二叉树的深度
int GetDepth(pNode head){ int rd,ld; if(!head) return 0; rd = GetDepth(head->rchild) ; ld = GetDepth(head->lchild) ; return rd>ld?(rd+1):(ld+1) ; }
层次遍历二叉树
/*方法一:递归法层次遍历二叉树*/ void LevelTraverse1(pNode head, pVisit fun ){ int i,depth ; depth = GetDepth(head) ; for(i=1;i<=depth;i++) OneLevelTraverse(head,i,fun) ; }
/*方法二:递归法层次遍历二叉树*/ void LevelTraverse2(pNode head, pVisit fun ){ int i = 0; for(i=1;;i++)//当访问到最后一层的下一层的时候,会返回0,退遍历结束 if(!OneLevelTraverse(head,i,fun)) break; }
/*方法三:非递归方式(借用队列)层次遍历二叉树*/ void LevelTraverse3(pNode head, pVisit fun ){ queue<pNode > que ; pNode p ; que.push(head) ; while(!que.empty()){ p = que.front(); fun(p); if(p->lchild) que.push(p->lchild); if(p->rchild) que.push(p->rchild); que.pop(); } }
/*如果是逆序层次遍历的话,则可以用栈的功能,先全部进栈,则出栈即可*/
main函数测试
int main(int argc,char** argv){ char a[255]; int len ; pNode head ; len = 10; CreateRandChar(a,len); printf("%s\n",a); head= CreateTree(a,len); PreOrderTraverse(head,&VisitFun); printf("\nlevel traverse:"); LevelTraverse3(head,&VisitFun) ; return 0; }