数据结构 二叉树的递归与非递归

实例代码：

#include <iostream> #include <queue> #include <stack> #include <assert.h> using namespace std; template<class T> struct BinaryTreeNode { BinaryTreeNode<T>* _left; BinaryTreeNode<T>* _right; T _data; BinaryTreeNode(const T& x) :_left(NULL) , _right(NULL) , _data(x) {} }; template <class T> class BinaryTree { typedef BinaryTreeNode<T> Node; public: BinaryTree() :_root(NULL) {} BinaryTree(T* a, size_t n, const T& invalid) { size_t index = 0; _root=CreateTree(a, n, invalid, index); } BinaryTree(const BinaryTree<T>& t) { _root = _Copy(t._root); } BinaryTree<T>& operator=( BinaryTree<T>& t) { swap(_root,t._root); return *this; } ~BinaryTree() { _DestroyTree(_root); } Node* CreateTree(const T* a, size_t n, const T& invalid, size_t& index) { assert(a); Node* root = NULL; if (index < n && a[index] != invalid) { root = new Node(a[index]); root->_left = CreateTree(a, n, invalid, ++index); root->_right = CreateTree(a, n, invalid, ++index); } return root; }

先序遍历(递归法)

void PrevOrder() { _PrevOrder(_root); cout << endl; } //先序遍历非递归 void PrevOrderNorR( ) { Node* cur = _root; stack< Node* >s; while (cur||!s.empty()) { while (cur) { cout << cur->_data << " "; s.push(cur); cur = cur->_left; } Node* top = s.top(); s.pop(); cur = top->_right; } cout << endl; }

后序遍历

void PostOrder() { _PostOrder(_root); cout << endl; } //后序遍历非递归 void PostOrderNorR() { Node* cur = _root; Node* prev = NULL; stack< Node* >s; while (cur || !s.empty()) { while (cur) { s.push(cur); cur = cur->_left; } Node* top = s.top(); if (NULL==top->_right && prev==top->_right) { cout << top->_data << " "; s.pop(); prev = top; } cur = top->_right; } cout << endl; } //中序遍历 void InOrder() { _InOrder(_root); cout << endl; } //中序遍历非递归 void InOrderNorR() { Node* cur = _root; stack< Node* >s; while (cur || !s.empty()) { while (cur) { s.push(cur); cur = cur->_left; } Node* top = s.top(); s.pop(); cout << top->_data << " "; cur = top->_right; } cout << endl; } //节点个数 size_t Size() { return _Size(_root); } //叶子节点个数 size_t LeafSize() { return _LeafSize(_root); } //树的深度 size_t Depth() { return _Depth(_root); } size_t GetKLevel(size_t k) { return _GetKLevel(_root,k); } // 查找 Node* Find(size_t x) { return _Find(_root,x); } //层序遍历 void LevelOrder() { queue<Node*> q; if (_root) { q.push(_root); } while (!q.empty()) { Node* front = q.front(); cout << front->_data << " "; q.pop(); if (front->_left) { q.push(front->_left); } if (front->_right) { q.push(front->_right); } } cout << endl; } protected: Node* _Copy(Node* root) { if (root==NULL) { return NULL; } Node* NewRoot = new Node(root->_data); NewRoot->_left = _Copy(root->_left); NewRoot->_right = _Copy(root->_right); return NewRoot; } void _DestroyTree(Node* root) { if (NULL==root) { return; } _DestroyTree(root->_left); _DestroyTree(root->_right); delete root; } void _PrevOrder(BinaryTreeNode<T>* root) { if (root) { cout << root->_data << " "; _PrevOrder(root->_left); _PrevOrder(root->_right); } } void _PostOrder(BinaryTreeNode<T>* root) { if (root) { _PostOrder(root->_left); _PostOrder(root->_right); cout << root->_data << " "; } } void _InOrder(BinaryTreeNode<T>* root) { if (root) { _InOrder(root->_left); cout << root->_data << " "; _InOrder(root->_right); } } int _Size(BinaryTreeNode<T>* root) { if (root==0) { return 0; } return _Size(root->_left) + _Size(root->_right) + 1; } int _LeafSize(BinaryTreeNode<T>* root) { if (root==NULL) { return 0; } else if (root->_left == NULL&&root->_right == NULL) { return 1; } return _LeafSize(root->_left) + _LeafSize(root->_right); } int _Depth(Node* root) { if (root==NULL) { return 0; } int left = _Depth(root->_left); int right = _Depth(root->_right); return left > right ? left + 1 : right + 1; } int _GetKLevel(Node* root, size_t k) { assert(k>0); if (root==NULL) { return 0; } else if (k==1) { return 1; } return _GetKLevel(root->_left, k - 1) + _GetKLevel(root->_right, k - 1); } Node* _Find(Node* root, const T& x) { if (root==NULL) { return NULL; } if (root->_data==x) { return root; } Node* ret = _Find(root->_left,x); if (ret != NULL) return ret; return _Find(root->_right, x); } private: BinaryTreeNode<T>* _root; }; void TestBinaryTree() { int array[10] = { 1, 2, 3, '#', '#', 4, '#', '#', 5, 6 }; BinaryTree<int> t1(array,sizeof(array)/sizeof(array[0]),'#'); BinaryTree<int>t2(t1); BinaryTree<int> t3; t3 = t2; t2.LevelOrder(); t3.LevelOrder(); t1.LevelOrder(); t1.PrevOrder(); t1.PrevOrderNorR(); t1.InOrder(); t1.InOrderNorR(); t1.PostOrder(); t1.PostOrderNorR(); cout << endl; cout << t1.Size() << endl; cout << t1.LeafSize() << endl; cout << t1.Depth() << endl; cout << t1.GetKLevel(2) << endl; cout << t1.Find(2) << endl; }

感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！