数据结构之二叉树的实现
1、二叉树的基本运算
?? ??#define MaxSize 100
typedef char ElemType;typedef struct node{ ElemType data; struct node *lchild; struct node *rchild;}BTNode;void CreateBTNode(BTNode *&b,char *str){ BTNode *St[MaxSize],*p=NULL; int top=-1,k,j=0; char ch; b=NULL; ch=str[j]; while(ch!='\0'){ switch (ch) { case '(':top++,St[top]=p;k=1;break; case ')':top--;break; case ',': k=2;break; default:p=(BTNode *)malloc(sizeof(BTNode)); p->data=ch;p->lchild=p->rchild=NULL; if(b==NULL){ b=p; }else{ switch (k) { case 1:St[top]->lchild=p;break; case 2:St[top]->rchild=p;break; } } } j++; ch=str[j]; }}BTNode *FindNode(BTNode *b,ElemType x){ BTNode *p; if(b==NULL){ return NULL; } else if(b->data==x){ return b; }else{ p=FindNode(b->lchild, x); if(p!=NULL){ return p; }else{ return FindNode(b->rchild, x); } }}BTNode *LchildNode(BTNode *p){ return p->lchild;}BTNode *RchildNode(BTNode *p){ return p->rchild;}int BTNodeDepth(BTNode *b){ int lchilddep,rchilddep; if(b==NULL){ return 0; }else{ lchilddep=BTNodeDepth(b->lchild); rchilddep=BTNodeDepth(b->rchild); return lchilddep>rchilddep?lchilddep+1:rchilddep+1; }}void DispBTNode(BTNode *b){ if(b!=NULL){ printf("%c ",b->data); if(b->lchild!=NULL||b->rchild!=NULL){ printf("("); DispBTNode(b->lchild); if(b->rchild!=NULL){ printf(","); DispBTNode(b->rchild); } printf(")"); } } }int BTWidth(BTNode *b){ struct{ int lno; BTNode *p; }Qu[MaxSize]; int front,rear; int lnum,max,i,n; front=rear=0; if(b!=NULL){ rear++; Qu[rear].p=b; Qu[rear].lno=1; while(rear!=front){ front++; b=Qu[front].p; lnum=Qu[front].lno; if(b->lchild!=NULL){ rear++; Qu[rear].p=b->lchild; Qu[rear].lno=lnum+1; } if(b->rchild!=NULL){ rear++; Qu[rear].p=b->rchild; Qu[rear].lno=lnum+1; } } max=0;lnum=1;i=1; while(i<=rear){ n=0; while(i<=rear&&Qu[i].lno==lnum){ n++; i++; } lnum=Qu[i].lno; if(n>max){ max=n; } } return max; }else{ return 0; } }int Nodes(BTNode *b){ if(b==NULL){ return 0; }else if(b->lchild==NULL&&b->rchild==NULL){ return 1; }else{ return Nodes(b->lchild)+Nodes(b->rchild)+1; }}int LeafNodes(BTNode *b){ if(b==NULL){ return 0; }else if(b->lchild==NULL&&b->rchild==NULL){ return 1; }else{ return LeafNodes(b->lchild)+LeafNodes(b->rchild); }}?2、二叉树的遍历
?? ? ? 2.1递归遍历
?
void PreOrder(BTNode *b){ if(b!=NULL){ printf("%c",b->data); PreOrder(b->lchild); PreOrder(b->rchild); }}void InOrder(BTNode *b){ if(b!=NULL){ InOrder(b->lchild); printf("%c",b->data); InOrder(b->rchild); }}void PostOrder(BTNode *b){ if(b!=NULL){ PostOrder(b->lchild); PostOrder(b->rchild); printf("%c",b->data); }}?
?? 2.2非递归遍历
?
?
void ProOrder1(BTNode *b){ BTNode *p; struct { BTNode *pt; int tag; }St[MaxSize]; int top=-1; top++; St[top].pt=b; St[top].tag=1; while(top>-1){ if(St[top].tag==1){ p=St[top].pt; top--; if(p!=NULL){ top++; St[top].pt=p->rchild; St[top].tag=1; top++; St[top].pt=p->lchild; St[top].tag=1; top++; St[top].pt=p; St[top].tag=0; } } if(St[top].tag==0){ printf("%c",St[top].pt->data); top--; } }}void InOrder1(BTNode *b){ BTNode *p; struct { BTNode *pt; int tag; }St[MaxSize]; int top=-1; top++; St[top].pt=b; St[top].tag=1; while(top>-1){ if(St[top].tag==1){ p=St[top].pt; top--; if(p!=NULL){ top++; St[top].pt=p->rchild; St[top].tag=1; top++; St[top].pt=p; St[top].tag=0; top++; St[top].pt=p->lchild; St[top].tag=1; } } if(St[top].tag==0){ printf("%c",St[top].pt->data); top--; } }}void PostOrder1(BTNode *b){ BTNode *p; struct { BTNode *pt; int tag; }St[MaxSize]; int top=-1; top++; St[top].pt=b; St[top].tag=1; while(top>-1){ if(St[top].tag==1){ p=St[top].pt; top--; if(p!=NULL){ top++; St[top].pt=p; St[top].tag=0; top++; St[top].pt=p->rchild; St[top].tag=1; top++; St[top].pt=p->lchild; St[top].tag=1; } } if(St[top].tag==0){ printf("%c",St[top].pt->data); top--; } } }?3、从叶子节点到根结点的路径
??
?
void AllPath(BTNode *b){ struct snode { BTNode *node; int parent; }Qu[MaxSize]; int front,rear,p; front=rear=-1; rear++; Qu[rear].node=b; Qu[rear].parent=-1; while(front<rear){ front++; b=Qu[front].node; if(b->lchild==NULL&&b->rchild==NULL){ printf("%c到根结点的路径： ",b->data); p=front; while(Qu[p].parent!=-1){ printf(" %c",Qu[p].node->data); p=Qu[p].parent; } printf(" %c\n",Qu[p].node->data); } if(b->lchild!=NULL){ rear++; Qu[rear].node=b->lchild; Qu[rear].parent=front; } if(b->rchild!=NULL){ rear++; Qu[rear].node=b->rchild; Qu[rear].parent=front; } }}void AllPath1(BTNode *b,ElemType path[],int pathlen){ int i; if(b!=NULL){ if(b->lchild==NULL&&b->rchild==NULL){ printf(" %c到根接的路径： %c",b->data,b->data); for(i=pathlen-1;i>=0;i--){ printf(" %c",path[i]); } printf("\n"); }else{ path[pathlen]=b->data; pathlen++; AllPath1(b->lchild, path, pathlen); AllPath1(b->rchild, path, pathlen); pathlen--; } }}void LongPath(BTNode *b,ElemType path[],int pathlen,ElemType longpath[],int &longpathlen){ int i; if(b==NULL){ if(pathlen>longpathlen){ for (i=pathlen-1; i>=0; i--) { longpath[i]=path[i]; } longpathlen=pathlen; } }else{ path[pathlen]=b->data; pathlen++; LongPath(b->lchild, path, pathlen, longpath, longpathlen); LongPath(b->rchild, path, pathlen, longpath, longpathlen); pathlen--; } }void DispLeaf(BTNode *b){ if(b!=NULL){ if(b->lchild==NULL&&b->rchild==NULL){ printf("%c ",b->data); }else{ DispLeaf(b->lchild); DispLeaf(b->rchild); } } }?