您好,登录后才能下订单哦!
密码登录
登录注册
点击 登录注册 即表示同意《亿速云用户服务条款》
思路:根据前序遍历依次访问对应的中序遍历的节点,分为左子树和右子树创建。
#include<iostream> #include<stdlib.h> using namespace std; struct BinaryTreeNode { BinaryTreeNode(int _value) :m_nValue(_value) ,m_pLeft(NULL) ,m_pRight(NULL) {} int m_nValue; struct BinaryTreeNode* m_pLeft; struct BinaryTreeNode* m_pRight; }; BinaryTreeNode* Buildtree(int* pre,int* mid,int n) { if(n==0) { return NULL; } int num=pre[0]; BinaryTreeNode* head=new BinaryTreeNode(num); int i=0; while(i<n&&mid[i]!=num) //求左子树的长度 { i++; } int left_len=i; //左子树的长度 int right_len=n-1-i; //右子树的长度 if(left_len>0) //构建左子树 { head->m_pLeft=Buildtree(&pre[1],&mid[0],left_len); } if(right_len>0) //构建右子树 { head->m_pRight=Buildtree(&pre[left_len+1],&mid[left_len+1],right_len); } return head; } void PreOrder(BinaryTreeNode* head) { if(head==NULL) { return; } cout<<head->m_nValue<<"->"; PreOrder(head->m_pLeft); PreOrder(head->m_pRight); } void MidOrder(BinaryTreeNode* head) { if(head==NULL) { return; } MidOrder(head->m_pLeft); cout<<head->m_nValue<<"->"; MidOrder(head->m_pRight); } int main() { int pre[]={1,2,4,7,3,5,6,8}; int mid[]={4,7,2,1,5,3,8,6}; BinaryTreeNode* head=Buildtree(pre,mid,8); PreOrder(head); cout<<endl; MidOrder(head); system("pause"); return 0; }
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。