由二叉树的前序和中序如何得到二叉树的后序呢?-创新互联
由二叉树的前序和中序如何得到二叉树的后序呢?
专注于为中小企业提供成都做网站、成都网站制作服务,电脑端+手机端+微信端的三站合一,更高效的管理,为中小企业阿克陶免费做网站提供优质的服务。我们立足成都,凝聚了一批互联网行业人才,有力地推动了成百上千家企业的稳健成长,帮助中小企业通过网站建设实现规模扩充和转变。首先得明白什么是前序、中序、后序。
二叉树前序:遍历顺序为,根节点、左子树、右子树;中序:遍历顺序为,左子树、根节点、右子树;后序:遍历顺序为,左子树、右子树、根节点
可以发现,二叉树前序中的第一个节点为树的根节点root,然后找出root在中序里面的位置,就可以把前序和中序分别划分为左、右子树两个部分,然后递归调用即可。
#includeusing namespace std; template struct BinaryTreeNode { T _data; BinaryTreeNode* _left; BinaryTreeNode* _right; BinaryTreeNode(const T& x) :_data(x) , _left(NULL) , _right(NULL) {} }; template class BinaryTree { protected: BinaryTreeNode * _root; protected: void _PreOrder(BinaryTreeNode * root) { if (root != NULL) { cout << root->_data << " "; _PreOrder(root->_left); _PreOrder(root->_right); } return; } BinaryTreeNode * _CreateBinary(char* preOrder, char* inOrder, int length) { BinaryTreeNode * root = NULL; if (length == 0) return NULL; int tmp = *preOrder; int index = 0; while (index < length&&inOrder[index] != tmp) index++; if (index < length) { root = new BinaryTreeNode (tmp-'0'); root->_left = _CreateBinary(preOrder + 1, inOrder,index); root->_right = _CreateBinary(preOrder + index + 1, inOrder + index + 1, length - index - 1); } return root; } void _Clear(BinaryTreeNode * root) { if (root) { _Clear(root->_left); _Clear(root->_right); delete root; } } public: BinaryTree() :_root(NULL) {} ~BinaryTree() { _Clear(_root); _root = NULL; } void PreOrder() { _PreOrder(_root); cout << endl; } void CreateBinaryTree(char* preOrder, char* inOrder) { int length = strlen(preOrder); _root = _CreateBinary(preOrder, inOrder,length); } }; void Test1() { char* preOrder = "12473568"; char* inOrder = "47215386"; BinaryTree bt; bt.CreateBinaryTree(preOrder, inOrder); bt.PreOrder(); }
另外有需要云服务器可以了解下创新互联scvps.cn,海内外云服务器15元起步,三天无理由+7*72小时售后在线,公司持有idc许可证,提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案,具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势,专为企业上云打造定制,能够满足用户丰富、多元化的应用场景需求。
新闻名称:由二叉树的前序和中序如何得到二叉树的后序呢?-创新互联
本文地址:http://scyanting.com/article/dijgch.html