二叉树的构造及遍历

时间:2022-07-05 19:32:26

自定义二叉树类型

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]);
}
}
}