数据结构之二叉树的实现

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);
        }
    }
    
}