题目:通过树的前序遍历和中序遍历来确定树的结构并输出,通过递归的方法
#include <iostream> //#include <boost\shared_ptr.hpp> using namespace std; struct NodeTree { int m_value; NodeTree *m_left; NodeTree *m_right; }; NodeTree* maketree(int *pre,int *mid,int length) { if (pre==nullptr||mid==nullptr||length<=0) { cout<<"input is error"<<endl; return nullptr; } NodeTree *root=new NodeTree(); //boost::shared_ptr<NodeTree> root(new NodeTree()); root->m_value=*pre; root->m_left=nullptr; root->m_right=nullptr; if (length==1) { if (*pre==*mid) { return root; } else { cout<<"error"<<endl; return nullptr; } } int *midbeg=mid; while (*midbeg!=root->m_value&&midbeg<mid+length) { ++midbeg; } if (midbeg==mid+length) { cout<<"error root"<<endl; return nullptr; } int rootlength=midbeg-mid; //构建左子树 if (rootlength>0) { root->m_left=maketree(pre+1,mid,rootlength); } //构建右子树 if (rootlength<length-1) { root->m_right=maketree(pre+rootlength+1,midbeg+1,length-1-rootlength); } return root; } void PrintTreeNode(NodeTree* pNode) { if(pNode != nullptr) { printf("value of this node is: %d\n", pNode->m_value); if(pNode->m_left != nullptr) printf("value of its left child is: %d.\n", pNode->m_left->m_value); else printf("left child is null.\n"); if(pNode->m_right != nullptr) printf("value of its right child is: %d.\n", pNode->m_right->m_value); else printf("right child is null.\n"); } else { printf("this node is null.\n"); } printf("\n"); } void PrintTree(NodeTree* pRoot) { PrintTreeNode(pRoot); if(pRoot != nullptr) { if(pRoot->m_left != nullptr) PrintTree(pRoot->m_left); if(pRoot->m_right != nullptr) PrintTree(pRoot->m_right); } } int main() { const int length = 5; int preorder[length] = {1, 2, 3, 4, 5}; int inorder[length] = {5, 4, 3, 2, 1}; NodeTree *root=nullptr; root=maketree(preorder,inorder,length); PrintTree(root); delete root; root=nullptr; return 0; }
解决