这篇文章主要为大家展示了“编程语言中数据结构之二叉树递归与非递归的示例分析”,内容简而易懂,条理清晰,希望能够帮助大家解决疑惑,下面让小编带领大家一起研究并学习一下“编程语言中数据结构之二叉树递归与非递归的示例分析”这篇文章吧。
成都创新互联服务项目包括双塔网站建设、双塔网站制作、双塔网页制作以及双塔网络营销策划等。多年来,我们专注于互联网行业,利用自身积累的技术优势、行业经验、深度合作伙伴关系等,向广大中小型企业、政府机构等提供互联网行业的解决方案,双塔网站推广取得了明显的社会效益与经济效益。目前,我们服务的客户以成都为中心已经辐射到双塔省份的部分城市,未来相信会继续扩大服务区域并继续获得客户的支持与信任!数据结构 二叉树的递归与非递归
实例代码:
#include#include #include #include using namespace std; template struct BinaryTreeNode { BinaryTreeNode * _left; BinaryTreeNode * _right; T _data; BinaryTreeNode(const T& x) :_left(NULL) , _right(NULL) , _data(x) {} }; template class BinaryTree { typedef BinaryTreeNode 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) { _root = _Copy(t._root); } BinaryTree & operator=( BinaryTree & 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() { queueq; 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 * root) { if (root) { cout << root->_data << " "; _PrevOrder(root->_left); _PrevOrder(root->_right); } } void _PostOrder(BinaryTreeNode * root) { if (root) { _PostOrder(root->_left); _PostOrder(root->_right); cout << root->_data << " "; } } void _InOrder(BinaryTreeNode * root) { if (root) { _InOrder(root->_left); cout << root->_data << " "; _InOrder(root->_right); } } int _Size(BinaryTreeNode * root) { if (root==0) { return 0; } return _Size(root->_left) + _Size(root->_right) + 1; } int _LeafSize(BinaryTreeNode * 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 * _root; };
void TestBinaryTree() { int array[10] = { 1, 2, 3, '#', '#', 4, '#', '#', 5, 6 }; BinaryTreet1(array,sizeof(array)/sizeof(array[0]),'#'); BinaryTree t2(t1); BinaryTree 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; }
以上是“编程语言中数据结构之二叉树递归与非递归的示例分析”这篇文章的所有内容,感谢各位的阅读!相信大家都有了一定的了解,希望分享的内容对大家有所帮助,如果还想学习更多知识,欢迎关注创新互联行业资讯频道!