以二叉链表为存储结构，完成以下功能： 以先序递归方式创建一棵二叉树；输出二叉树的先序、中序和后序递归或非递归遍历下的结点访问次序；输出二叉树所有的叶子节点和叶子节点个数；输出二叉树的高度；输出二叉树的按层次遍历序列（提示：实现需用到队列）；c语言的代码

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

//二叉树结构体定义
typedef struct BiTNode {
    char data;              //数据域
    struct BiTNode *lchild; //左孩子指针
    struct BiTNode *rchild; //右孩子指针
}BiTNode, *BiTree;

//先序递归创建二叉树
void CreateBiTree(BiTree *T) {
    char ch;
    scanf("%c", &ch);
    if (ch == '#') {
        *T = NULL;
    }
    else {
        *T = (BiTNode*)malloc(sizeof(BiTNode));
        (*T)->data = ch;
        CreateBiTree(&((*T)->lchild));
        CreateBiTree(&((*T)->rchild));
    }
}

//先序递归遍历
void PreOrderTraverse(BiTree T) {
    if (T == NULL) return;
    printf("%c ", T->data);
    PreOrderTraverse(T->lchild);
    PreOrderTraverse(T->rchild);
}

//中序递归遍历
void InOrderTraverse(BiTree T) {
    if (T == NULL) return;
    InOrderTraverse(T->lchild);
    printf("%c ", T->data);
    InOrderTraverse(T->rchild);
}

//后序递归遍历
void PostOrderTraverse(BiTree T) {
    if (T == NULL) return;
    PostOrderTraverse(T->lchild);
    PostOrderTraverse(T->rchild);
    printf("%c ", T->data);
}

//先序非递归遍历（借助栈实现）
void PreOrderTraverseByStack(BiTree T) {
    BiTNode *stack[100];    //定义一个栈
    int top = -1;           //栈顶指针
    BiTNode *p;             //定义一个指针，用于遍历二叉树

    if (T == NULL) return;
    stack[++top] = T;       //根节点入栈
    while (top >= 0) {
        p = stack[top--];   //出栈并访问栈顶节点
        printf("%c ", p->data);
        if (p->rchild != NULL) {    //右孩子先入栈
            stack[++top] = p->rchild;
        }
        if (p->lchild != NULL) {    //左孩子后入栈
            stack[++top] = p->lchild;
        }
    }
}

//中序非递归遍历（借助栈实现）
void InOrderTraverseByStack(BiTree T) {
    BiTNode *stack[100];
    int top = -1;
    BiTNode *p = T;

    while (p != NULL || top >= 0) {
        if (p != NULL) {        //一直往左走，把左孩子入栈
            stack[++top] = p;
            p = p->lchild;
        }
        else {
            p = stack[top--];   //左孩子为空时，出栈并访问节点
            printf("%c ", p->data);
            p = p->rchild;      //然后转向右孩子节点
        }
    }
}

//后序非递归遍历（借助栈实现）
void PostOrderTraverseByStack(BiTree T) {
    BiTNode *stack[100];
    int top = -1;
    BiTNode *p = T;
    BiTNode *r = NULL;          //用r记录上一个访问的节点

    while (p != NULL || top >= 0) {
        if (p != NULL) {        //将左孩子入栈
            stack[++top] = p;
            p = p->lchild;
        }
        else {
            p = stack[top];     //左孩子为空时，取出栈顶节点判断右孩子是否存在
            if (p->rchild != NULL && p->rchild != r) {
                p = p->rchild;  //存在右孩子且未被访问过，则进入右子树
                stack[++top] = p;
                p = p->lchild;
            }
            else {
                printf("%c ", p->data); //否则出栈并访问该节点
                r = p;
                top--;
                p = NULL;
            }
        }
    }
}

//统计二叉树叶子节点数
int CountLeaf(BiTree T) {
    if (T == NULL) return 0;
    if (T->lchild == NULL && T->rchild == NULL) { //如果该节点是叶子节点
        return 1;
    }
    return CountLeaf(T->lchild) + CountLeaf(T->rchild);
}

//输出二叉树所有叶子节点
void PrintLeaf(BiTree T) {
    if (T == NULL) return;
    if (T->lchild == NULL && T->rchild == NULL) { //如果该节点是叶子节点
        printf("%c ", T->data);
    }
    PrintLeaf(T->lchild);
    PrintLeaf(T->rchild);
}

//求二叉树高度
int GetHeight(BiTree T) {
    if (T == NULL) return 0;
    int left_height = GetHeight(T->lchild);   //递归求左子树高度
    int right_height = GetHeight(T->rchild);  //递归求右子树高度
    return (left_height > right_height ? left_height : right_height) + 1;  //加上根节点
}

//按层次遍历（借助队列实现）
void LevelOrderTraverse(BiTree T) {
    BiTNode *queue[1000];   //定义一个队列
    int front = 0, rear = 0;    //队头队尾指针
    BiTNode *p;             //定义一个指针，用于遍历二叉树

    if (T == NULL) return;
    queue[rear++] = T;      //根节点入队
    while (front < rear) {
        p = queue[front++]; //出队并访问队头节点
        printf("%c ", p->data);
        if (p->lchild != NULL) {    //左孩子入队
            queue[rear++] = p->lchild;
        }
        if (p->rchild != NULL) {    //右孩子入队
            queue[rear++] = p->rchild;
        }
    }
}

int main() {
    BiTree T = NULL;
    printf("请按先序序列输入二叉树节点信息（'#'表示空节点）：\n");
    CreateBiTree(&T);

    printf("先序递归遍历结果：");
    PreOrderTraverse(T);
    printf("\n");

    printf("中序递归遍历结果：");
    InOrderTraverse(T);
    printf("\n");

    printf("后序递归遍历结果：");
    PostOrderTraverse(T);
    printf("\n");

    printf("先序非递归遍历结果：");
    PreOrderTraverseByStack(T);
    printf("\n");

    printf("中序非递归遍历结果：");
    InOrderTraverseByStack(T);
    printf("\n");

    printf("后序非递归遍历结果：");
    PostOrderTraverseByStack(T);
    printf("\n");

    printf("叶子节点的个数为：%d，叶子节点分别为：", CountLeaf(T));
    PrintLeaf(T);
    printf("\n");

    printf("二叉树的高度为：%d\n", GetHeight(T));

    printf("按层次遍历结果：");
    LevelOrderTraverse(T);
    printf("\n");

    return 0;
}