二叉树遍历非递归实现.doc二叉树遍历非递归实现.doc
【版权声明:转载请保留出处:blog.csdn.net/algorithm_only。邮箱:liuy0711@foxmail.com】 遍历是二叉树各种操作的基础，上一节给出的遍历算法是递归实现的，本节给出二叉树遍历的非递归实现，非递归实现需要使用前面讲到的数据结构——栈、队列来作为辅助空间。
, 先序遍历
[cpp] view plaincopy
1. int preorder_traverse(bitree bt, int (*visit)(elemtype e))
2....
二叉树遍历非递归实现.doc
【版权声明:转载请保留出处:blog.csdn.net/algorithm_only。邮箱:liuy0711@foxmail.com】 遍历是二叉树各种操作的基础，上一节给出的遍历算法是递归实现的，本节给出二叉树遍历的非递归实现，非递归实现需要使用前面讲到的数据结构——栈、队列来作为辅助空间。
, 先序遍历
[cpp] view plaincopy
1. int preorder_traverse(bitree bt, int (*visit)(elemtype e))
2. {
3. sqstack s;
4. bitree p;
5.
6. init_stack(&s);
7.
8. p = bt;
9. while (p || !is_stack_empty(s)) {
10. while (p) { /* 左结点依次进栈，向左走到尽
头 */
11. visit(p->data);
12. push_stack(&s, p);
13. p = p->lchild;
14. }
15. if (!is_stack_empty(s)) {
16. pop_stack(&s, &p); /* 出栈 */
17. p = p->rchild;
18. }
19. }
20. return OK;
21. }
根结点先进栈，访问结点值，左孩子依次进栈，直到最左的孩子进栈。然后栈顶指针出栈，退至上一层，然后访问右子树，右子树访问完成之后，退至上一层，直至栈空，节点访问完成。先序遍历访问结点值是在结点进栈时。理解此算法最好找一棵简单的树跟着程序走一遍，在纸上画出栈的进栈、出栈情况。
, 中序遍历
[cpp] view plaincopy
1. int inorder_traverse(bitree bt, int (*visit)(elemtype e))
2. {
3. sqstack s;
4. bitree p;
5.
6. init_stack(&s);
7.
8. p = bt;
9. while (p || !is_stack_empty(s)) { 10. while (p) {
11. push_stack(&s, p); 12. p = p->lchild; 13. }
14. if (!is_stack_empty(s)) { 15. pop_stack(&s, &p); 16. visit(p->data); 17. p = p->rchild; 18. }
19. }
20. return OK;
21. }
中序遍历和先序遍历类似，只是访问结点值是在出栈的时候，而先序遍历是在进栈的时候。
, 后序遍历
[cpp] view plaincopy
1. int postorder_traverse(bitree bt, int (*visit)(elemtype e))
2. {
3. sqstack s;
4. bitree p, q;
5.
6. init_stack(&s);
7.
8. p = bt;
9. q = NULL;
10. while (p || !is_stack_empty(s)) { 11. while (p) {
12. push_stack(&s, p); 13. p = p->lchild; 14. }
15. if (!is_stack_empty(s)) { 16. get_top(s, &p); /* 取栈顶元素 */ 17. if (!p->rchild || p->rchild == q) { /* 如果p没有右孩子，或右孩子已
经访问过 */
18. visit(p->data); 19. q = p;
20. p = NULL;
21. --s.top;/* 退栈 */
22. }
23. else
24. p = p->rchild; 25. }
26. }
27. return OK;
28. }
后序遍历和先序、中序类似，但要稍复杂一点，需要判断结点是否有右孩子和右孩子是否访
问过。
, 层次遍历
[cpp] view plaincopy
1. int levelorder_traverse(bitree bt, int (*visit)(elemtype e))
2. {
3. sqqueue sq;
4. bitree cur;
5.
6. init_queue(&sq);
7.
8. if (bt) {
9. in_queue(&sq, bt); 10. while (!is_queue_empty(sq)) { 11. out_queue(&sq, &cur); 12. visit(cur->data); 13.
14. if (cur->lchild)
15. in_queue(&sq, cur->lchild);
16. if (cur->rchild)
17. in_queue(&sq, cur->rchild);
18. }
19. }
20. return OK;
21. }
层次遍历算法比较好理解，使用队列作为辅助空间，根节点首先进队列，如果队列不为空的
话，访问结点值再出队列，然后左孩子进队列(如果有的话)，右孩子进队列(如果有的话)。
, 总结
遍历二叉树算法基本操作是访问结点，不论按哪一种次序进行遍历，对含n个结点的二叉
树时间复杂度都为O(n)
本文档为【二叉树遍历非递归实现.doc】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。
该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。
[版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
浙公网安备 33021202002483