首页 > 代码库 > travel the binary tree by level 5 ( from down to top and from left to right every level )
travel the binary tree by level 5 ( from down to top and from left to right every level )
travel the binary tree by level 5 ( from down to top and from left to right every level )
个人信息:就读于燕大本科软件工程专业 目前大三;
本人博客:google搜索“cqs_2012”即可;
个人爱好:酷爱数据结构和算法,希望将来从事算法工作为人民作出自己的贡献;
博客内容:travel the binary tree by level 5 ( from down to top and from left to right every level )
博客时间:2014-5-4;
编程语言:C++ ;
编程坏境:Windows 7 专业版 x64;
编程工具:vs2008 32位编译器;
制图工具:office 2010 ppt;
硬件信息:7G-3 笔记本;
my words
Money can be stolen, but not knowledge. Studying benefits me forever.
problem( from beauty of programming )
my solutiontravel the binary tree by level, and visit nodes form left to right every level.
make the function: int TravelByLevel(node * root, int level)
eg: the binary tree follows
the 2 level nodes: 3,7,12,15
first action: make tree stored with a two-dimensional table like following
then getting nodes of every level becomes very easy.
time cost O(n), n is the numbers node of the binary tree, and this algorithm is faster than that algorithm with queue and stack which I proposed yesterday.
function follows( we assume the binary tree is not so big, or new more space just ok)
int _TravelByLevel(node * T,int level) { cout<<"travel start level "<<level<<endl; // first action table * table_tree = new table[length]; queue<std::pair<node *,int>> Q; if(T != NULL) Q.push(std::make_pair(T,0)); // second action std::pair<node*,int> p; while(! Q.empty()) { // first action: 2.1 p = Q.front(); Q.pop(); ((table_tree[p.second]).list)[( (table_tree[p.second]).num)++] = p.first; // second action: 2.2 if((p.first)->left != NULL) Q.push(std::make_pair((p.first)->left,p.second+1)); if((p.first)->right != NULL) Q.push(std::make_pair((p.first)->right,p.second+1)); } // third action node * p1; if( level < length && table_tree[level].num > 0 ) { for(int j =0;j<(table_tree[level]).num;j++) { p1 = ((table_tree[level]).list)[j]; cout<<p1->data<<endl; } cout<<"travel over"<<endl; return 1; } cout<<"travel over"<<endl; return 0; }program run out:
my code
test.cpp
#include<iostream> #include<queue> #include<stack> using namespace std; const int length = 100; //const int Longlength = 10000; class node { public: int data ; node * left ; node * right ; node() { data = http://www.mamicode.com/0 ;>