首页 诗词 字典 板报 句子 名言 友答 励志 学校 网站地图
当前位置: 首页 > 教程频道 > 开发语言 > Ruby Rails >

uva548 二叉树有关问题 Runtime Error看过来

2013-10-25 
uva548 二叉树问题 Runtime Error看过来!第一次练习二叉树的相关操作,还是很有收获,期间遇到了几个问题。1、

uva548 二叉树问题 Runtime Error看过来!

第一次练习二叉树的相关操作,还是很有收获,期间遇到了几个问题。

1、在delete节点时判断if(pNode==NULL)没用,不清楚为何,遂改了写法

2、全局变量写在类外时,类内的函数不能直接用,如果定义在类内是可以的,只不过在main函数中要加tree.引用

3、看网上的做法都是先建树,再dfs求路径最短,而我定义了一个sum域,保存根节点到该节点的路径和,如果判断该节点是叶子节点,则将sum与最小值Min比较,同时将节点加入vector中,进而可以求得路径和相同时哪个叶子节点的id最小。

4、注意动态数组申请及释放的写法,第一次就写错了!int* arr=new int【maxn】,delete【】arr;

5、runtime error就不知道该怎么改了。。。

#include<iostream>#include<cstring>#include<vector>using namespace std;struct Node{int id;int sum;Node* left;Node* right;};class Tree{public:Node* root;vector<Node*> nvec;int Min;Tree(){root=new Node;Min=10000;}void clear(Node* pNode);~Tree(){clear(root);}void build(Node* pNode,int n,int sum,int* s1,int* s2);//s1后序遍历,s2中序遍历void convert(int* arr,int len);int indexof(int* arr,int tar);};int Tree::indexof(int* arr,int tar){int i=0;while(1){if (arr[i]==tar){return i;}i++;}}void Tree::convert(int* arr,int len){for (int i=0;i<len/2;i++){int tmp=arr[i];arr[i]=arr[len-1-i];arr[len-1-i]=tmp;}}void Tree::clear(Node* pNode){if (pNode->id<0)delete pNode;else{clear(pNode->left);clear(pNode->right);}}void Tree::build(Node* pNode,int n,int sum,int* s1,int* s2){if (n<=0) {pNode=NULL;return;}pNode->id=s1[0];pNode->sum=sum+pNode->id;int p=indexof(s2,s1[0]);if (p<=0&&n-p-1<=0){nvec.push_back(pNode);if (pNode->sum<=Min){Min=pNode->sum;}}pNode->left= new Node;pNode->right= new Node;build(pNode->right,n-p-1,pNode->sum,s1+1,s2+p+1);build(pNode->left,p,pNode->sum,s1+n-p,s2);}#define MAXN 10001int main(){int tmp;while(cin>>tmp){int *inorder=new int[MAXN];int *postorder=new int[MAXN];inorder[0]=tmp;int dex=1;char ch=cin.get();while(ch==' '){cin>>inorder[dex++];ch=cin.get();}for (int i=0;i<dex;i++){cin>>postorder[i];}Tree tree;tree.convert(postorder,dex);tree.build(tree.root,dex,0,postorder,inorder);int* nodevalue=new int[MAXN];int index=0;for (int i=0;i<tree.nvec.size();i++){if (tree.nvec[i]->sum==tree.Min){nodevalue[index++]=tree.nvec[i]->id;}}int min=nodevalue[0];for (int j=0;j<index;j++){if (nodevalue[j]<min) min=nodevalue[j];}cout<<min<<endl;delete[] inorder;delete[] postorder;delete[] nodevalue;}return 0;}


热点排行