js递归遍历树结构_二分搜索树（BST）的前/中/后序遍历-递归+非递归

#ifndef BST_H
#define BST_H
 
#include <iostream>
#include <stack>
#include <queue>
 
using namespace std;
 
template <typename T>
class bst
{
 private:
  struct node
  {
    T e;
    node* left;
    node* right;
    node() : e(), left(nullptr), right(nullptr) {}
    node(T e) : e(e), left(nullptr), right(nullptr) {}
    node(T e, node* left, node* right) : e(e), left(left), right(right) {}
  };
 
 public:
  bst()
  {
    root_ = nullptr;
    size_ = 0;
  }
 
  ~bst()
  {
    destroy_tree(root_);
  }
 
  void add(T e)
  {
    root_ = add(root_, e);
  }
 
  int get_size()
  {
    return size_;
  }
 
  void pre_order_traverse()
  {
    pre_order_traverse(root_);
    cout << endl;
  }
 
  void in_order_traverse()
  {
    in_order_traverse(root_);
    cout << endl;
  }
 
  void post_order_traverse()
  {
    post_order_traverse(root_);
    cout << endl;
  }
 
  // previous order traverse no recursion
  void pre_order_traverse_nr()
  {
    pre_order_traverse_nr(root_);
  }
 
  void in_order_traverse_nr()
  {
    in_order_traverse_nr(root_);
  }
 
  void post_order_traverse_nr()
  {
    post_order_traverse_nr(root_);
  }
 
  void level_order_traverse()
  {
    level_order_traverse(root_);
  }
 
 private:
  node* root_;
  int size_;
 
  void destroy_tree(node* root)
  {
    if (root == nullptr)
      return;
    destroy_tree(root->left);
    destroy_tree(root->right);
    cout << “delete: “ << root->e << endl;
    delete root;
    root = nullptr;
  }
 
  node* add(node* root, T e);
  void pre_order_traverse(node* root);
  void in_order_traverse(node* root);
  void post_order_traverse(node* root);
 
  // 非递归算法
  void pre_order_traverse_nr(node* root);
  void in_order_traverse_nr(node* root);
  void post_order_traverse_nr(node* root);
 
  void level_order_traverse(node* root);
};
 
template <typename T>
typename bst<T>::node* bst<T>::add(node* root, T e)
{
  if (root == nullptr)
  {
    size_++;
    return new node(e);
  }
  if (root->e > e)
    root->left = add(root->left, e);
  else if (root->e < e)
    root->right = add(root->right, e);
  else
    root->e = e;  // do nothing
  return root;
}
 
template <typename T>
void bst<T>::pre_order_traverse(node* root)
{
  if (root == nullptr)
    return;
  cout << root->e << “ “;
  pre_order_traverse(root->left);
  pre_order_traverse(root->right);
}
 
template <typename T>
void bst<T>::in_order_traverse(node* root)
{
  if (root == nullptr)
    return;
  in_order_traverse(root->left);
  cout << root->e << “ “;
  in_order_traverse(root->right);
}
 
template <typename T>
void bst<T>::post_order_traverse(node* root)
{
  if (root == nullptr)
    return;
  post_order_traverse(root->left);
  post_order_traverse(root->right);
  cout << root->e << " ";
}
 
template <typename T>
void bst<T>::pre_order_traverse_nr(node* root)
{
  if (root == nullptr)
    return;
  stack<node*> st;
  st.push(root);
  while (!st.empty())
  {
    node* curr = st.top();
    cout << curr->e << “ “;
    st.pop();
    if (curr->right != nullptr)
      st.push(curr->right);
    if (curr->left != nullptr)
      st.push(curr->left);
  }
  cout << endl;
}
 
template <typename T>
void bst<T>::in_order_traverse_nr(node* root)
{
  stack<node*> st;
  node* curr = root;
  while (curr != nullptr || !st.empty())
  {
    while (curr != nullptr)
    {
      st.push(curr);
      curr = curr->left;
    }
    if (!st.empty())
    {
      curr = st.top();
      cout << curr->e << “ “;
      st.pop();
      curr = curr->right;
    }
  }
  cout << endl;
}
 
template <typename T>
void bst<T>::post_order_traverse_nr(node* root)
{
  stack<node*> st;
  node* curr = root;
  node* visited = nullptr;
  while (curr != nullptr || !st.empty())
  {
    while (curr != nullptr)
    {
      st.push(curr);
      curr = curr->left;
    }
    if (!st.empty())
    {
      curr = st.top();
      if (curr->right == visited || curr->right == nullptr)
      {
        cout << curr->e << “ “;
        st.pop();
        visited = curr;
        curr = nullptr;
      }
      else
        curr = curr->right;
    }
  }
  cout << endl;
}
 
template <typename T>
void bst<T>::level_order_traverse(node* root)
{
  if (root == nullptr)
    return;
  queue<node*> q;
  q.push(root);
  while (!q.empty())
  {
    node* curr = q.front();
    q.pop();
    if (curr->left != nullptr)
      q.push(curr->left);
    if (curr->right != nullptr)
      q.push(curr->right);
    cout << curr->e << “ “;
 
  }
  cout << endl;
}
 
 
#endif // BST_H

#include “bst.h”
#include <cstdlib>
 
int main()
{
  bst<int>* my_bst = new bst<int>();
  srand(time(nullptr));
  my_bst->add(54);
  my_bst->add(32);
  my_bst->add(77);
  my_bst->add(18);
  my_bst->add(45);
  my_bst->add(66);
  my_bst->add(81);
 
  cout << “Pre-Order Traverse: “ << endl;
  my_bst->pre_order_traverse();
  my_bst->pre_order_traverse_nr();
  cout << endl;
 
  cout << “In-Order Traverse: “ << endl;
  my_bst->in_order_traverse();
  my_bst->in_order_traverse_nr();
  cout << endl;
 
  cout << “Post-Order Traverse: “ << endl;
  my_bst->post_order_traverse();
  my_bst->post_order_traverse_nr();
  cout << endl;
 
  cout << “Lever Order Traverse: “ << endl;
  my_bst->level_order_traverse();
  delete my_bst;
  return 0;
}