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

using namespace std;

typedef struct BTNode{
    int data;
    struct BTNode *lchild,*rchild;
}BTNode;

int main()
{
    //new一个结点并进行构造函数初始化
    BTNode a1;  a1.data = http://www.mamicode.com/1;//这里的a1是普通变量
    //BTNode a1 = malloc 以前的a1是这个指针变量，接收的值是地址，并指向结构体的普通变量
    BTNode a2;  a2.data = http://www.mamicode.com/2;
    BTNode a3;  a3.data = 3;


    //建立连接关系
    a1.lchild = &a2;
    a1.rchild = &a3;
    a2.lchild = NULL; //变量a2.lchild接收的是地址
    a2.rchild = NULL; //a2.rchild是结构体指针变量
    a3.lchild = NULL;
    a3.rchild = NULL;

    //遍历二叉树
    queue<BTNode *> q1;
    BTNode *a =&a1; //a是当前访问的结点，a是结构体指针变量

    q1.push(&a1);      //算法1:根结点入队，地址入队
    while(!q1.empty()){//算法2:当队列不为空是循环

       cout<< q1.front()->data<<endl;    //算法3：弹出并访问队首元素
       a = q1.front(); //这一步很重要，把控制权交出来了了
       q1.pop();     //弹出队列的第一个元素，注意，并不会返回被弹出元素的值

       if(a->lchild!=NULL)  {a = a->lchild;  q1.push(a->lchild);} ;
       if(a->rchild!=NULL)  {q1.push(a->rchild);};
    }

    cout <<"-----------"<<endl;
    void preOrder(BTNode *a);
    preOrder(&a1);

    return 0;
}

void preOrder(BTNode *a)
{
    if(a==NULL) return;

    preOrder(a->lchild);
    preOrder(a->rchild);
    cout << a->data <<endl;
}