(06-01)写出以下二叉树先序/中序/后序遍历的顺序。ab cde fg请输入文字

对于给定的二叉树，按照先序、中序和后序遍历的顺序来描述如下：

先序遍历顺序（根左右）：ab cde fg
先序遍历的顺序是，首先访问根节点a，然后按照从左到右的顺序遍历左子树和右子树。对于当前的二叉树，根节点为a，首先访问a。然后按照从左到右的顺序遍历左子树和右子树，左子树为b，右子树为cde fg。继续遍历左子树b，得到先序遍历结果ab。然后遍历右子树cde fg，先访问c，再访问d，再访问e，最后访问f和g。所以最终的先序遍历结果为ab cde fg。

中序遍历顺序（左根右）：b a c d e f g
中序遍历的顺序是，首先按照从左到右的顺序遍历左子树，然后访问根节点，最后按照从左到右的顺序遍历右子树。对于当前的二叉树，首先按照从左到右的顺序遍历左子树，得到中序遍历结果b。然后访问根节点a。最后按照从左到右的顺序遍历右子树，得到中序遍历结果cde fg。对于右子树cde fg，首先按照从左到右的顺序遍历左子树，得到中序遍历结果c。然后访问根节点d。最后按照从左到右的顺序遍历右子树，得到中序遍历结果e fg。对于右子树e fg，首先按照从左到右的顺序遍历左子树和右子树，得到中序遍历结果e f g。所以最终的中序遍历结果为b a c d e f g。

后序遍历顺序（左右根）：b e f g d c a
后序遍历的顺序是，首先按照从左到右的顺序遍历左子树和右子树，最后访问根节点。对于当前的二叉树，首先按照从左到右的顺序遍历左子树和右子树，得到后序遍历结果b e f g d c。最后访问根节点a。所以最终的后序遍历结果为b e f g d c a。

相关问题

构建二叉树的二叉链表存储结构，实现二叉树的创建、二叉树的先序/中序/后序递归遍历、统计二叉树的高度、统计各类结点的个数、先序/中序非递归遍历、层序遍历等运算。

二叉树的二叉链表存储结构定义如下：

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

其中，data 表示结点的数据项，lchild 和 rchild 分别指向左右子树。

二叉树的创建可以采用递归方式，先输入根结点，然后递归输入左右子树。

void createBiTree(BiTree *T) {
    int data;
    scanf("%d", &data);
    if (data == -1) {
        *T = NULL;
    } else {
        *T = (BiTree) malloc(sizeof(BiTNode));
        (*T)->data = data;
        createBiTree(&((*T)->lchild));
        createBiTree(&((*T)->rchild));
    }
}

二叉树的先序/中序/后序递归遍历可以采用类似的递归方式，分别先遍历根结点，然后递归遍历左右子树。

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

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

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

统计二叉树的高度可以采用递归方式，左右子树的高度取最大值并加 1。

int getDepth(BiTree T) {
    if (T == NULL) {
        return 0;
    } else {
        int leftDepth = getDepth(T->lchild);
        int rightDepth = getDepth(T->rchild);
        return (leftDepth > rightDepth ? leftDepth : rightDepth) + 1;
    }
}

统计各类结点的个数同样可以采用递归方式，分别统计根结点、左子树、右子树的结点个数。

int getNodeNum(BiTree T) {
    if (T == NULL) {
        return 0;
    } else {
        return getNodeNum(T->lchild) + getNodeNum(T->rchild) + 1;
    }
}

int getLeafNum(BiTree T) {
    if (T == NULL) {
        return 0;
    } else if (T->lchild == NULL && T->rchild == NULL) {
        return 1;
    } else {
        return getLeafNum(T->lchild) + getLeafNum(T->rchild);
    }
}

int getSingleNum(BiTree T) {
    if (T == NULL) {
        return 0;
    } else if ((T->lchild == NULL && T->rchild != NULL) || (T->lchild != NULL && T->rchild == NULL)) {
        return getSingleNum(T->lchild) + getSingleNum(T->rchild) + 1;
    } else {
        return getSingleNum(T->lchild) + getSingleNum(T->rchild);
    }
}

先序/中序非递归遍历采用栈来实现。先序遍历时，先将根结点入栈，然后弹出栈顶结点并输出其值，如果该结点有右子树，则将其右子树入栈；如果该结点有左子树，则将其左子树入栈。中序遍历时，先将根结点入栈，然后将其左子树全部入栈，再弹出栈顶结点并输出其值，最后将其右子树入栈。

// 先序非递归遍历
void preOrderNonRecursive(BiTree T) {
    if (T == NULL) {
        return;
    }
    BiTree stack[MAXSIZE];
    int top = -1;
    stack[++top] = T;
    while (top != -1) {
        BiTree node = stack[top--];
        printf("%d ", node->data);
        if (node->rchild != NULL) {
            stack[++top] = node->rchild;
        }
        if (node->lchild != NULL) {
            stack[++top] = node->lchild;
        }
    }
}

// 中序非递归遍历
void inOrderNonRecursive(BiTree T) {
    if (T == NULL) {
        return;
    }
    BiTree stack[MAXSIZE];
    int top = -1;
    BiTree node = T;
    while (node != NULL || top != -1) {
        while (node != NULL) {
            stack[++top] = node;
            node = node->lchild;
        }
        if (top != -1) {
            node = stack[top--];
            printf("%d ", node->data);
            node = node->rchild;
        }
    }
}

层序遍历采用队列来实现。先将根结点入队，然后每次弹出队首结点并输出其值，如果该结点有左子树，则将其左子树入队；如果该结点有右子树，则将其右子树入队。

void levelOrder(BiTree T) {
    if (T == NULL) {
        return;
    }
    BiTree queue[MAXSIZE];
    int front = 0, rear = 0;
    queue[rear++] = T;
    while (front != rear) {
        BiTree node = queue[front++];
        printf("%d ", node->data);
        if (node->lchild != NULL) {
            queue[rear++] = node->lchild;
        }
        if (node->rchild != NULL) {
            queue[rear++] = node->rchild;
        }
    }
}

c语言用二叉链实现二叉树的创建、二叉树的先序/中序/后序递归遍历、统计二叉树的高度、统计结点的个数、叶子结点的个数、先序/中序非递归遍历、层序遍历等运算。

好的，下面我来为您介绍一下C语言如何用二叉链表实现二叉树的创建，以及实现二叉树的各种操作。

1. 二叉树的结构体定义

typedef struct BiTNode
{
    char data; // 数据域
    struct BiTNode *lchild, *rchild; // 左右孩子指针
}BiTNode, *BiTree;

2. 二叉树的创建

二叉树的创建可以采用递归的方式，每次递归创建左右子树。

void CreateBiTree(BiTree *T)
{
    char ch;
    scanf("%c", &ch);
    if(ch == '#') // 如果输入的是'#'，则表示该节点为空
        *T = NULL;
    else
    {
        *T = (BiTree)malloc(sizeof(BiTNode));
        (*T)->data = ch;
        CreateBiTree(&((*T)->lchild)); // 递归创建左子树
        CreateBiTree(&((*T)->rchild)); // 递归创建右子树
    }
}

3. 二叉树的先序/中序/后序递归遍历

先序遍历：根节点 -> 左子树 -> 右子树

void PreOrderTraverse(BiTree T)
{
    if(T != NULL)
    {
        printf("%c ", T->data);
        PreOrderTraverse(T->lchild);
        PreOrderTraverse(T->rchild);
    }
}

中序遍历：左子树 -> 根节点 -> 右子树

void InOrderTraverse(BiTree T)
{
    if(T != NULL)
    {
        InOrderTraverse(T->lchild);
        printf("%c ", T->data);
        InOrderTraverse(T->rchild);
    }
}

后序遍历：左子树 -> 右子树 -> 根节点

void PostOrderTraverse(BiTree T)
{
    if(T != NULL)
    {
        PostOrderTraverse(T->lchild);
        PostOrderTraverse(T->rchild);
        printf("%c ", T->data);
    }
}

4. 统计二叉树的高度

二叉树的高度可以采用递归的方式，每次递归计算左右子树的高度，并取最大值。

int TreeHeight(BiTree T)
{
    int leftHeight, rightHeight;
    if(T == NULL)
        return 0;
    else
    {
        leftHeight = TreeHeight(T->lchild);
        rightHeight = TreeHeight(T->rchild);
        return (leftHeight > rightHeight ? leftHeight : rightHeight) + 1;
    }
}

5. 统计节点的个数

节点的个数可以采用递归的方式，每次递归计算左右子树的节点个数，并加上根节点。

int NodeCount(BiTree T)
{
    if(T == NULL)
        return 0;
    else
        return NodeCount(T->lchild) + NodeCount(T->rchild) + 1;
}

6. 统计叶子节点的个数

叶子节点的个数可以采用递归的方式，如果当前节点是叶子节点，则返回1，否则返回左右子树叶子节点的个数之和。

int LeafCount(BiTree T)
{
    if(T == NULL)
        return 0;
    else if(T->lchild == NULL && T->rchild == NULL)
        return 1;
    else
        return LeafCount(T->lchild) + LeafCount(T->rchild);
}

7. 先序/中序非递归遍历

先序非递归遍历可以采用栈的方式，先入根节点，然后依次入栈右子树、左子树。每次出栈打印节点即可。

void PreOrderTraverse2(BiTree T)
{
    if(T == NULL)
        return;
    BiTree p;
    Stack stack;
    InitStack(&stack);
    Push(&stack, T);
    while(!StackEmpty(stack))
    {
        Pop(&stack, &p);
        printf("%c ", p->data);
        if(p->rchild != NULL)
            Push(&stack, p->rchild);
        if(p->lchild != NULL)
            Push(&stack, p->lchild);
    }
}

中序非递归遍历可以采用栈的方式，先入根节点和左子树，然后依次入栈右子树。每次出栈打印节点即可。

void InOrderTraverse2(BiTree T)
{
    if(T == NULL)
        return;
    BiTree p;
    Stack stack;
    InitStack(&stack);
    Push(&stack, T);
    while(!StackEmpty(stack))
    {
        while(GetTop(stack, &p) && p != NULL)
            Push(&stack, p->lchild);
        Pop(&stack, &p);
        if(!StackEmpty(stack))
        {
            Pop(&stack, &p);
            printf("%c ", p->data);
            Push(&stack, p->rchild);
        }
    }
}

8. 层序遍历

层序遍历可以采用队列的方式，先入根节点，然后依次入队左右子树。每次出队打印节点即可。

void LevelOrderTraverse(BiTree T)
{
    if(T == NULL)
        return;
    BiTree p;
    Queue queue;
    InitQueue(&queue);
    EnQueue(&queue, T);
    while(!QueueEmpty(queue))
    {
        DeQueue(&queue, &p);
        printf("%c ", p->data);
        if(p->lchild != NULL)
            EnQueue(&queue, p->lchild);
        if(p->rchild != NULL)
            EnQueue(&queue, p->rchild);
    }
}

以上就是C语言用二叉链表实现二叉树的各种操作的代码实现。