데이터 구조이 진 트 리 의 기본 동작

이 진 트 리 의 정의

typedef int BTDataType;
typedef struct BTNode
{
    struct BTNode* _left;
    struct BTNode* _right;
    BTDataType _data;
}BTNode;

이 진 트 리 의 인터페이스 구현

BTNode* BuyBTNode(BTDataType x)   //    
{
    BTNode * cur = (BTNode*)malloc(sizeof(BTNode));
    assert(cur);
    cur->_data = x;
    cur->_left = NULL;
    cur->_right = NULL;

    return cur;
}

//       
BTNode* CreateBTree(BTDataType* a, size_t* pIndex, BTDataType invalid)   //a   ，invalid     ，pIndex    ，        
{
    assert(a);

    BTNode* tree = NULL;
    if (a[*pIndex] == invalid)
    {
        tree = NULL;
    }
    else
    {
        tree = BuyBTNode(a[*pIndex]);

        (*pIndex)++;
        tree->_left = CreateBTree(a, pIndex, invalid);   //   

        (*pIndex)++;
        tree->_right = CreateBTree(a, pIndex, invalid);   //   
    }
    return tree;
}

void BTreePrevOrder(BTNode* root)  //    
{
    if (root == NULL)
    {
        return;
    }
    printf("%d ", root->_data);

    BTreePrevOrder(root->_left);
    BTreePrevOrder(root->_right);
}

void BTreeInOrder(BTNode* root)    //    
{
    if (root == NULL)
    {
        return;
    }

    BTreeInOrder(root->_left);
    printf("%d ", root->_data);
    BTreeInOrder(root->_right);

}
void BTreePostOrder(BTNode* root)   //    
{
    if (root==NULL)
    {
        return;
    }

    BTreePostOrder(root->_left);
    BTreePostOrder(root->_right);
    printf("%d ", root->_data);
}

size_t BTreeSize(BTNode* root)     //     
{
    if (root == NULL)
        return 0;
    return 1 + BTreeSize(root->_left) + BTreeSize(root->_right);   //  +       +       
}

size_t BTreeLeafSize(BTNode* root)         //   
{
    if (root == NULL)
    {
        return 0;
    }
    if (root->_left == NULL&&root->_right == NULL)
    {
        return 1;
    }
    return BTreeLeafSize(root->_left) + BTreeLeafSize(root->_right);
}

size_t BTreeKLevelSize(BTNode* root, size_t k)     // K    
{
    if (root == NULL)
    {
        return 0;
    }
    else if (k == 0)
    {
        return 1;
    }
    else
        return BTreeKLevelSize(root->_left, k - 1) + BTreeKLevelSize(root->_right, k - 1);
}

size_t BTreeDepth(BTNode* root)     //    
{
    size_t ldepth;
    size_t rdepth;
    if (root == NULL)
        return 0;
    ldepth = BTreeDepth(root->_left);
    rdepth = BTreeDepth(root->_right);
    return  ldepth > rdepth ? (ldepth + 1) : (rdepth + 1);
}

BTNode* BTreeFind(BTNode* root, BTDataType x)    //  
{
    BTNode* lnode = NULL, *rnode = NULL;
    if (root == NULL)
        return NULL;
    if (root->_data == x)
        return root;

    lnode = BTreeFind(root->_left, x);
    if (lnode != NULL)
        return lnode;

    rnode = BTreeFind(root->_right, x);
    if (rnode != NULL)
        return rnode;

    return NULL;
}

void BTreeLevelOrder(BTNode* root)    //     
{
    Queue queue;
    QueueInit(&queue);
    BTNode* cur = root;

    if (cur != NULL)
    {
        QueuePush(&queue,cur);
    }
    while (QueueEmpty(&queue))
    {
        cur = QueueFront(&queue);
        printf("%d ", cur->_data);
        QueuePop(&queue);

        if (cur->_left != NULL)
        {
            QueuePush(&queue, cur->_left);
        }
        if (cur->_right != NULL)
        {
            QueuePush(&queue, cur->_right);
        }
    }
    printf("
");
}

int IsCompleteBTree(BTNode* root)  //              
{
    Queue q;
    QueueInit(&q);
    if (root != NULL)
        QueuePush(&q, root);

    while (QueueEmpty(&q) != 0)
    {
        BTNode* front = QueueFront(&q);
        QueuePop(&q);

        if (front == NULL)
        {
            break;
        }
        else
        {
            QueuePush(&q, front->_left);
            QueuePush(&q, front->_right);
        }
    }

    while (QueueEmpty(&q) != 0)
    {
        BTNode* front = QueueFront(&q);
        if (front != NULL)
        {
            return 0;
        }
        QueuePop(&q);
    }

    return 1;

}
int IsCompleteBTree1(BTNode* root)    // flag      
{
    int flag = 1;
    Queue q;
    QueueInit(&q);

    if (root != NULL)
    {
        QueuePush(&q, root);
    }
    while (QueueEmpty(&q) != 0)
    {
        BTNode* cur = QueueFront(&q);
        QueuePop(&q);
        if (cur == NULL)
        {
            break;
        }
        else
        {
            if (cur->_left == NULL)
            {
                flag = 0;
            }
            else
            {
                QueuePush(&q, cur->_left);
            }
            if (cur->_right == NULL)
            {
                flag = 0;
            }
            else
            {
                if (flag == 0)
                    return 0;

                QueuePush(&q, cur->_right);
            }
        }
    }
    return 1;
}

//       
void BTreePrevOrderNonR(BTNode* root)
{
    BTNode* cur = root;
    Stack stack;
    StackInit(&stack);

    while (cur != NULL || StackEmpty(&stack) != 0)
    {
        while (cur != NULL)
        {
            printf("%d ", cur->_data);
            StackPush(&stack, cur);
            cur = cur->_left;
        }

        BTNode* top = StackTop(&stack);
        StackPop(&stack);
        cur = top->_right;
    }
    printf("
");
}

void BTreeInOrderNonR(BTNode* root)
{
    BTNode* cur = root;
    Stack stack;
    StackInit(&stack);

    while (cur != NULL || StackEmpty(&stack) != 0)
    {
        while (cur != NULL)
        {
            StackPush(&stack, cur);
            cur = cur->_left;
        }

        BTNode* top = StackTop(&stack);
        StackPop(&stack);
        printf("%d ", top->_data);
        cur = top->_right;
    }
    printf("
");
}

void BTreePostOrderNonR(BTNode* root)
{
    BTNode* cur = root;
    BTNode* prev = NULL;
    Stack stack;
    StackInit(&stack);

    while (cur != NULL || StackEmpty(&stack) != 0)
    {
        while (cur != NULL)
        {
            StackPush(&stack, cur);
            cur = cur->_left;
        }

        BTNode* top = StackTop(&stack);

        if (top->_right == NULL || top->_right == prev)
        {
            printf("%d ", top->_data);
            StackPop(&stack);
            prev = top;
        }
        else
        {
            cur = top->_right;
        }

    }
    printf("
");
}

void DestoryBTree(BTNode** pTree)   //  
{
    assert(pTree);

    if (*pTree == NULL)
        return;
    DestoryBTree(&(*pTree)->_left);
    DestoryBTree(&(*pTree)->_right);

    free(*pTree);
    *pTree = NULL;
    return;
}

BTNode* BTreeMirror(BTNode* root)   //  
{
    BTNode* tmp = root->_left;
    if (root == NULL)
        return NULL;
    root->_left = root->_right;
    root->_right = tmp;
    BTreeMirror(root->_left);
    BTreeMirror(root->_right);
    return root;
}

BTNode* BTMirrorNonR(BTNode* root)   //   
{
    Queue q;
    QueueInit(&q);
    if (root == NULL)
        return NULL;

    QueuePush(&q, root);
    while (QueueEmpty(&q) != 0)
    {
        BTNode* front = QueueFront(&q);
        QueuePop(&q);
        if (front != NULL)
        {
            BTNode* cur = front->_left;
            front->_left = front->_right;
            front->_right = cur;
            QueuePush(&q, front->_left);
            QueuePush(&q, front->_right);
        }
    }
    return root;    
}

테스트 용례

#include "BTree.h"

void TestBinaryTree()
{
    int a[] = { 1, 2, 3, '#', '#', 4, '#', '#', 5, 6, '#', '#', '#' };
//  int a[] = { 1, 2, 3, 4, '#', '#', 5, '#', '#',  '#', '#', 6, '#',9, '#' ,'#'};
    size_t index = 0;
    BTNode* tree = CreateBTree(a, &index, '#');
    BTreePrevOrder(tree);
    printf("
");
    BTreePrevOrderNonR(tree);
    BTreeInOrder(tree);
    printf("
");
    BTreePostOrder(tree);
    printf("
");
    BTreeLevelOrder(tree);
    printf("
");

    printf("BTreeSize?%d
", BTreeSize(tree));
    printf("BTreeLeafSize?%d
", BTreeLeafSize(tree));
    printf("BTreeKLevelSize?%d
", BTreeKLevelSize(tree, 2));
    printf("BTreeDepth?%d
", BTreeDepth(tree));
    printf("IsCompleteBTree?%d
", IsCompleteBTree(tree));
    printf("IsCompleteBTree?%d
", IsCompleteBTree1(tree));

}

int main()
{
    TestBinaryTree();
    return 0;
}