好贷网好贷款

二叉树系列(3)层序遍历的非递归实现

发布时间:2016-12-3 12:42:40 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"二叉树系列(3)层序遍历的非递归实现",主要涉及到二叉树系列(3)层序遍历的非递归实现方面的内容,对于二叉树系列(3)层序遍历的非递归实现感兴趣的同学可以参考一下。

按照层次序实现二叉树遍历。 对于上图中的二叉树,层次遍历的实现结果如下 层次遍历的过程天然地符合队列这个数据结构,因此可以用队列方法来非递归地实现层次遍历。目前还不太清楚如何递归地实现层次遍历,网上看到的一些解法,声称采用了递归方法进行层次遍历,但是它们是在while循环中进行的递归,是一种伪递归。由此有可以猜测,可能这种遍历表现出来的数据访问方式确实不匹配递归的算法。下面仅仅给出层次遍历的非递归解法。 void level_order_2(link t, void (*visit)(link)) { if(!t) return; std::queue<struct node> que; que.push(*t); while(!que.empty()){ struct node node_p; node_p = que.front(); que.pop(); visit(&node_p); if(node_p.l!=NULL) que.push(*node_p.l); if(node_p.r!=NULL) que.push(*node_p.r); } return; } 下面是完整的文件,主要实现了二叉树的前序,中序,后序,层序的遍历。有bintree.h,bintree.cpp,main.cpp 以下为bintree.h #ifndef BINTREE_H #define BINTREE_H typedef struct node* link; struct node{ int item; link l,r; }; struct tag_node{ link node_link; bool is_first; }; link init(int VLR[],int LVR[],int n); void pre_order(link t, void (*visit)(link));//递归前续遍历 void pre_order_2(link t, void (*visit)(link));//非递归前续遍历 void in_order(link t, void (*visit)(link));//递归中续遍历 void in_order_2(link t, void (*visit)(link));//非递归中续遍历 void post_order(link t, void (*visit)(link));//递归后续遍历 void post_order_2(link t, void (*visit)(link));//非递归后续遍历第一种 void post_order_3(link t, void (*visit)(link)); //非递归后续遍历第二种 void level_order(link t, int level, void (*visit)(link));//层序遍历递归, void level_order_2(link t, void (*visit)(link));//层序遍历非递归 int count(link t); int depth(link t); int count_leaf(link t); int count_non_leaf(link t); link mirror_tree(link parent_t,link copy_t, int is_left); void destroy(link t); #endif 以下为bintree.cpp #include <stdlib.h> #include <stack> #include <queue> #include "bintree.h" static link make_node(int item) { link p = new node; p->item = item; p->l = p->r = NULL; return p; } static void free_node(link p) { free(p); } link init(int VLR[], int LVR[], int n) { link t; int k; if(n <= 0) return NULL; for (k =0; VLR[0] != LVR[k];k++); //注意这里分号的位置 t = make_node(VLR[0]); t->l = init(VLR+1, LVR,k); t->r = init(VLR+1+k, LVR+1+k,n-k-1); return t; } //前序递归 void pre_order(link t, void (*visit)(link)) { if(!t) return; visit(t); pre_order(t->l, visit); pre_order(t->r, visit); } //前序非递归 void pre_order_2(link t, void (*visit)(link)) { if(t==NULL) return; std::stack<link> s; link p = t; s.push(p); while(!s.empty()) { p = s.top(); s.pop(); visit(p); if(p->r != NULL) s.push(p->r); if(p->l != NULL) s.push(p->l); } } //中序递归 void in_order(link t, void (*visit)(link)) { if(!t) return; in_order(t->l, visit); visit(t); in_order(t->r, visit); } //中序非递归 void in_order_2(link t, void (*visit)(link)) { std::stack<link> s; link p=t; while( p!=NULL || !s.empty())// p!=NULL这个条件是为了兼容第1次循环的条件设置。 { while(p!=NULL) { s.push(p); p=p->l; } //找到当前节点的最深最深最深的左儿子 if(!s.empty()) { p=s.top(); visit(p); s.pop(); p=p->r; } } } //后序递归 void post_order(link t, void (*visit)(link)) { if(!t) return; post_order(t->l, visit); post_order(t->r, visit); visit(t); } //后序非递归第一种 void post_order_2(link t, void (*visit)(link)) { std::stack<link> s; link cur=NULL; //当前结点 link pre=NULL; //前一次访问的结点 s.push(t); while(!s.empty()) { cur=s.top(); if( (cur->l==NULL&&cur->r==NULL) || ( (pre!=NULL) && (pre==cur->l || pre==cur->r ) ) ) { visit(cur); //如果当前结点没有孩子结点或者孩子节点都已被访问过 s.pop(); pre=cur; } else { if(cur->r!=NULL) s.push(cur->r); if(cur->l!=NULL) s.push(cur->l); } } return; } //后序非递归第二种 void post_order_3(link t, void (*visit)(link)) { std::stack<tag_node*> s; link p=t; tag_node *temp; while(p!=NULL||!s.empty()) { while(p!=NULL) { tag_node* t_node=(tag_node*)malloc(sizeof(tag_node)); t_node->node_link=p; t_node->is_first=true; s.push(t_node); p=p->l; } if(!s.empty()) { temp=s.top(); s.pop(); if(temp->is_first==true) //表示是第一次出现在栈顶 { temp->is_first=false; s.push(temp); p=temp->node_link->r; } else //第二次出现在栈顶 { visit(temp->node_link); free(temp); p=NULL; //避免下一次循环的时候重复找P的最深左子节点 } } } return; } //层序递归 void level_order(link t, int level, void (*visit)(link)) { return; } //层序非递归 void level_order_2(link t, void (*visit)(link)) { if(!t) return; std::queue<struct node> que; que.push(*t); while(!que.empty()){ struct node node_p; node_p = que.front(); que.pop(); visit(&node_p); if(node_p.l!=NULL) que.push(*node_p.l); if(node_p.r!=NULL) que.push(*node_p.r); } return; } int count(link t) { if(!t) return 0; return 1 + count(t->l) + count(t->r); } int depth(link t) { int dl,dr; if(!t) return 0; dl=depth(t->l); dr=depth(t->r); return 1+ (dr>dl?dr:dl); } int count_leaf(link t) { if(!t) return 0; if( (t->l==NULL) && (t->r==NULL) ) return 1; return count_leaf(t->r)+count_leaf(t->l); } int count_non_leaf(link t) { if(!t) return 0; if( (t->l==NULL) && (t->r==NULL) ) return 0; return 1+count_non_leaf(t->l)+count_non_leaf(t->r); } link mirror_tree(link parent_t,link copy_t, int is_left) { if(!copy_t) return NULL; link new_root=make_node(copy_t->item); if(parent_t!=NULL&&is_left==1)//first_time==1 parent_t->l=new_root; if(parent_t!=NULL&&is_left==0) parent_t->r=new_root; mirror_tree(new_root, copy_t->r, 1); mirror_tree(new_root, copy_t->l, 0); return new_root; } void destroy(link t) { post_order(t,free_node); //post_order的第一个参数是函数指针,所以post_order(t,vist),post_order(t,free_node)都参数合理 } 以下为main.cpp // tree_traverse_1.cpp : Defines the entry point for the console application. // #include <stdio.h> #include "bintree.h" void print_item(link p) { printf("%d ",p->item); } int main(int argc, char* argv[]) { //test_data_1 //int pre_seq[] = {4,2,1,3,6,5,7}; //int in_seq[] = {1,2,3,4,5,6,7}; //test_data_2 int pre_seq[] = {4,2,1,8,9,3,6,5,7}; int in_seq[] = {8,1,9,2,3,4,5,6,7}; //test_data_3 //int pre_seq[] = {4,2,1,3,6,5,8,7,9}; //int in_seq[] = {1,2,3,4,8,5,6,7,9}; //link root = init(pre_seq,in_seq,7); link root = init(pre_seq,in_seq,9); printf("count=%d, depth=%d, leaf=%d, non_leaf=%d\n",count(root),depth(root),count_leaf(root),count_non_leaf(root)); putchar('\n'); putchar('\n'); pre_order(root, print_item); putchar('\n'); pre_order_2(root, print_item); putchar('\n'); in_order(root, print_item); putchar('\n'); in_order_2(root, print_item); putchar('\n'); post_order(root, print_item); putchar('\n'); post_order_2(root, print_item); putchar('\n'); post_order_3(root, print_item); putchar('\n'); putchar('\n'); level_order_2(root, print_item); putchar('\n'); putchar('\n'); link root2 = mirror_tree(NULL,root,-1); in_order(root2, print_item); putchar('\n'); putchar('\n'); destroy(root); destroy(root2); return 0; } 以下为main函数的运行结果

上一篇:(C++实现)——解释器模式(Interpreter Pattern)
下一篇:MATLAB颜色控制命令

相关文章

相关评论