输入某二叉树的前序遍历和中序遍历的结果,请重建该二叉树。
思路:根据前序遍历依次访问对应的中序遍历的节点,分为左子树和右子树创建。
#include<iostream>#include<stdlib.h>usingnamespacestd;structBinaryTreeNode{BinaryTreeNode(int_value):m_nValue(_value),m_pLeft(NULL),m_pRight(NULL){}intm_nValue;structBinaryTreeNode*m_pLeft;structBinaryTreeNode*m_pRight;};BinaryTreeNode*Buildtree(int*pre,int*mid,intn){if(n==0){returnNULL;}intnum=pre[0];BinaryTreeNode*head=newBinaryTreeNode(num);inti=0;while(i<n&&mid[i]!=num)//求左子树的长度{i++;}intleft_len=i;//左子树的长度intright_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);}returnhead;}voidPreOrder(BinaryTreeNode*head){if(head==NULL){return;}cout<<head->m_nValue<<"->";PreOrder(head->m_pLeft);PreOrder(head->m_pRight);}voidMidOrder(BinaryTreeNode*head){if(head==NULL){return;}MidOrder(head->m_pLeft);cout<<head->m_nValue<<"->";MidOrder(head->m_pRight);}intmain(){intpre[]={1,2,4,7,3,5,6,8};intmid[]={4,7,2,1,5,3,8,6};BinaryTreeNode*head=Buildtree(pre,mid,8);PreOrder(head);cout<<endl;MidOrder(head);system("pause");return0;}
声明:本站所有文章资源内容,如无特殊说明或标注,均为采集网络资源。如若本站内容侵犯了原著者的合法权益,可联系本站删除。