2022年非递归遍历二叉树 .pdf

《2022年非递归遍历二叉树 .pdf》由会员分享，可在线阅读，更多相关《2022年非递归遍历二叉树 .pdf（9页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、遍历二叉树的递归算法与非递归算法分类： C/C+ 2009-03-08 17:26 6752人阅读 评论 (3) 收藏 举报遍历二叉树的递归算法与非递归算法先来看下面这棵二叉树。 如图 1。现在我们要对它进行先序遍历。递归思想：就是把这个大树拆分成N 棵小树，每棵小树都进行一次先序遍历。再把这些遍历连合起来就是这棵树的先序遍历了。同理中序遍历和后序遍历也是一样的方法。下面举例说明先序递归算法：令先序遍历的结果等于S；图 1对于图 2 这棵小树的先序遍历是： 1 2 3S = 123图 2名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - -

2、 - 名师精心整理 - - - - - - - 第 1 页，共 9 页 - - - - - - - - - 但以 2 为根节点又有一棵小树，这棵小树的先序遍历是：2 4 5S = 12453图 3以 3 为根节点又有一棵小树，这棵小树的先序遍历是：3 6 7S = 1245367图 4以 6 为根节点又有一棵小树，这个小树的先序遍历是：6 7 S =1 2453687图 5名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 9 页 - - - - - - - - - 以 7

3、为跟节点又有一棵小树，这棵小树的先序遍历是：7 9S = 1 2453687 9图 6这样就得出了这棵大树的最终先序遍历结果了：S = 1 2453687 9。再来看看这个变化过程：S = 123S = 12453S = 1245367S =1 2453687S = 1 2453687 9对于二叉树的非递归算法，则是需要应用一种重要的数据结构栈。用栈来存放准备需要访问的节点。例如先序遍历的非递归算法则是：指针 p 指向根节点；while （p 不为 NULL 或栈不空）反复访问当前节点 *p，指针 p 进栈、再将指针左移，直至最左下节点；当栈不空时，出栈，取出栈顶指针且右移（返回上面操作，去遍

4、历右子树）；下面是二叉树递归与非递归算法的C 语言实现实例：/tree.h#ifndef _TREE_H_#define _TREE_H_名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 9 页 - - - - - - - - - typedefstruct _node struct_node * left_child;struct_node *right_child;ctype_tdata; node , * tree; /二叉树节点结构/一种简单创建树的办法，供测试使用

5、void create_tree (tree *root, constctype_telems, csize_t *current_index, constcsize_t max_size );/不考虑二叉树的销毁了/二叉树先序遍历递归算法void preorder_recursion (treeroot);/二叉树先序遍历递非归算法void preorder_nonrecursive (treeroot);/二叉树中序遍历递归算法void inorder_recursion(treeroot);/二叉树中序遍历递非归算法void inorder_nonrecursive (treeroot)

6、;/二叉树后序遍历递归算法void postorder_recursion (treeroot);/二叉树后序遍历递非归算法void postorder_nonrecursive (treeroot);#endif /_TREE_H_/tree.c#include tree.h名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 9 页 - - - - - - - - - void create_tree (tree *root, constctype_telems, csiz

7、e_t *current_index, constcsize_t max_size )if (* current_index data = t;create_tree (&(* root)-left_child, elems, current_index, max_size );create_tree (&(* root)-right_child, elems , current_index, max_size ); void preorder_recursion (treeroot)if (NULL != root) printf(%d/t, root-data); /根preorder_r

8、ecursion (root-left_child); /左子树preorder_recursion (root-right_child); /右子树 void preorder_nonrecursive (treeroot)treestack100;int top = 0;名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 9 页 - - - - - - - - - treep=root;while (NULL != p | top 0) while (NULL != p)

9、 printf(%d/t, p-data);stacktop+ = p;p=p-left_child; p = stack-top;p = p-right_child; void inorder_recursion(treeroot)if (NULL != root) inorder_recursion (root-left_child); /左子树printf(%d/t, root-data); /根inorder_recursion (root-right_child); /右子树 void inorder_nonrecursive (treeroot)treestack100;int t

10、op = 0;treep = root;while (NULL != p | top 0) while (NULL != p) stacktop+ = p;p = p-left_child;名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 9 页 - - - - - - - - - p = stack-top;printf(%d/t, p-data);p = p-right_child; void postorder_recursion (treeroot)if (NULL

11、 != root) postorder_recursion (root-left_child);postorder_recursion (root-right_child);printf(%d/t, root-data); void postorder_nonrecursive (treeroot)treestack100;int top=0;treep = root;treelastvist = NULL ;while (NULL != p | top 0) while (NULL != p) stacktop+ = p;p = p-left_child; p = stacktop-1;if

12、 (NULL = p-right_child | lastvist = p-right_child) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 9 页 - - - - - - - - - printf(%d/t, p-data); -top;lastvist = p;p = NULL ; else p = p-right_child; /main.c#include tree.hint main()ctype_telems = 1,2,4,0,0,5,0,0,3,6

13、,8,0,0,0,7,0,9,0,0,0,;csize_tcurrent_index = 0;treet=NULL ;create_tree (&t, elems, ¤t_index, sizeof(elems);printf(二叉树先序遍历递归算法/n);preorder_recursion (t);printf(/n);printf(二叉树先序遍历非递归算法/n);preorder_nonrecursive (t);printf(/n/n);printf(二叉树中序遍历递归算法/n);inorder_recursion(t);printf(/n);printf(二叉树中序遍历非

14、递归算法/n);inorder_nonrecursive (t);printf(/n/n);名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 9 页 - - - - - - - - - printf(二叉树后序遍历递归算法/n);postorder_recursion (t);printf(/n);printf(二叉树后序遍历非递归算法/n);postorder_nonrecursive (t);printf(/n);return0;名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 9 页 - - - - - - - - -