静态数组版二叉树
#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 dfn[N] = {0}; //dfn[i]是结点i的时间戳
int dfn_timer = 0;
void dfn_order (char father){
if(father != 0){
dfn[father] = ++dfn_timer;
printf("dfn[%c]=%d; ", tree[father].value, dfn[father]); //打印时间戳
dfn_order (tree[father].lson);
dfn_order (tree[father].rson);
}
}
int visit_timer = 0;
void visit_order (int father){ //打印DFS序
if(father != 0){
printf("visit[%c]=%d; ", tree[father].value, ++visit_timer);
//打印DFS序：第1次访问结点
visit_order (tree[father].lson);
visit_order (tree[father].rson);
printf("visit[%c]=%d; ", tree[father].value, ++visit_timer);
//打印DFS序：第2次回溯
}
}
int deep[N] = {0}; //deep[i]是结点i的深度
int deep_timer = 0;
void deep_node (int father){
if(father != 0){
deep[father] = ++deep_timer; //打印树的深度，第一次访问时，深度+1
printf("deep[%c]=%d; ",tree[father].value,deep[father]);
deep_node (tree[father].lson);
deep_node (tree[father].rson);
deep_timer--; //回溯时，深度-1
}
}
int num[N] = {0}; //num[i]是以i为父亲的子树上的结点总数
int num_node (int father){
if(father == 0) return 0;
else{
num[father] = num_node (tree[father].lson) +
num_node (tree[father].rson) + 1; //左节点总数+右节点总数+自身节点
printf("num[%c]=%d; ", tree[father].value, num[father]); //打印数量
return num[father]; //返回节点数量
}
}
void preorder (int father){ //求先序序列
if(father != 0){
cout << tree[father].value <<" "; //先序输出
preorder (tree[father].lson);
preorder (tree[father].rson);
}
}
void inorder (int father){ //求中序序列
if(father != 0){
inorder (tree[father].lson);
cout << tree[father].value <<" "; //中序输出
inorder (tree[father].rson);
}
}
void postorder (int father){ //求后序序列
if(father != 0){
postorder (tree[father].lson);
postorder (tree[father].rson);
cout << tree[father].value <<" "; //后序输出
}
}
int buildtree(){ //建一棵树
int A = newNode('A');int B = newNode('B');int C = newNode('C'); //定义结点
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();
cout <<"dfn order: "; dfn_order(root); cout << endl; //打印时间戳 = 先序输出
cout <<"visit order: "; visit_order(root); cout << endl; //打印DFS序：递去打印一次，归来打印第二次
cout <<"deep order: "; deep_node(root); cout << endl; //打印结点深度：递去深度+1，归来深度-1
cout <<"num of tree: "; num_node(root); cout << endl; //打印子树上的结点数：计算公式使用递归方式返回i+1层的节点，再计算i层的节点
cout <<"in order: "; inorder(root); cout << endl; //打印中序序列：左、父、右节点
cout <<"pre order: "; preorder(root); cout << endl; //打印先序序列：父、左、右节点
cout <<"post order: "; postorder(root); cout << endl; //打印后序序列：左、右、父节点
return 0;
}
笔记：深度优先算法使用递归的方式输出节点，每条路走到头才会回头，输出了几种常用的节点访问方式
指针版二叉树
#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 preorder (node *root){ //求先序序列
if(root != NULL){
cout << root->value <<" "; //先序输出
preorder (root ->l);
preorder (root ->r);
}
}
void inorder (node *root){ //求中序序列
if(root != NULL){
inorder (root ->l);
cout << root->value <<" "; //中序输出
inorder (root ->r);
}
}
void postorder (node *root){ //求后序序列
if(root != NULL){
postorder (root ->l);
postorder (root ->r);
cout << root->value <<" "; //后序输出
}
}
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;
cout << "in order: "; inorder(E); cout << endl; //打印中序序列
cout << "pre order: "; preorder(E); cout << endl; //打印先序序列
cout << "post order: "; postorder(E); cout << endl; //打印后序序列
remove_tree(E);
return 0;
}
笔记：指针版的BFS和DFS比较起来更加明显，一个是队列一层一层的寻找，一个是递归到底发掘。