1．按先序序列构造一棵二叉链表表示的二叉树T； 2．对这棵二叉树进行递归遍历：先序、中序、后序以及层次遍历遍历序列，分别输出结点的遍历序列； 3. 对这棵树用非递归方式进行遍历：先序、中序以及后序遍历序列，分别输出结点的遍历序列； 4．求二叉树的深度/结点数目/叶结点数目； 5．将二叉树每个结点的左右子树交换位置； 6. 设计二叉树的双序遍历算法（双序遍历是指对于二叉树的每一个结点来说，先访问这个结点，再按双序遍历它的左子树，然后再一次访问这个结点，接下来按双序遍历它的右子树）； 7. 计算二叉树最大宽度（二叉树的最大宽度是指二叉树所有层中结点个数的最大值）； 8. 求二叉树中第一条最长的路径长度，并输出此路径上各结点。 9.用C语言

实现以上功能。

1. 构造二叉链表表示的二叉树

typedef struct BiTNode {
    int data;
    struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;

// 先序遍历构造二叉树
void createBiTree(BiTree *T) {
    int data;
    scanf("%d", &data);
    if (data == 0) {
        *T = NULL;
    } else {
        *T = (BiTree) malloc(sizeof(BiTNode));
        (*T)->data = data;
        createBiTree(&(*T)->lchild);
        createBiTree(&(*T)->rchild);
    }
}

2. 递归遍历二叉树

// 先序遍历
void preOrderTraverse(BiTree T) {
    if (T) {
        printf("%d ", T->data);
        preOrderTraverse(T->lchild);
        preOrderTraverse(T->rchild);
    }
}

// 中序遍历
void inOrderTraverse(BiTree T) {
    if (T) {
        inOrderTraverse(T->lchild);
        printf("%d ", T->data);
        inOrderTraverse(T->rchild);
    }
}

// 后序遍历
void postOrderTraverse(BiTree T) {
    if (T) {
        postOrderTraverse(T->lchild);
        postOrderTraverse(T->rchild);
        printf("%d ", T->data);
    }
}

// 层次遍历
void levelOrderTraverse(BiTree T) {
    if (!T) return;
    Queue Q;
    initQueue(&Q);
    enQueue(&Q, T);
    while (!isEmptyQueue(Q)) {
        BiTree p = deQueue(&Q);
        printf("%d ", p->data);
        if (p->lchild) enQueue(&Q, p->lchild);
        if (p->rchild) enQueue(&Q, p->rchild);
    }
}

3. 非递归遍历二叉树

// 先序遍历
void preOrderTraverseNonRecursion(BiTree T) {
    Stack S;
    initStack(&S);
    BiTree p = T;
    while (p || !isEmptyStack(S)) {
        if (p) {
            printf("%d ", p->data);
            push(&S, p);
            p = p->lchild;
        } else {
            p = pop(&S);
            p = p->rchild;
        }
    }
}

// 中序遍历
void inOrderTraverseNonRecursion(BiTree T) {
    Stack S;
    initStack(&S);
    BiTree p = T;
    while (p || !isEmptyStack(S)) {
        if (p) {
            push(&S, p);
            p = p->lchild;
        } else {
            p = pop(&S);
            printf("%d ", p->data);
            p = p->rchild;
        }
    }
}

// 后序遍历
void postOrderTraverseNonRecursion(BiTree T) {
    Stack S;
    initStack(&S);
    BiTree p = T, r = NULL;
    while (p || !isEmptyStack(S)) {
        if (p) {
            push(&S, p);
            p = p->lchild;
        } else {
            BiTree peek_elem = getTop(S);
            if (peek_elem->rchild && r != peek_elem->rchild) {
                p = peek_elem->rchild;
            } else {
                printf("%d ", peek_elem->data);
                r = pop(&S);
            }
        }
    }
}

4. 求二叉树的深度/结点数目/叶结点数目

// 求二叉树深度
int getDepth(BiTree T) {
    if (!T) return 0;
    int left_depth = getDepth(T->lchild);
    int right_depth = getDepth(T->rchild);
    return left_depth > right_depth ? left_depth + 1 : right_depth + 1;
}

// 求二叉树结点数
int getNodeNum(BiTree T) {
    if (!T) return 0;
    return getNodeNum(T->lchild) + getNodeNum(T->rchild) + 1;
}

// 求二叉树叶结点数
int getLeafNodeNum(BiTree T) {
    if (!T) return 0;
    if (!T->lchild && !T->rchild) return 1;
    return getLeafNodeNum(T->lchild) + getLeafNodeNum(T->rchild);
}

5. 将二叉树每个结点的左右子树交换位置

void swap(BiTree T) {
    if (!T) return;
    BiTree tmp = T->lchild;
    T->lchild = T->rchild;
    T->rchild = tmp;
    swap(T->lchild);
    swap(T->rchild);
}

6. 设计双序遍历算法

void doubleOrderTraverse(BiTree T) {
    if (!T) return;
    printf("%d ", T->data);
    doubleOrderTraverse(T->lchild);
    printf("%d ", T->data);
    doubleOrderTraverse(T->rchild);
}

7. 计算二叉树最大宽度

int getWidth(BiTree T) {
    if (!T) return 0;
    Queue Q;
    initQueue(&Q);
    enQueue(&Q, T);
    int max_width = 1;
    while (!isEmptyQueue(Q)) {
        int level_len = getSize(Q);
        max_width = max(max_width, level_len);
        for (int i = 0; i < level_len; i++) {
            BiTree p = deQueue(&Q);
            if (p->lchild) enQueue(&Q, p->lchild);
            if (p->rchild) enQueue(&Q, p->rchild);
        }
    }
    return max_width;
}

8. 求二叉树中第一条最长的路径长度，并输出此路径上各结点

void getLongestPath(BiTree T, int *max_depth, Stack *S, Stack *max_S) {
    if (!T) return;
    push(S, T);
    if (!T->lchild && !T->rchild) { // 到达叶结点
        if (S->size > *max_depth) {
            *max_depth = S->size;
            copyStack(S, max_S);
        }
    } else {
        getLongestPath(T->lchild, max_depth, S, max_S);
        getLongestPath(T->rchild, max_depth, S, max_S);
    }
    pop(S);
}

void printStack(Stack *S) {
    for (int i = 0; i < S->size; i++) {
        printf("%d ", S->data[i]->data);
    }
}

void printLongestPath(BiTree T) {
    int max_depth = 0;
    Stack S, max_S;
    initStack(&S);
    initStack(&max_S);
    getLongestPath(T, &max_depth, &S, &max_S);
    printStack(&max_S);
}