广度优先搜索

静态版二叉树

#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
struct Node{                              //用静态数组记录二叉树
  char value;
  int lson, rson;                         //左右孩子
}tree[N];                                 //tree[0]不用，0表示空结点
int index = 1;                            //记录结点存在tree[]的位置，从tree[1]开始用
int newNode(char val){
  tree[index].value = val;
  tree[index].lson = 0;                   //0表示空，tree[0]不用
  tree[index].rson = 0;
  return index ++;
}
void Insert(int &father, int child, int l_r){          //插入孩子
  if(l_r == 0)      tree[father].lson = child;         //左孩子
  else                    tree[father].rson = child;   //右孩子
}
int buildtree(){                                                    //建一棵二叉树
  int A = newNode('A');int B = newNode('B');int C = newNode('C');   //创建节点,A = 1, B = 2...以此类推
  int D = newNode('D');int E = newNode('E');int F = newNode('F');
  int G = newNode('G');int H = newNode('H');int I = newNode('I');
  Insert(E,B,0);        Insert(E,G,1);                              //E的左孩子是B，右孩子是G
  Insert(B,A,0);        Insert(B,D,1);                              
  Insert(G,F,0);        Insert(G,I,1);
  Insert(D,C,0);        Insert(I,H,0);
  int root = E;
  return root;                       //返回根节点
}
int main(){
  int root = buildtree();                               //二叉树根节点
  queue <int> q;                                        //队列
  q.push(root);                                         //从根结点开始
  while(q.size()){                                      //非空
    int tmp = q.front();
    cout << tree[tmp].value << " ";                     //打印队头
    q.pop();                                            //去掉队头
    if(tree[tmp].lson != 0)   q.push(tree[tmp].lson);   //左孩子入队
    if(tree[tmp].rson != 0) q.push(tree[tmp].rson);     //右孩子入队
  }
  return 0;
}

笔记：广度优先搜索使用队列的方式入队左右孩子，处理完 i 层后，才会处理 i + 1 层，每个节点都可以照顾到，而且不重复搜索节点

指针版二叉树

#include <bits/stdc++.h>
using namespace std;
struct node{                         //指针二叉树
  char value;
  node *l, *r;
  node(char value='#',node *l=NULL, node *r=NULL):value(value), l(l), r(r){}      //初始化列表：有参构造
};
void remove_tree(node *root){         //释放空间
  if(root == NULL) return;
  remove_tree(root->l);
  remove_tree(root->r);
  delete root;
}
int main(){
  node *A,*B,*C,*D,*E,*F,*G,*H,*I;
  A = new node('A'); B = new node('B'); C = new node('C');       //建一棵二叉树
  D = new node('D'); E = new node('E'); F = new node('F');
  G = new node('G'); H = new node('H'); I = new node('I');
  E->l = B; E->r = G; B->l = A; B->r = D;                        //访问结构体指针放入左孩子和右孩子
  G->l = F; G->r = I; D->l = C; I->l = H;
  queue <node> q;
  q.push(*E);                         //队尾插入数根节点
  while(q.size()){
    node *tmp;                        //搜索指针
    tmp = &(q.front());               //从根节点开始搜索
    cout << tmp->value << " ";        //打印队头
    q.pop();                          //去掉队头
    if(tmp->l) q.push(*(tmp->l));     //左孩子入队
    if(tmp->r) q.push(*(tmp->r));     //右孩子入队
  }
  remove_tree(E);
  return 0;
}

笔记：最后释放内存交还操作系统，以便操作系统将这片内存空间分配给其他程序使用