算法应用-二叉树层次遍历

对于一个二叉树结构，请写代码实现传入一个二叉树的根节点，按层次顺序输出二叉树各个节点：

二叉树.png 输出：ABCDEFG.

方法一：从根节点开始加入一个队列，每次让节点的左右孩子依次加入队列中，最后输出队列里面的内容。队列是先进先出的，所以是可以实现按顺序输出。代码如下：

typedef struct TreeNode{
    struct TreeNode *left;
    struct TreeNode *right;
    char val;
}BiTreeNode, *binTree;

typedef struct queue{
    struct TreeNode *nodeQueue[100];
    int front, rear;
}Queue;

Queue q;

// 按照前序遍历的方式输入，遇到没有左孩子和右孩子用空格代替
void createTree(binTree *root){
    char input;
    scanf("%c", &input);
    if (input == ' ') {
        root = NULL;
        return;
    }
    *root = (struct TreeNode *)malloc(sizeof(struct TreeNode));
    (*root)->val = input;
    createTree(&(*root)->left);
    createTree(&(*root)->right);
}

void initializeQueue(){
    q.front = 0;
    q.rear = 0;
}

void push(struct TreeNode* root){
    q.nodeQueue[++q.rear] = root;
}

struct TreeNode * pop(){// 从front读出一个来。
    return q.nodeQueue[++q.front];
}

int empty(){
    return q.front == q.rear;
}


void levelOrderTraversal(struct TreeNode *root){//二叉树的层次遍历
    if (root == NULL) {
        return;
    }
    struct TreeNode *temp;
    push(root);
    while (!empty()) {
        temp = pop();
        printf("%c ", temp->val);
        
        if (temp->left) {
            push(temp->left);
        }
        if (temp->right) {
            push(temp->right);
        }
    }
}

// 
int main(int argc, const char * argv[]) {
    printf("请输入二叉树：");
    binTree root = NULL;
    createTree(&root);
    
    initializeQueue();
    
    printf("二叉树层序遍历的结果：");
    levelOrderTraversal(root);
    return 0;
}

方法二：一次将每个节点的左右孩子加到一个数组中。代码如下：

void levelOrderTraversal2222(struct TreeNode *root){//二叉树的层次遍历
    if (root == NULL) {
        return;
    }
    
    struct TreeNode *arr[100];
    int arr_index = 0;
    arr[arr_index++] = root;
    
    int arr_front = 0;
    while (arr_front != arr_index) {
        
        struct TreeNode *curNode = arr[arr_front++];
        printf("%c", curNode->val);
        if (curNode->left) {
            arr[arr_index++] = curNode->left;
        }
        if (curNode->right) {
            arr[arr_index++] = curNode->right;
        }
    }
}