左孩子右兄弟存储方式:
struct tree_node
{
int data;
tree_node* first_child;
tree_node* sibling;
}
一个观念必须要有: root没有兄弟sibling,根是独立的,代表这一棵树---------忘记了绝不会写递归了。
(A) 深度遍历:
(1)递归算法:
先根遍历 void preOrder(tree_node * root)
{
if (!root)
return;
printf(root->data);
tree_node* p;
for(p=root->first_child;p,p=p->sibling)
{
preOrder(p);
}
}
后根遍历 void postOrder(tree_node * root)
{
if (!root)
return;
tree_node* p;
for(p=root->first_child;p,p=p->sibling)
{
preOrder(p);
}
printf(root->data);
}
(2)非递归算法:
记忆技巧是将节点看成是二叉树,因为树对应的二叉树的
先序与树的先根遍历序列是一致的,这是公认的事实。
先根遍历 void preOrder(tree_node* root)
{
stack sk;
while(root || !sk.empty())
{
while(root)
{
printf(root->data);
sk.push(root);
root=root->first_child;
}
root=sk.top(); sk.pop();//STL要求这样做的
root=root->sibling; //root可以为空的
}
}
记忆技巧是将节点看成是二叉树,因为树对应的二叉树的
中序与树的后根遍历序列是一致的,这是公认的事实。
后根遍历 void postOrder(tree_node* root)
{
stack sk;
while(root || !sk.empty())
{
while(root)
{
sk.push(root);
root=root->first_child;
}
root=sk.top();sk.pop();//STL要求这样做的
printf(root->data);
root=root->sibling;//root可以为空的
}
}
(B)广度遍历(按层次次序遍历树的算法)
用队列实现
void levelOrde(tree_node* root)
{
queue q;
q.push(root);
while(!q.empty())
{
root=q.font();q.pop();
printf(root->data);
root=root->first_child;
while(!root)
{
q.push(root);
root=root->sibling;
}
}
}
阅读(8071) | 评论(0) | 转发(0) |