第16題：
題目（微軟）：
輸入一顆二元樹，從上往下按層打印樹的每個結點，同一層中按照從左往右的順序打印。
例如輸入
8
/ \
6 10
/ \ / \
5 7 9 11
輸出8 6 10 5 7 9 11。
[cpp] view plaincopyprint?#include<iostream>
#include<iomanip>
using namespace std;
struct BTreeNode
{
int m_Value;
BTreeNode* m_pLeft;
BTreeNode* m_pRight;
};
template<typename T>
struct Node
{
T data;
Node *next;
};
template<typename T>
class Myqueue
{
public:
Myqueue():front(NULL),rear(NULL){}
~Myqueue()
{
// Node<T> * p;
while(!empty())
{
dequeue();
}
}
bool empty()
{
if(NULL==rear)
return true;
else
return false;
}
void enqueue(T t)
{
Node<T> *p=new Node<T>;
p->data=t;
p->next=NULL;
if(empty())
{
rear=front=p;
}
else
{
rear->next=p;
rear=p;
}
}
T dequeue()
{
T temp=front->data;
if(front==rear)
{
delete front;
rear=front=NULL;
}
else
{
Node<T> * p=front;
front=front->next;
delete p;
}
return temp;
}
private:
Node<T> *front;
Node<T> *rear;
};
void print(BTreeNode * t)
{
if(NULL==t)
return ;
Myqueue<BTreeNode *> MQ;
MQ.enqueue(t);
BTreeNode *TNode;
while(!MQ.empty())
{
TNode=MQ.dequeue();
cout<<TNode->m_Value<<" ";
if(TNode->m_pLeft!=NULL)
MQ.enqueue(TNode->m_pLeft);
if(TNode->m_pRight!=NULL)
MQ.enqueue(TNode->m_pRight);
}
}
int main()
{
system("pause");
return 0;
}
#include<iostream>
#include<iomanip>
using namespace std;
struct BTreeNode
{
int m_Value;
BTreeNode* m_pLeft;
BTreeNode* m_pRight;
};
template<typename T>
struct Node
{
T data;
Node *next;
};
template<typename T>
class Myqueue
{
public:
Myqueue():front(NULL),rear(NULL){}
~Myqueue()
{
// Node<T> * p;
while(!empty())
{
dequeue();
}
}
bool empty()
{
if(NULL==rear)
return true;
else
return false;
}
void enqueue(T t)
{
Node<T> *p=new Node<T>;
p->data=t;
p->next=NULL;
if(empty())
{
rear=front=p;
}
else
{
rear->next=p;
rear=p;
}
}
T dequeue()
{
T temp=front->data;
if(front==rear)
{
delete front;
rear=front=NULL;
}
else
{
Node<T> * p=front;
front=front->next;
delete p;
}
return temp;
}
private:
Node<T> *front;
Node<T> *rear;
};
void print(BTreeNode * t)
{
if(NULL==t)
return ;
Myqueue<BTreeNode *> MQ;
MQ.enqueue(t);
BTreeNode *TNode;
while(!MQ.empty())
{
TNode=MQ.dequeue();
cout<<TNode->m_Value<<" ";
if(TNode->m_pLeft!=NULL)
MQ.enqueue(TNode->m_pLeft);
if(TNode->m_pRight!=NULL)
MQ.enqueue(TNode->m_pRight);
}
}
int main()
{
system("pause");
return 0;
}
采用隊列，從上到下從左到右的逐一打印出樹中每個節點的值
