Obsidian-Knowledge-Base/X-Knowledge-Base/raw/Joplin/计算机专业基础/数据结构与算法/(C)840数据结构与算法/2.二叉树的实现和应用.md

#pragma clang diagnostic push
#pragma ide diagnostic ignored "misc-no-recursion"

#include <stdio.h>
#include <stdlib.h>

typedef int ElementType;
struct BTreeNode {
    ElementType Data;
    struct BTreeNode *Left;
    struct BTreeNode *Right;
};

int max(int a, int b) {
    return a > b ? a : b;
}

void Visit(struct BTreeNode *T) {
    printf("%d ", T->Data);
}

void PreOrder(struct BTreeNode *T) {
    if (T != NULL) {
        Visit(T);
        PreOrder(T->Left);
        PreOrder(T->Right);
    }
}

void InOrder(struct BTreeNode *T) {
    if (T != NULL) {
        InOrder(T->Left);
        Visit(T);
        InOrder(T->Right);
    }
}

void PostOrder(struct BTreeNode *T) {
    if (T != NULL) {
        PostOrder(T->Left);
        PostOrder(T->Right);
        Visit(T);
    }
}

int Count(struct BTreeNode *T) {
    if (T == NULL) {
        return 0;
    }
    return 1 + Count(T->Left) + Count(T->Right);
}

int CountLeaf(struct BTreeNode *T) {
    if (T == NULL) {
        return 0;
    }
    if (T->Left == NULL && T->Right == NULL) {
        return 1;
    }
    return CountLeaf(T->Left) + CountLeaf(T->Right);
}

int Height(struct BTreeNode *T) {
    if (T == NULL) {
        return 0;
    } else {
        return 1 + max(Height(T->Left), Height(T->Right));
    }
}

void SqPreOrder(char SqTree[], int Index, int MaxSize) {
    if (Index < MaxSize) {
        printf("%c ", SqTree[Index]);
        SqPreOrder(SqTree, 2 * Index + 1, MaxSize);
        SqPreOrder(SqTree, 2 * Index + 2, MaxSize);
    }
}

int main() {
    //数据初始化
    struct BTreeNode *Tree, *n2, *n3, *n4, *n5, *n6;
    Tree = (struct BTreeNode *) malloc(sizeof(struct BTreeNode));
    n2 = (struct BTreeNode *) malloc(sizeof(struct BTreeNode));
    n3 = (struct BTreeNode *) malloc(sizeof(struct BTreeNode));
    n4 = (struct BTreeNode *) malloc(sizeof(struct BTreeNode));
    n5 = (struct BTreeNode *) malloc(sizeof(struct BTreeNode));
    n6 = (struct BTreeNode *) malloc(sizeof(struct BTreeNode));

    Tree->Data = 1;
    Tree->Left = n2;
    Tree->Right = NULL;

    n2->Data = 2;
    n2->Left = n3;
    n2->Right = n4;

    n3->Data = 3;
    n3->Left = n3->Right = NULL;

    n4->Data = 4;
    n4->Left = n5;
    n4->Right = n6;

    n5->Data = 5;
    n5->Left = n5->Right = NULL;

    n6->Data = 6;
    n6->Left = n6->Right = NULL;
    //测试函数
    int count = Count(Tree);
    printf("count=%d\n", count);
    int countLeaf = CountLeaf(Tree);
    printf("countLeaf=%d\n", countLeaf);
    int height = Height(Tree);
    printf("height=%d\n", height);

    printf("PreOrder: ");
    PreOrder(Tree);
    printf("\n");

    printf("InOrder: ");
    InOrder(Tree);
    printf("\n");

    printf("PostOrder: ");
    PostOrder(Tree);
    printf("\n");

    //释放空间
    free(Tree);
    free(n2);
    free(n3);
    free(n4);
    free(n5);
    free(n6);

    char SqTree[] = {'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k'};
    int MaxSize = sizeof(SqTree) / sizeof(char);
    printf("SqPreOrder: ");
    SqPreOrder(SqTree, 0, MaxSize);
    printf("\n");

    return 0;
}

#pragma clang diagnostic pop