自定义二叉树类型
struct tree
{
char v; //记录节点内容
int node; //记录该节点在数组中的位置
tree *left,*right; //链表构建时的左右节点
bool have_value; //判断该节点是否存在数字
tree():have_value(0),left(NULL),right(NULL) {}; //构造函数
};
利用链表构造二叉树
tree* build()
{
tree*root = new tree;
root -> v = '1';
root -> left = new tree;
root -> left -> v = '2';
root -> right = new tree;
root -> right -> v = '3';
return root;
}
利用数组构造二叉树(数组需要开到二叉树的4倍大)
tree a[1000];
void build(int node,char v)
{
a[node].v = v;
}//构造node的左节点,node = 2 * node;
//构造node的右节点,node = 2 * node + 1;
二叉树的遍历
前序遍历
void dfs_front(tree *now) //前序遍历
{
if(!now) return;
cout << now -> v << " ";
dfs_middle(now -> left);
dfs_middle(now -> right);
}
中序遍历
void dfs_middle(tree *now) //中序遍历
{
if(!now) return;
dfs_middle(now -> left);
cout << now -> v << " ";
dfs_middle(now -> right);
}
后序遍历
void dfs_last(tree *now) //后序遍历
{
if(!now) return;
dfs_last(now -> left);
dfs_last(now -> right);
cout << now -> v << " ";
}
逐层遍历(BFS)
void bfs(int node)
{
queue<tree>q;
q.push(a[node]);
tree now;
while(!q.empty())
{
now = q.front();q.pop();
cout << now.v << endl;
if(a[now.node * 2].have_value)
{
q.push(a[now.node * 2]);
}
if(a[2 * now.node + 1].have_value)
{
q.push(a[now.node * 2 + 1]);
}
}
}