Binary tree traversal-- level-order traversal using queue【1月23日学习笔记】

//Binary tree traversal-- level-order traversal using queue
#include<iostream>
#include<queue>//STL
using namespace std;

struct node {
    int data;
    node *left, *right;
};

node* getnewnode(int x)
{
    node* temp = new node;
    temp->data = x;
    temp->left = temp->right = NULL;

    return temp;
}

void insert(node*& travptr, int data) {//Node*& travptr 表示 travptr 是一个引用，引用的是一个指向 Node 类型的指针

    if (travptr == NULL)
    {
        travptr = getnewnode(data);
        return;
    }
    (data > travptr->data) ? insert(travptr->right, data) : insert(travptr->left, data);
}

void levelorder(node* root) {
    if (root == NULL) return;
    queue<node*> Q;//存放指针（地址）
    Q.push(root);

    while (!Q.empty()) {
        cout << Q.front()->data << " ";//;利用指针访问数据
        if(Q.front()->left != NULL)    Q.push(Q.front()->left);//利用Q.front()访问子节点，注意指针是否为空
        if(Q.front()->right != NULL)  Q.push(Q.front()->right);
        Q.pop();
    }
}//时间复杂度：O（1）in best case
 //           O（n）in average case

int main()
{
    node* root = NULL;

    insert(root, 2);
    insert(root, 1);
    insert(root, 3);
    insert(root, 0);
    insert(root, 5);
    levelorder(root);
    return 0;
}