Chương trình C ++ để thực hiện truyền tải không đệ quy Inorder của một cây nhị phân cho trước

Nếu cây nhị phân được duyệt theo thứ tự, cây con bên trái được truy cập đầu tiên, sau đó đến cây gốc và sau đó là cây con bên phải. Đầu ra khóa theo thứ tự tăng dần trong in_order traversal. Đây là một chương trình C ++ cho Inorder Tree Traversal mà không cần đệ quy.

Thuật toán

Begin
   Declare a structure n.
      Declare d of the integer datatype.
      Declare a pointer l against structure n.
      Declare a pointer r against structure n.
      Declare a constructor of structure n.
         Pass an integer variable d to parameter.
         this->d = d
         l = r = NULL
   Declare inOrder(struct n *root) function.
      Declare a stack s.
      Declare a pointer current against structure n.
         Initialize n *current = root.
      while (current != NULL || s.empty() == false)
         while (current != NULL)
            s.push(current)
            current = current->l
         current = s.top()
         s.pop()
         print current->d.
         current = current->r.
   insert values in nodes of tree.
   Call inOrder(root) function to travern the tree.
End.

Ví dụ

#include<bits/stdc++.h>
using namespace std;
struct n {
   int d;
   struct n* l;
   struct n* r;
   n (int d) {
      this->d = d;
      l = r = NULL;
   }
};
void inOrder(struct n *root) {
   stack<n *> s;
   n *current = root;
   while (current != NULL || s.empty() == false) {
      while (current != NULL) {
         s.push(current);
         current = current->l;
      }
      current = s.top();
      s.pop();
      cout << current->d << " ";
      current = current->r;
   }
}
int main() {
   struct n* root = new n(6);
   root->l = new n(4);
   root->r= new n(7);
   root->l->l = new n(8);
   root->l->r= new n(5);
   root->r->l = new n(9);
   root->r->r = new n(10);
   inOrder(root);
   return 0;
}

Đầu ra

8 4 5 6 9 7 10