C++ 數據結構二叉樹（前序/中序/后序遞歸、非遞歸遍歷）

2020-01-26 13:59:45

字體：大中小

來源：轉載

供稿：網友

C++ 數據結構二叉樹（前序/中序/后序遞歸、非遞歸遍歷）

二叉樹的性質：

二叉樹是一棵特殊的樹，二叉樹每個節點最多有兩個孩子結點，分別稱為左孩子和右孩子。

例：

實例代碼：

#include <iostream> #include <Windows.h> #include <stack> using namespace std;  template <class T> struct BinaryTreeNode {  int _data;  BinaryTreeNode<T>* _left; //左孩子  BinaryTreeNode<T>* _right;  //右孩子  BinaryTreeNode(const T& data)   :_data(data)   , _left(NULL)   , _right(NULL)  {} };  template <class T> class BinaryTree {  typedef BinaryTreeNode<T> Node; public:  BinaryTree()   :_root(NULL)  {}   BinaryTree(T* arr, size_t n, const T& invalid=T())  {   size_t index = 0;   _root = _CreatTree(arr, n, invalid, index);  }   void PreOrderR()  //前序遍歷 遞歸  {   _PreOrderR(_root);  }   void PreOrder()  //前序遍歷 非遞歸  {   _PreOrder(_root);  }   void InOrderR() //中序遍歷 遞歸  {   _InOrderR(_root);  }   void InOrder()   //中序遍歷  非遞歸  {   _InOrder(_root);   }   void PostOrderR()  //后序遍歷 左 右 根  遞歸  {   _PostOrderR(_root);   }   void PostOrder()  //后序遍歷 左 右 根  非遞歸  {   _PostOrder(_root);   }   ~BinaryTree()  {}  protected:  //建樹 arr:建樹使用的數組 n：數組大小 invalid:非法值 index:當前下標  Node* _CreatTree(T* arr, size_t n, const T& invalid, size_t& index)  {   Node* root = NULL;   if (index < n && arr[index] != invalid)   {    root = new Node(arr[index]); //根節點    root->_left = _CreatTree(arr, n, invalid, ++index);    root->_right = _CreatTree(arr, n, invalid, ++index);   }   return root;   }   void _PreOrderR(Node* root)  //前序遍歷 遞歸  {   if (root == NULL)   {    return;   }   cout << root->_data << " ";   _PreOrderR(root->_left);   _PreOrderR(root->_right);  }   void _PreOrder(Node* root)  //前序遍歷 非遞歸  {   stack<Node*> tty;   while (root != NULL || !tty.empty())   {    if (root)    {     cout << root->_data << " ";     tty.push(root);     root = root->_left;    }    else    {     Node* temp = tty.top();     tty.pop();     root = temp->_right;    }   }  }   void _InOrderR(Node* root) //中序遍歷 遞歸  {   if (root == NULL)   {    return;   }   _InOrderR(root->_left);   cout << root->_data << " ";   _InOrderR(root->_right);  }   void _InOrder(Node* root) //中序遍歷 非遞歸  {   if (root == NULL)   {    return;   }   stack<Node*> tty;   while (root != NULL || !tty.empty())   {    while (root)    {     tty.push(root);     root = root->_left;    }    //此時出了循環走到了最左葉子節點    Node* temp = tty.top();    tty.pop();    cout << temp->_data << " ";    root = temp->_right;   }  }   void _PostOrderR(Node* root)  //后序遍歷 左 右 根  遞歸  {   if (root == NULL)   {    return;   }   _PostOrderR(root->_left);   _PostOrderR(root->_right);   cout << root->_data << " ";  }   void _PostOrder(Node* root)  //后序遍歷 左 右 根  非遞歸  {   if (root == NULL)   {    return;   }   stack<Node*> tty;   Node* PreNode = NULL; //上一個訪問的結點   tty.push(root);   while (!tty.empty())   {    Node* cur = tty.top();    //訪問的當前節點左右孩子均為空或者當前節點左右子樹均已經訪問過    if ((cur->_left == NULL && cur->_right == NULL) || ((PreNode != NULL) && (PreNode == cur->_left || PreNode == cur->_right)))    {     cout << cur->_data << " ";     tty.pop();     PreNode = cur;    }    else    {     if (cur->_right != NULL)     {      tty.push(cur->_right);     }     if (cur->_left != NULL)     {      tty.push(cur->_left);     }    }   }  }  protected:  Node* _root; };

#include "源.h"  void Test() {  int array[10] = { 1, 2, 3, '#', '#', 4, '#', '#', 5, 6 };  BinaryTree<int> p(array, sizeof(array) / sizeof(array[0]), '#');  cout << "前序遞歸遍歷： " << "";  p.PreOrderR();  cout << endl;   cout << "前序非遞歸遍歷： " << "";  p.PreOrder();  cout << endl;   cout << "中序遞歸遍歷： " << "";  p.InOrderR();  cout << endl;   cout << "中序非遞歸遍歷： " << "";  p.InOrder();  cout << endl;   cout << "后序遞歸遍歷： " << "";  p.PostOrderR();  cout << endl;   cout << "后序非遞歸遍歷： " << "";  p.PostOrder();  cout << endl; }  int main() {  Test();  system("pause");  return 0; }

實現效果：