大佬教程收集整理的这篇文章主要介绍了【数据结构】前序遍历和中序遍历确定二叉树,大佬教程大佬觉得挺不错的,现在分享给大家,也给大家做个参考。
已知一个二叉树,我们可以得到它的前序遍历,中序遍历和后续遍历。那么,我们已知前序和中序的遍历结果,怎样还原二叉树呢?
假设前序遍历结果为:abdcef,中序遍历结果为dbaecf。
前序遍历:根结点+左子树+右子树
中序遍历:左子树+根结点+右子树
由此,我们可以得知,前序结果第一个字母a为根结点,在中序遍历结果中找到a,a的左侧d,b为a的左子树,a的右侧e,c,f为a的右子树;前序结果第二个字母b为a的左孩子,在中序遍历结果中找到b,b的左侧d为b的左子树,右子树为空;以此类推,利用递归,最终可以得到二叉树。
#include <iostream> using namespace std; #include <String> template <class T> struct TreeNode { TreeNode(const T& data) : _data(data),_pLeft(NULL),_pRight(NULL) {} T _data; TreeNode<T> *_pLeft; TreeNode<T> *_pRight; }; template <class T> class BinTree { typedef TreeNode<T> Node; public: BinTree() : _pRoot(NULL) {} Node* ReBuildTree(char* preorder,char* inorder) { size_t size = strlen(inorder); return _ReBuildTree(_pRoot,preorder,inorder,inorder + size - 1); } void PostOrder() { cout << "后序遍历结果:"; _PostOrder(_pRoot); cout << endl; } private: Node* _ReBuildTree(Node*& pRoot,char*& preorder,char* inbegin,char* inend) { if (inbegin>inend || *preorder == '\0') return NULL; pRoot = new Node(*preorder); char* cur = inbegin; for (cur = inbegin; cur <= inend; cur++) { if (*cur == *preorder) { if (inbegin <= cur - 1) _ReBuildTree(pRoot->_pLeft,++preorder,inbegin,cur - 1); if (cur + 1 <= inend) _ReBuildTree(pRoot->_pRight,cur + 1,inend); } } return pRoot; } void _PostOrder(const Node* pRoot) { if (pRoot) { _PostOrder(pRoot->_pLeft); _PostOrder(pRoot->_pRight); cout << pRoot->_data << " "; } } private: Node* _pRoot; };
以上是大佬教程为你收集整理的【数据结构】前序遍历和中序遍历确定二叉树全部内容,希望文章能够帮你解决【数据结构】前序遍历和中序遍历确定二叉树所遇到的程序开发问题。
如果觉得大佬教程网站内容还不错,欢迎将大佬教程推荐给程序员好友。
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。