Cây Nhị Phân- Duyệt Sâu Và Duyệt Rộng

template<class entry>struct Binary_node
{
    entry data;
    Binary_node<entry> *left;
    Binary_node<entry> *right;
};
template<class Entry>class Binary_Tree
{
public:
    int sum_node;
    Binary_node<Entry> *root;

};

• Duyệt theo độ sâu
• Duyệt trước( Preorder traversal sequence)(NLR):F B A D C E G I H
• Duyệt giữa (Inorder traversal sequence)(LNR)   :A B C D E F G H I
• Duyệt sau(Postorder traversal sequence )(LRN):A C E D A H I G F
• Duyệt theo chiều rộng(Theo từng mức) 
• F B G A D I C E H
• Dùng Stack và Queue để khử đệ quy(Thật sự đây cũng là đệ quy , nhưng chúng ta điều khiển cách thức đệ quy để ngăn lại việc bị tràn bộ nhớ. Việc khử đệ quy thật sự là chúng ta chỉ dùng các vòng lập. Vì thât ra đệ quy ,bên dưới nó đả dùng stack để tạo nên việc gọi đệ quy)
•  Dùng Stack để xử lý duyệt trước
• void NLR(Binary_node<Entry> *node)
      {
          Binary_node<Entry> *p;
          stack<Binary_node<Entry> *> STK;
          STK.push(node);
          while(!STK.empty())
          {
              p=STK.top();
              printf("%d ", p->data);
              STK.pop();
              if(p->right!=NULL)
                  STK.push(p->right);
              if(p->left!=NULL)
                  STK.push(p->left);
          }
      }
• Dùng STack để xử lý duyệt giữa
• void LNR_KhongDeQuy(Binary_node<Entry> *node)
      {
          stack<Binary_node<Entry> *> STK;
          Binary_node<Entry> *p=node;   
          while(p||!STK.empty())
          {
              if(!p)
              {
                  p=STK.top();
                  STK.pop();
                  printf("%d ",p->data);
                  p=p->right;
              }
              else
              {
                  STK.push(p);
                  p=p->left;
              }
          }
• Dùng stack xử lý duyệt sau
• void LRN(Binary_node<Entry> *node)
      {
          stack<Binary_node<Entry> * >STK;
          Binary_node<Entry> *p=node;
          while(p ||!STK.empty())
          {
              if(!p)
              {
                  while(!STK.empty() && p==STK.top()->right)
                  {
                      p=STK.top();
                      STK.pop();
                      printf("%d ",p->data);
                      //STK.pop();
                  }
                  p=STK.empty() ?NULL:STK.top()->right;
              }
              else
              {
                  STK.push(p);
                  p=p->left;
              }
          }
• Dùng Queue để xử lý duyêt rộng
• void DuyetRong(Binary_node<Entry> *node)
      {
          queue<Binary_node<Entry>  * > Q;
          Binary_node<Entry> *tem;
          Q.push(node);
          while(!Q.empty())
          {
              tem=Q.front();
              cout<<tem->data<<" ";
              Q.pop();
              if(tem->left!=NULL)
                  Q.push(tem->left);
              if(tem->right!=NULL)
                  Q.push(tem->right);
          }
      }