baidu_32703855 2015-11-10 05:30
浏览 1382

根据二叉树的先序中序重构二叉树的算法问题

代码编译没有问题,就是输出结果不对
这是我的代码
#include
#include
using namespace std;

class TreeNode
{
private:
int data;
public:
TreeNode* LeftChild;
TreeNode* RightChild;
TreeNode():data(0),LeftChild(NULL),RightChild(NULL)
{

}
TreeNode(int& record):LeftChild(NULL),RightChild(NULL)
{
    data = record;
}
int Data()
{
    return data;
}

};

TreeNode* Rebuild(vector& preorder,int preleft,int preright,vector& inorder,int inleft,int inright)
{
if(preorder.size()!=inorder.size())
{
return NULL;
}
TreeNode* root = new TreeNode(preorder[preleft]);
root->LeftChild = NULL;
root->RightChild = NULL;
int i;

for(i=inleft; i<=inright; i++)
{
    if(inorder[i] == preorder[preleft]);
    break;
}
if(i>inright)
{
    return NULL;
}
int leftcount = i - inleft;
int rightcount = inright-i;
if(leftcount>0)
{
    root->LeftChild = Rebuild(preorder,preleft+1,preleft+leftcount,inorder,inleft,i-1);
}

if(rightcount>0)
{
    root->RightChild = Rebuild(preorder,preright-rightcount+1,preright,inorder,i+1,inright);
}

return root;

}
void PreOrderTraverse(TreeNode* root)
{
if(root!=NULL)
{
cout << root->Data() << " ";
if(root->LeftChild!=NULL)
{
PreOrderTraverse(root->LeftChild);
}
if(root->RightChild!=NULL)
{
PreOrderTraverse(root->RightChild);
}
}
}

void PostOrderTraverse(TreeNode* root)
{

if(root->LeftChild!=NULL)
{
    PostOrderTraverse(root->LeftChild);
}
if(root->RightChild!=NULL)
{
    PostOrderTraverse(root->RightChild);
}
cout << root->Data() << " ";

}
void InOrderTraverse(TreeNode* root)
{
if(root!=NULL)
{
if(root->LeftChild!=NULL)
{
InOrderTraverse(root->LeftChild);
}
cout << root->Data() << " ";
if(root->RightChild!=NULL)
{
InOrderTraverse(root->RightChild);
}
}
}

int main()
{
int n;
cin >> n;
vector preorder(n);

for(int i=0; i<n; i++)
{
    int data;
    cin >> data;
    preorder[i] = data;
}
vector<int> inorder(n);
for(int i=0; i<n; i++)
{
    int data;
    cin >> data;
    inorder[i] = data;
}
TreeNode* root = Rebuild(preorder,0,n-1,inorder,0,n-1);
InOrderTraverse(root);
cout << endl;
PreOrderTraverse(root);
cout << endl;
PostOrderTraverse(root);


return 0;

}
输入样例:
10

1 2 5 10 3 6 13 7 14 15
2 10 5 1 6 13 3 14 7 15

结果就是不对。。实在找不出来了,求大神知道

  • 写回答

0条回答 默认 最新

    报告相同问题?

    悬赏问题

    • ¥15 微信公众号自制会员卡没有收款渠道啊
    • ¥15 stable diffusion
    • ¥100 Jenkins自动化部署—悬赏100元
    • ¥15 关于#python#的问题:求帮写python代码
    • ¥20 MATLAB画图图形出现上下震荡的线条
    • ¥15 关于#windows#的问题:怎么用WIN 11系统的电脑 克隆WIN NT3.51-4.0系统的硬盘
    • ¥15 perl MISA分析p3_in脚本出错
    • ¥15 k8s部署jupyterlab,jupyterlab保存不了文件
    • ¥15 ubuntu虚拟机打包apk错误
    • ¥199 rust编程架构设计的方案 有偿