树
树的遍历
前序遍历
1
2
3
4
5
6
7
8
9
| void Inorder(int rt)
{
if(nodeArray[rt].element()!='#')
{
Inorder(nodeArray[rt].left());
cout<<nodeArray[rt].element()<<" ";
Inorder(nodeArray[rt].right());
}
}
|
中序遍历
1
2
3
4
5
6
7
8
9
| void Inorder(int rt)
{
if(nodeArray[rt].element()!='#')
{
Inorder(nodeArray[rt].left());
cout<<nodeArray[rt].element()<<" ";
Inorder(nodeArray[rt].right());
}
}
|
后序遍历
1
2
3
4
5
6
7
8
9
| void postorder(int rt)
{
if(nodeArray[rt].element()!='#')
{
postorder(nodeArray[rt].left());
postorder(nodeArray[rt].right());
cout<<nodeArray[rt].element()<<" ";
}
}
|
层次遍历
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| void LevelOrderTraverse(int rt)
{
queue<int> q;
if(nodeArray[rt].element()!='#')
q.push(rt);
int temp;
while(!q.empty())
{
temp=q.front();
cout<<nodeArray[temp].element()<<" ";
q.pop();
int l=nodeArray[temp].left();
int r=nodeArray[temp].right();
if(nodeArray[l].element()!='#')
q.push(l);
if(nodeArray[r].element()!='#')
q.push(r);
}
}
|
层次遍历可以用队列来实现，先将根节点放入队列中，然后弹出，同时将子节点放入队列，这样一直循环一直到队列为空为止。
记得当时上人工智能的时候就用到了队列，好像是A*算法吧，虽然不是树的结构，是图的结构，但也大同小异。
