二叉树相关算法

一、层序遍历一个二叉树

 

/* 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);
    }
}

二、根据二叉树的前序遍历和中序遍历恢复二叉树

思路：由前序遍历顺序为“根->左->右”、中序遍历为“左->根->右”知前序遍历的第一个结点定为根结点，根结点在中序遍历中将该二叉树分为左右两颗子树。再对两颗子树分别递归求解即可。如前序遍历序列为“ABDGCEF”，中序遍历序列为“DGBAECF”，先找到根A，然后将该二叉树分为DGB和ECF两颗子树；由前序遍历序列BDG知B为根，可知DG为左子树，右子树为空；又由前序遍历序列DG知D为根，则G为右孩子；同理可将A的右子树恢复。

/* 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;
}

附：

层序遍历二叉树算法中的结点访问函数Visit()

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