두 갈래 나무의 정의 및 기본 조작

두 갈래 나무의 정의 및 기본 조작

두 갈래 나무는 또 다른 나무 구조로 그 특징은 매 결점마다 두 그루의 나무만 있고 두 갈래 나무의 나무는 좌우의 구분이 있으며 그 다음은 임의로 전도할 수 없다는 것이다.
1、InitBiTree(&T); 작업 결과: 구조 빈 두 갈래 나무

void InitBiTree(BiTree &T)
 { 
   T=NULL;
 }

2. DestroyBiTree(&T) 초기 조건: 두 갈래 트리 T 작업 결과: 두 갈래 트리 T 제거

void destroyBiTree(BiTree &T)  
{  
    if(T){  
        destroyBiTree(T->lchild);  
        destroyBiTree(T->rchild);  
        delete T;  
        T = NULL;  
    }  
}  

3、CreateBiTree(&T,definition); 초기 조건:definition에서 두 갈래 트리 T의 정의 작업 결과:definition에 따라 두 갈래 트리 T 구성

void createBiTree(BiTree &T)  
{  
    char data;  
    data = getchar();  
    if(data == '#')  
    {  
        T = NULL;  
    }  
    else  
    {  
        T = new BiTreeNode;  
        T->data = data;  
        createBiTree(T->lchild);  
        createBiTree(T->rchild);  
    }  
}  

4. ClearBiTree(&T) 초기 조건: 두 갈래 트리 T 작업 결과: 두 갈래 트리 T를 빈 트리로 만들기

void ClearTree(Tree *T)  
{  
    if (!*T)  
    {  
        return;  
    }  

    ClearTree(&(*T)->left);  
    ClearTree(&(*T)->right);  
    free(*T);  
    *T = NULL;  
}  

5、BiTreeEmpty(T); 초기 조건: 두 갈래 트리 T에 작업 결과가 존재합니다. 만약 T가 빈 두 갈래 트리라면 TRUE로 돌아가고 그렇지 않으면 FALSE로 돌아갑니다.

Status BiTreeEmpty(BiTree T)
{ 
    if(T)
    return FALSE;
    else
    return TRUE;
}

6. BiTreeDepth(T) 초기 조건: 두 갈래 트리 T 작업 결과: T 깊이를 되돌려줍니다.

int BiTreeDepth(BiTNode *T)  
{  
    int Depth = 0;  
    if (T != NULL){  
        int leftDepth = TreeDepth(T->lChild);  
        int rightDepth = TreeDepth(T->rChild);  
        Depth = leftDepth >= righDepth?leftDepth+1:rightDepth+1;  
    }  

    return Depth;  
}  

7. Root(T) 초기 조건: 두 갈래 트리 T 작업 결과: T의 루트 반환

TElemType Root(BiTree T)
{
    return T->data;
}

8. Value(T, e) 초기 조건: 두 갈래 트리 T가 존재하고 e는 T의 어떤 결점 작업 결과: e의 값을 되돌려줍니다.

TElemType Value(T,  node) 
{
    return node->data;
}

9. Assign(T,&e,value) 초기 조건: 두 갈래 트리 T가 존재하고 e는 T의 어떤 결점 조작 결과: 결점 e부치value

Status Assign(Position *node,TElemType value) { 
    (*node)->data = value;
    return OK;
}

10. Parent(T, e) 초기 조건: 두 갈래 트리 T가 존재하고 e는 T의 어떤 결점 작업 결과입니다. 만약에 e가 T의 비뿌리 결점이라면 양친을 되돌려주고 그렇지 않으면 "공"으로 되돌려줍니다.

BiTree Parent(BiTree T,BiTNode* e)
{
    if(T){
        if(T->data==e->data)
            return NULL;
    }
    if(T->lchild!=NULL && T->lchild->data==e->data||T->rchild!=NULL && T->rchild->data==e->data) 
        return T;
    else
    {
        BiTNode* tempP=NULL;
            if(tempP=Parent(T->lchild,e))
                return tempP;
            if(tempP=Parent(T->rchild,e))
                return tempP;
    }
    return NULL;
}

11、LeftChild(T,e); 초기 조건: 두 갈래 나무 T가 존재하고 e는 T의 어떤 결점 작업 결과입니다. e의 왼쪽 아이로 돌아갑니다.만약 e가 왼쪽 아이가 없다면, "빈"으로 돌아갑니다

TElemType LeftChild(BiTree T,TElemType elem) {
    Position p;
    p = NodePoint(T,elem);
    if(p->lchild)
        return p->lchild->data;
    return NULL;
}

12. RightChild(T, e) 초기 조건: 두 갈래 나무 T가 존재하고 e는 T의 어떤 노드 조작 결과: e의 오른쪽 아이로 돌아간다.만약 e가 오른쪽 아이가 없다면, "빈"으로 돌아갑니다

TElemType RightChild(BiTree T,TElemType elem) {
    Position p;

    p = NodePoint(T,elem);

    if(p->rchild)
        return p->rchild->data;

    return NULL;
}

13. LeftSibling(T, e) 초기 조건: 두 갈래 트리 T가 존재하고 e는 T의 어떤 결점 조작 결과: e의 왼쪽 형제를 되돌려줍니다.만약 e가 T의 왼쪽 아이이거나 왼쪽 형제가 없다면'공'으로 돌아간다.

TElemType LeftSibling(BiTree T,TElemType e)  
{ 
    TElemType a;  
    BiTree p;  
    if(T)
    {  
        a=Parent(T,e); 
        p=Point(T,a); 
        if(p->lchild&&p->rchild&&p->rchild->data==e) 
            return p->lchild->data; 
    }  
    return NULL; 
}  

14. RightSibling(T, e) 초기 조건: 두 갈래 트리 T가 존재하고 e는 T의 어떤 결점 조작 결과: e의 오른쪽 형제로 되돌아간다.만약 e가 T의 오른쪽 아이이거나 오른쪽 형제가 없다면'공'으로 돌아간다.

TElemType LeftSibling(BiTree T,TElemType e)  
{ 
    TElemType a;  
    BiTree p;  
    if(T)
    {  
        a=Parent(T,e); 
        p=Point(T,a); 
        if(p->rchild&&p->lchild&&p->lchild->data==e) 
            return p->rchild->data; 
    }  
    return NULL; 
}  

15. InsertChild(T, p, LR, c)의 초기 조건: 두 갈래 트리 T가 존재하고 p는 T의 어떤 결점을 가리키며 LR은 0 또는 1이고 비공 두 갈래 트리 c는 T와 교차하지 않으며 오른쪽 하위 트리는 비어 있다.작업 결과: LR이 0 또는 1이고 c가 T에서 p가 가리키는 결점의 왼쪽 또는 오른쪽 트리에 삽입됩니다.p가 가리키는 결점의 원래 왼쪽 나무나 오른쪽 나무는 c의 오른쪽 나무가 된다

Status InsertChild(Position p,int LR,BiTree c) {
    if(p) {
        if(LR == 0) {
            c->rchild = p->lchild;
            p->lchild = c;
        }
        else if(LR == 1) {
            c->rchild = p->rchild;
            p->rchild = c;
        }

        return OK;
    }
    else
        return ERROR;
}

16. DeleteChild(T,p,LR) 초기 조건: 두 갈래 트리 T가 존재하고 p는 T의 어떤 결점을 가리키며 LR은 0 또는 1이다.작업 결과: LR이 0 또는 1인 경우 T에서 p가 가리키는 결점의 왼쪽 또는 오른쪽 하위 트리를 삭제합니다.

Status DeleteChild(Position p,int LR) {
    if(LR == 0) {
        if(p->lchild) {
            DestoryBiTree(&p->lchild);
            return OK;
        }
    }
    else if(LR == 1) {
        if(p->rchild) {
            DestoryBiTree(&p->rchild);
            return OK;
        }
    }


    return ERROR;

}

17、PreOrderTraverse(T Visit( ) ); 초기 조건: 두 갈래 트리 T가 존재합니다.Visit는 결점 작업에 대한 응용 함수입니다.작업 결과: 모든 결점에 대한 함수visit를 한 번에 한 번만 호출합니다.visit () 가 실패하면 작업이 실패합니다

Status PostOrderTraverse(BiTree T,Status (*visit)(TElemType elem)) {
    if(T) {
        if(PostOrderTraverse(T->lchild,visit))
            if(PostOrderTraverse(T->rchild,visit))
                if(visit(T->data))
                    return OK;
        return ERROR;
    }

    return OK;
}

18、InOrderTraverse(T, Visit( ) ); 초기 조건: 두 갈래 트리 T가 존재하고 Visit는 결점 작업에 대한 응용 함수입니다.작업 결과: 모든 결점에 대한 함수visit를 한 번, 한 번만 호출합니다.visit () 가 실패하면 작업이 실패합니다

Status InOrderTraverse(BiTree T,Status (*visit)(TElemType elem)) {
    if(T) {
        if(InOrderTraverse(T->lchild,visit))
            if(visit(T->data))
                if(InOrderTraverse(T->rchild,visit))
                    return OK;
        return ERROR;
    }

    return OK;
}

19、PostOrderTraverse(T,Visit()); 초기 조건: 두 갈래 트리 T가 존재하고 Visit는 결점 작업에 대한 응용 함수입니다.작업 결과: 모든 결점에 대한 함수visit를 한 번 호출하고 한 번만 호출합니다.visit () 가 실패하면 작업이 실패합니다

Status PostOrderTraverse(BiTree T,Status (*visit)(TElemType elem)) {
    if(T) {
        if(PostOrderTraverse(T->lchild,visit))
            if(PostOrderTraverse(T->rchild,visit))
                if(visit(T->data))
                    return OK;
        return ERROR;
    }

    return OK;
}

20、LevelOrderTraverse(T, Visit( ) ); 초기 조건: 두 갈래 트리 T가 존재하고 Visit는 결점 작업에 대한 응용 함수입니다.작업 결과: 각 결점에 대한 함수visit를 한 번에 한 번만 호출합니다.visit () 가 실패하면 작업이 실패합니다

Status LevelOrderTraverse(BiTree T,Status (*visit) (TElemType elem)) {
    if(T == NULL)
        return ERROR;

    LinkQueue TreeQueue;
    ElemType p;

    InitQueue(&TreeQueue);
    p = T;

    EnQueue(&TreeQueue,p);

    while(!QueueEmpty(TreeQueue)) {
        DeQueue(&TreeQueue,&p);

        if(p) {
            visit(p->data);
            EnQueue(&TreeQueue,p->lchild);
            EnQueue(&TreeQueue,p->rchild);
        }
    }

    return OK;
}