二叉树相关算法

/* bt指向二叉树的根结点.本算法用到顺序队列 */
void LevelOrder(BiTreeNode* bt)
{
    SeqCQueue queue;
    BiTreeNode* p = bt;

    QueueInitiate(&queue);

    /* 若左/右孩子非空,则入队列 */
    if (bt -> leftChild != NULL) QueueAppend(&queue, * bt -> leftChild);
    if (bt -> rightChild != NULL) QueueAppend(&queue, * bt -> rightChild);

    /* 队列非空时,队首元素出队列,若其存在左/右孩子,则左/右孩子入队列 */
    while (QueueNotEmpty(queue)) {
        QueueDelete(&queue, p);
        Visit(p -> data);
        if (p -> leftChild != NULL) QueueAppend(&queue, * p -> leftChild);
        if (p -> rightChild != NULL) QueueAppend(&queue, * p -> rightChild);
    }
}

/* pre指向二叉树前序遍历的数组,in指向中序遍历的数组,n为二叉树的结点数 */
/* 即数组中元素个数(可用strlen(pre)表示).函数返回指向根结点的指针 */
BiTreeNode* BiTreeRecover(DataType* pre, DataType* in, int n)
{
    BiTreeNode* p;
    DataType* str;
    int r;

    if (n <= 0) return NULL;

    p = (BiTreeNode*)malloc(sizeof(BiTreeNode));    
    p -> data = * pre;
    for (str = in; * str != * pre; str ++);
    r = str - in;
    p -> leftChild = BiTreeRecover(pre + 1, in, r);
    p -> rightChild = BiTreeRecover(pre + 1 + r, str + 1, n - r - 1);

    return p;
}

/* T1,T2分别指向两个二叉树的根结点.若T1与T2相等,则返回1;否则返回0 */
int BiTreeEqual(BiTreeNode* T1, BiTreeNode* T2)
{
    if (T1 == NULL && T2 == NULL) return 1;
    if (T1 != NULL && T2 != NULL && T1 -> data == T2 -> data && \
        BiTreeEqual(T1 -> leftChild, T2 -> leftChild) && \
        BiTreeEqual(T1 -> rightChild, T2 -> rightChild)) return 1;

    return 0;
}

void Visit(DataType item)
{
    printf("%c", item);
}