数据结构 二叉树的递归与非递归
发布时间:2020-12-15 05:14:48 所属栏目:安全 来源:网络整理
导读:数据结构 二叉树的递归与非递归 实例代码: #include iostream #include queue #include stack #include assert.h using namespace std; templateclass T struct BinaryTreeNode { BinaryTreeNodeT* _left; BinaryTreeNodeT* _right; T _data; BinaryTreeNod
数据结构 二叉树的递归与非递归 实例代码: #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,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,++index); root->_right = CreateTree(a,++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; } 感谢阅读,希望能帮助到大家,谢谢大家对本站的支持! (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |
相关内容
- twitter-bootstrap – 在Bootstrap 3.0中带缩略图的旋转木马
- bootstrap学习笔记-布局-基本
- twitter-bootstrap – Bootstrap 3样式编辑器
- 使用Jersey来创建RESTful WebService
- shell学习三十--综合应用
- ssh命令执行时不考虑.bashrc | .bash_login | .ssh/rc?
- unity3d 访问webservice到dataset
- 如何使用AngularJS动态更新.less文件中的变量
- angular – 使用md-slider选择范围
- bootstrapTable editable select empty