Chap 4: Trees⚓︎

// from my work of project 2
Tree ExpTree(Queue q)
{
    Tree ans;   // The final expression tree
    Stack s;    // The stack for tree construction, containing the nodes or the trees
    PtrToNode node, op1, op2, new;  // node for all element in the queue; op1 and op2 are operands;and new is a new tree
    PtrToQueue cur = q->front->next;  // Starting from the second element, for the queue has a dummy header

    s = CreateStack();  // Initialization
    while (cur != NULL)  // Traversing all the element in the queue
    {
        node = CreateNode(cur->var);  // Creating node for every element in the queue
        if(isalnum(cur->var[0]) || cur->var[0] == '-' && isalnum(cur->var[1]))  // If it's an operand, push it into the stack
        {
            Push1(node, s);
            // printf("%s\n", str);
        }
        else  // If it's a operator,
        {

            op2 = Top1(s);  // Obtaining the top two operands from the stack
            Pop(s);
            op1 = Top1(s);
            Pop(s);
            new = CreateTree(node, op1, op2);  // Creating an expression (sub)tree
            Push1(new, s);
        }
        cur = cur->next;
    }
    ans = Top1(s); // The remaining tree in the stack is the answer

    return ans;

}

// 声明部分
#ifndef _Tree_H

struct TreeNode;
typedef struct TreeNode * Position;
typedef struct TreeNode * SearchTree;

SearchTree MakeEmpty(SearchTree T);
Position Find(ElementType X, SearchTree T);
Position FindMin(SearchTree T);
Position FindMax(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;
}

// 初始化处理（用到后序遍历），时间复杂度 O(logN)
SearchTree MakeEmpty(SearchTree T)
{
    if (T != NULL)
    {
        MakeEmpty(T->Left);
        MakeEmpty(T->Right);
        free(T);
    }
    return NULL;
}

Position Find(ElementType X, SearchTree T)
{
    if (T == NULL)
        return NULL; // not found in an empty tree
    if (X < T->Element)  // if smaller than root
        return Find(X, T->Left);  // search left subtree
    else if (X > T->Element)  // if larger than root
        return Find(X, T->Right);  // search right subtree
    else  // if X == root
        return T;  // found
}

Position Iter_Find(ElementType X, SearchTree T)
{
    while (T)
    {
        if (X == T->Element)
            return T;  // found
        if (X < T->Element)
            T = T->Left;  // move down along left path
        else
            T = T->Right;  // move down along right path
    } // end while-loop
    return NULL;  // not found
}

Position FindMin(SearchTree T)
{
    if (T == NULL)
        return NULL;  // not found in an empty tree
    else if (T->Left == NULL)  // found left most
        return T;
    else
        return FindMin(T->Left); // keep moving to left
}

Position FindMax(SearchTree T)
{
    if (T != NULL)
        while (T->Right != NULL)
            T = T->Right;  // keep moving to find right most
    return T;  // return NULL or the right most
}

SearchTree Insert(ElementType X, SearchTree T)
{
    if (T == NULL)  // Create and return a one-node tree
    {
        T = (SearchTree)malloc(sizeof(struct TreeNode));
        if (T == NULL)
            FatalError("Out of space!!!");
        else
        {
            T->Element = X;
            T->Left = T->Right = NULL;
        }
    }  // End create a one-node tree
    else
    {
        if (X < T->Element)
            T->Left = Insert(X, T->Left);
        else if (X > T->Element)
            T->Right = Insert(X, T->Right);
        // Else X is in the tree already, we'll do nothing
    }
    return T; // Don't forget this line!!
}

// 这里删除度为 2 的节点时采用拿右子树最小节点替换的方法
SearchTree Delete(ElementType X, SearchTree T)
{
    Position TmpCell;
    if (T == NULL)
        Error("Element not found");
    else
    {
        if (X < T->ELement)  // Go left
            T->Left = Delete(X, T->Left);
        else if (X > T->Element)  // Go right
            T->Right = Delete(X, T->Right);
        else  // Found element to be deleted
        {
            if (T->Left && T->Right)  // Two children
            {  // Replace with smallest in right subtree
                TmpCell = FindMin(T->Right);
                T->Element = TmpCell->Element;
                T->Right = Delete(T->Element, T->Right);
            }  // End if 
            else  // One or zero child
            {
                TmpCell = T;
                if (T->Left == NULL)  // Also handles 0 child
                    T = T->Right;
                else if (T->Right == NULL)
                    T = T->Left;
                free(TmpCell);  // End else 1 or 0 child
            }
        }
    } 
    return T;
}