학습 노트 (5) - 트리 ADT

하나, 두 갈래 나무
1. 정의
두 갈래 나무는 한 그루의 나무로 그 중 노드마다 두 아들보다 많을 수 없다.
2. 실현

typedef struct TreeNode *PtrToNode;

typedef PtrToNode Tree;

typedef char ElementType;





struct TreeNode

{

    ElementType Element;

    Tree Left;

    Tree Right;

};

3. 후차 표현식을 통해 표현식 트리를 구성한다

void bianli(Tree t)

{

    if (t)

    {

        bianli(t->Left);

        cout << t->Element << " ";

        bianli(t->Right);

    }

}



int main()

{



    char c;

    stack<Tree> treeStack;

    

    while (1)

    {

        cout << "Please enter a suffix expression!(the last must is ';')" << endl;

        cin >> c;

        if (c == ';')

        {

            break;

        }

        else

        {

            if (c == '+' || c == '-' || c == '*' || c == '/')

            {

                auto t2 = treeStack.top();

                treeStack.pop();

                auto t1 = treeStack.top();

                treeStack.pop();



                PtrToNode temp2 = new(struct TreeNode);



                temp2->Element = c;

                temp2->Left = t1;

                temp2->Right = t2;



                treeStack.push(temp2);



            }

            else

            {

                PtrToNode temp;

                temp = new(struct TreeNode);

                temp->Element = c;

                temp->Left = temp->Right = nullptr;

                treeStack.push(temp);

            }

        }

    }



    auto t = treeStack.top();

    bianli(t);

    

    return 0;

}

2. 트리 찾기 ADT
1. 정의
트리의 각 노드 X의 경우 왼쪽 트리의 모든 키워드 값은 X의 키워드 값보다 작고 오른쪽 트리의 모든 키워드 값은 X의 키워드 값보다 큽니다.
2. 실현

#ifndef _Tree_H

#define _Tree_H



// ~

struct TreeNode;



typedef struct TreeNode *Position;

typedef struct TreeNode *SearchTree;



typedef int ElementType;// 

// 

SearchTree MakeEmpty(SearchTree T);

Position Find(SearchTree, ElementType X);

Position FindMin(SearchTree T);

Position FindMxa(SearchTree T);

SearchTree Insert(ElementType X, SearchTree T);

SearchTree Delete(ElementType X, SearchTree T);

ElementType Retrieve(Position P);





#endif // !_Tree_H

struct TreeNode           // 

{

    ElementType Element;

    SearchTree Left;

    SearchTree Right;



};

3. 관련 방법의 실현
(1) 비워~
비우기 위해서는 뒷차례를 반복하는 방법을 사용해야 한다. 뒷차례를 옮겨야만 모든 나무를 다 정리할 수 있기 때문이다.

SearchTree MakeEmpty(SearchTree T)

{

    if (T)

    {

        MakeEmpty(T->Left);

        MakeEmpty(T->Right);

        delete(T);

    }

    return nullptr;

}

(2) 찾기
결점보다 작은 것은 좌자나무를 찾으러 가고, 큰 것은 우자나무를 찾으러 간다

Position Find(SearchTree T, ElementType X)

{

    if (T)

    {

        if (T->Element == X)

        {

            return T;

        }

        else if (T->Element>X)

        {

            return Find(T->Left, X);

        }

        else

        {

            return Find(T->Right, X);

        }

    }

    

        return nullptr;



}

(3) 가장 작은 것을 찾다
한 가지 방법은 마지막 결점까지 끊임없이 왼쪽 나무를 찾아가는 것이다.

Position FindMin(SearchTree T)

{

    if (T)

    {

        if (T->Left == nullptr)

        {

            return T;

        }

        else

        {

            return FindMin(T);

        }

    }

    else

    {

        return nullptr;

    }

}

(3) 가장 큰 것을 찾다
물론 이런 간단한 귀속은 for순환 하나로 해결할 수 있다.

Position FindMax(SearchTree T)

{

    if (T != nullptr)

    {

        while (T->Right != nullptr)

        {

            T = T->Right;

        }

    }

    return T;

}

(4) 삽입
//SearchTree Insert(ElementType X, SearchTree T) {if (T==nullptr)//빈 트리를 삽입하면 {T = new (struct TreeNode), if (T=nullptr) {cout << Out of Space!>endl;        }        else        {            T->Element = X;            T->Left = T->Right = nullptr;        }    }    else if (T->Element < X)     {        T->Left = Insert(X, T->Left);    }    else if (T->Element>X)                 {        T->Right = Insert(X, T->Right);} else//와 같은 말은 이미 있다는 것을 나타낸다 {cout << "It has existed!"    return T;//다시 돌아와주세요
(5) 삭제
//SearchTree Delete 삭제(ElementType X, SearchTree T) {if (T==nullptr)//빈 트리를 찾으면 멈추기 {cout << "Element not found!"Element)    {        T->Left = Delete(X, T->Left);    }    else if (X>T->Element)    {        T->Right = Delete(X, T->Right);} else if (T->Left & T->Right)//트리가 모두 존재할 때 오른쪽 트리 중 가장 작은 것으로 대체합니다.    {        auto t = FindMin(T->Right);        T->Element = t->Element;        T->Right = Delete(T->Element, T->Right);}else//하나의 하위 트리만 있거나 없으면 간단합니다. 직접 대체하거나 delete {auto t = T;if (T->Left = nullptr) {T = T->Right;        }        else if (T->Right == nullptr)        {            T = T->Left;        }        else        {            delete(t);        }    }   return T;}