首页 > 代码库 > travel the binary tree by level 4 ( from down to top and from left to right every level )
travel the binary tree by level 4 ( from down to top and from left to right every level )
travel the binary tree by level 4 ( from down to top and from left to right every level )
个人信息:就读于燕大本科软件工程专业 目前大三;
本人博客:google搜索“cqs_2012”即可;
个人爱好:酷爱数据结构和算法,希望将来从事算法工作为人民作出自己的贡献;
博客内容:travel the binary tree by level 4 ( from down to top and from left to right every level )
博客时间:2014-5-3;
编程语言:C++ ;
编程坏境:Windows 7 专业版 x64;
编程工具:vs2008 32位编译器;
制图工具:office 2010 ppt;
硬件信息:7G-3 笔记本;
my words
problemto be or not to be.
travel the binary tree by level from down to top and from left to right every level, with classing them by level.
eg: the binary tree follows
travelling result follows:
my solution
travel the binary tree with queue from top to down
travel these nodes in queue with stack to get reversed order
visit nodes in every level in stack with stack again
algorithm follows
void _TravelByLevel(node * T) { queue<node *> Q; stack<node *> S; stack<node *> S2; cout<<"travel start"<<endl; if(T != NULL) { Q.push(T); Q.push(NULL); node * p; while(! Q.empty()) { // first action p = Q.front(); Q.pop(); //_Visit(p); S.push(p); // second action if(p->left != NULL) Q.push(p->left); if(p->right != NULL) Q.push(p->right); // third action if(Q.front() == NULL) { Q.pop(); if(Q.empty()) break; S.push(NULL); Q.push(NULL); //cout<<"level"<<endl; } } while(! S.empty()) { if(S.top() != NULL) { S2.push(S.top()); S.pop(); } else { while( ! S2.empty() ) { _Visit(S2.top()); S2.pop(); } S.pop(); if(! S.empty()) cout<<"level"<<endl; } } // visit root _Visit(S2.top()); } cout<<"travel over"<<endl; }
my code
test.cpp
#include<iostream> #include<queue> #include<stack> using namespace std; class node { public: int data ; node * left ; node * right ; node() { data = http://www.mamicode.com/0 ;>