输入某二叉树的前序遍历和中序遍历的结果,请重建该二叉树。

发布时间:2020-08-21 20:32:42 作者:秋笙夏笛
来源:网络 阅读:335


思路:根据前序遍历依次访问对应的中序遍历的节点,分为左子树和右子树创建。

#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;
}


推荐阅读:
  1. 剑指offer:重建二叉树
  2. 前序遍历和中序遍历重建二叉树

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

重建树

上一篇:详解使用PM2管理nodejs进程

下一篇:PYTHON数据库之一(mysqlclient)

相关阅读

您好,登录后才能下订单哦!

密码登录
登录注册
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》