首页 > 代码库 > 编程之美——二叉树层次遍历
编程之美——二叉树层次遍历
方法一：从根节点开始，将每层节点压入一个数组，cur代表当前访问节点，last代表下一层第一个节点，遍历数组可得层次遍历；
代码：
1 #include<iostream> 2 #include<queue> 3 #include<vector> 4 using namespace std; 5 6 template<class T> 7 class binaryTree 8 { 9 struct node 10 { 11 T elem; 12 node *left; 13 node *right; 14 15 node(const T &x,node *lt=NULL,node *rt=NULL) 16 :elem(x),left(lt),right(rt){} 17 ~node(){} 18 }; 19 20 private: 21 node *root; 22 void makeEmpty(node *&t); 23 void levelTraverse(node *&t); 24 public: 25 binaryTree(node *t=NULL) 26 { 27 root=t; 28 } 29 void createBinaryTree(); 30 void levelTraverse() 31 { 32 levelTraverse(root); 33 } 34 ~binaryTree() 35 { 36 makeEmpty(root); 37 } 38 }; 39 40 //使用队列构造一个二叉查找树 41 template<class T> 42 void binaryTree<T>::createBinaryTree() 43 { 44 queue<node *>que; 45 node *t; 46 T value; 47 48 cout<<"enter root:(-1 represent NULL)"<<":"; 49 cin>>value; 50 51 root=new node(value); 52 que.push(root); 53 54 T ldata,rdata; 55 56 while(!que.empty()) 57 { 58 t=que.front(); 59 que.pop(); 60 61 cout<<"enter left son of the node "<<t->elem<<":"; 62 cin>>ldata; 63 cout<<"enter right son of the node "<<t->elem<<":"; 64 cin>>rdata; 65 66 if(ldata!=-1) 67 que.push(t->left=new node(ldata)); 68 if(rdata!=-1) 69 que.push(t->right=new node(rdata)); 70 } 71 cout<<"construct complement!"<<endl; 72 } 73 74 template<class T> 75 void binaryTree<T>::makeEmpty(node *&t) 76 { 77 if(t->left!=NULL) 78 makeEmpty(t->left); 79 if(t->right!=NULL) 80 makeEmpty(t->right); 81 delete t; 82 } 83 84 template<class T> 85 void binaryTree<T>::levelTraverse(node *&t) 86 { 87 if(t==NULL) 88 return; 89 90 vector<node *>arr; 91 int cur=0; 92 int last=1; 93 94 arr.push_back(t); 95 while(cur<last) 96 { 97 while(cur<last) 98 { 99 cout<<arr[cur]->elem<<‘\t‘;100 if(arr[cur]->left!=NULL)101 arr.push_back(arr[cur]->left);102 if(arr[cur]->right!=NULL)103 arr.push_back(arr[cur]->right);104 ++cur;105 }106 107 last=arr.size();108 cout<<endl;109 }110 }111 112 int main()113 {114 binaryTree<int>tree;115 tree.createBinaryTree();116 tree.levelTraverse();117 return 0;118 }
方法二：本问题可是使用队列数据结构直接解决：
1 template<class T> 2 void binaryTree<T>::levelTraverse(node *&t) 3 { 4 queue<node *>que; 5 que.push(t); 6 while(!que.empty()) 7 { 8 node *q=que.front(); 9 cout<<q->elem<<ends;10 if(q->left!=NULL)11 que.push(q->left);12 if(q->right!=NULL)13 que.push(q->right);14 que.pop();15 }16 }
但这种情况下不能清晰显示树的层次性，要求显示的各层之间有换行，则需修改；
我们可以设计一标记值，标记某一层已经遍历完毕，出对，入队，输出换行，然后开始新一轮的遍历；
1 template<class T> 2 void binaryTree<T>::levelTraverse(node *&t) 3 { 4 queue<node *>que; 5 node *sign; 6 //标记值 7 sign->elem=-1; 8 que.push(t); 9 que.push(sign);10 while(que.size()>1)11 {12 node *q=que.front();13 cout<<q->elem<<ends;14 if(q->left!=NULL)15 que.push(q->left);16 if(q->right!=NULL)17 que.push(q->right);18 que.pop();19 20 //若遇到标记值，出对，入队，输出换行，开始下一层遍历21 if(que.front()->elem==-1)22 {23 que.pop();24 que.push(sign);25 cout<<endl;26 }27 }28 }
若按深度从下到上遍历，可以将前面结果压入栈中，每层之间压入一标记值，最后将栈中元素pop即可；
编程之美——二叉树层次遍历
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。