第10週SHHデータ構造-【項目1-ツリー演算ライブラリ】

/*
Copyright (c)2015,              
All rights reserved.
    ：  1.cpp
      ：   
    ：2015 11 6 
     ：v1.0
    :              ，       ，     。
    ：  
    ：     
 */

 

btree.hヘッダファイルコード

//ヘッダファイル#define MaxSize 100 typedef char ElemType;typedef struct node{ElemType data;//データ要素struct node*lchild;//左子供struct node*rchild;//右子供}BTNode;void CreateBTNode(BTNode *&b,char *str);//str列から二叉鎖BTNode*FindNode(BTNode*b,ElemType x)を作成する.//dataドメインxのノードポインタBTNode*LchildNode(BTNode*p)を返す.//*pノードの左子ノードポインタBTNode*RchildNode(BTNode*p)を返す.//*pノードの右子ノードポインタint BTNodeDepth(BTNode*b);二叉木bの深さvoid DispBTNode(BTNode*b)を求めます;//二叉木void DestroyBTNode(BTNode*&b)を括弧表記で出力する.//ツリーの廃棄

btree.cppファイルコード

//   

#include <stdio.h>
#include <malloc.h>
#include "btree.h"

void CreateBTNode(BTNode *&b,char *str)     // str      
{
    BTNode *St[MaxSize],*p=NULL;
    int top=-1,k,j=0;
    char ch;
    b=NULL;             //           
    ch=str[j];
    while (ch!='\0')    //str       
    {
        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)                    //p         
                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)  //  data  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)   //  *p          
{
    return p->lchild;
}
BTNode *RchildNode(BTNode *p)   //  *p          
{
    return p->rchild;
}
int BTNodeDepth(BTNode *b)  //    b   
{
    int lchilddep,rchilddep;
    if (b==NULL)
        return(0);                          //      0
    else
    {
        lchilddep=BTNodeDepth(b->lchild);   //        lchilddep
        rchilddep=BTNodeDepth(b->rchild);   //        rchilddep
        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(")");
        }
    }
}
void DestroyBTNode(BTNode *&b)   //     
{
    if (b!=NULL)
    {
        DestroyBTNode(b->lchild);
        DestroyBTNode(b->rchild);
        free(b);
    }
}