C语言实现1. 二叉树的递归遍历 2. 二叉树的非递归遍历 3. 二叉树的层次遍历 4. 输出二叉树上所有叶节点 5. 求二叉树的高度 6. 二叉树层序生成算法

1. 二叉树的递归遍历：
二叉树的递归遍历是指通过递归方法遍历二叉树的各个节点，按照某种次序访问每个节点。常见的二叉树遍历方式有前序遍历、中序遍历和后序遍历。

2. 二叉树的非递归遍历：
二叉树的非递归遍历是指通过循环等非递归方法遍历二叉树的各个节点，按照某种次序访问每个节点。非递归遍历需要借助栈来实现，常见的二叉树遍历方式有前序遍历、中序遍历和后序遍历。

3. 二叉树的层次遍历：
二叉树的层次遍历是指按照从上到下、从左到右的顺序遍历每一层节点。常用的方法是使用队列来实现，首先将根节点入队列，然后依次出队列，并将其左右子节点入队列，直到队列为空。

4. 输出二叉树上所有叶节点：
二叉树上的叶节点是指没有子节点的节点。可以通过递归方式，对每个节点进行判断，如果该节点没有左右子节点，则将该节点输出。

5. 求二叉树的高度：
二叉树的高度是指从根节点到叶节点最长路径上经过的边数。可以通过递归方式求解，从左右子树中选取较大的一个加上根节点即可。

6. 二叉树层序生成算法：
二叉树层序生成算法是指按照从上到下、从左到右的顺序依次生成每个节点。可以使用队列来实现，首先将根节点入队列，然后依次出队列，并根据当前节点生成其左右子节点，将其入队列，直到生成完所有节点。

相关问题

用C语言实现二叉树的非递归遍历，输入二叉树后，输出层次遍历结果

好的，以下是用C语言实现二叉树的非递归遍历，输出层次遍历结果的代码：

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

typedef struct Node {
    int data;
    struct Node* left;
    struct Node* right;
} Node;

typedef struct Queue {
    Node** array;
    int front;
    int rear;
    int size;
} Queue;

Queue* createQueue(int size) {
    Queue* queue = (Queue*)malloc(sizeof(Queue));
    queue->array = (Node**)malloc(sizeof(Node*) * size);
    queue->front = 0;
    queue->rear = -1;
    queue->size = size;
    return queue;
}

void enqueue(Queue* queue, Node* node) {
    if (queue->rear == queue->size - 1) {
        printf("Queue is full\n");
        return;
    }
    queue->rear++;
    queue->array[queue->rear] = node;
}

Node* dequeue(Queue* queue) {
    if (queue->front > queue->rear) {
        printf("Queue is empty\n");
        return NULL;
    }
    Node* node = queue->array[queue->front];
    queue->front++;
    return node;
}

Node* createNode(int data) {
    Node* node = (Node*)malloc(sizeof(Node));
    node->data = data;
    node->left = NULL;
    node->right = NULL;
    return node;
}

void insertNode(Node** root, int data) {
    if (*root == NULL) {
        *root = createNode(data);
        return;
    }
    Queue* queue = createQueue(100);
    enqueue(queue, *root);
    while (1) {
        Node* node = dequeue(queue);
        if (node == NULL) {
            enqueue(queue, createNode(data));
            break;
        }
        if (node->left != NULL) {
            enqueue(queue, node->left);
        } else {
            node->left = createNode(data);
            break;
        }
        if (node->right != NULL) {
            enqueue(queue, node->right);
        } else {
            node->right = createNode(data);
            break;
        }
    }
}

void levelOrderTraversal(Node* root) {
    if (root == NULL) {
        printf("Tree is empty\n");
        return;
    }
    Queue* queue = createQueue(100);
    enqueue(queue, root);
    while (queue->front <= queue->rear) {
        Node* node = dequeue(queue);
        printf("%d ", node->data);
        if (node->left != NULL) {
            enqueue(queue, node->left);
        }
        if (node->right != NULL) {
            enqueue(queue, node->right);
        }
    }
}

int main() {
    Node* root = NULL;
    insertNode(&root, 1);
    insertNode(&root, 2);
    insertNode(&root, 3);
    insertNode(&root, 4);
    insertNode(&root, 5);
    insertNode(&root, 6);
    insertNode(&root, 7);
    printf("Level order traversal: ");
    levelOrderTraversal(root);
    return 0;
}

这个程序中，我们定义了一个`Node`结构体，表示二叉树节点，包含一个整型数据`data`以及左右子节点的指针。我们还定义了一个`Queue`结构体，表示队列，包含一个`Node`类型的数组，以及队首、队尾、队列大小等信息。`createQueue`函数用于创建一个指定大小的队列，`enqueue`函数用于将一个节点入队，`dequeue`函数用于将队首节点出队。`createNode`函数用于创建一个值为`data`的节点。`insertNode`函数用于将一个值为`data`的节点插入二叉树中。`levelOrderTraversal`函数用于进行层次遍历，并输出遍历结果。

在`main`函数中，我们创建一个空的二叉树，并依次插入值为1到7的节点。然后调用`levelOrderTraversal`函数进行层次遍历，并输出结果。

希望这个程序能够解决你的问题！

二叉树递归遍历和非递归遍历的时空复杂度

二叉树的递归遍历和非递归遍历的时空复杂度如下所示：

1. 递归遍历的时空复杂度：
- 时间复杂度：对于含有n个节点的二叉树，递归遍历的时间复杂度为O(n)，因为每个节点都需要被访问一次。
- 空间复杂度：递归遍历的空间复杂度取决于递归调用的深度，即树的高度。在最坏情况下，二叉树的高度为n，所以递归遍历的空间复杂度为O(n)。

2. 非递归遍历的时空复杂度：
- 时间复杂度：对于含有n个节点的二叉树，非递归遍历的时间复杂度也为O(n)，因为每个节点都需要被访问一次。
- 空间复杂度：非递归遍历使用了辅助数据结构栈来存储节点，所需的空间取决于栈的最大容量，即树的深度。在最坏情况下，二叉树的深度为n，所以非递归遍历的空间复杂度为O(n)。