题目 二叉树中根结点到所有其他结点的路径及路径长度问题
[实验目的]
验证二叉树及其上的基本操作。
[实验内容及要求]
1、 定义二叉树类。
2、 实现如下功能:
① 根据老师输入的测试数据(整型)从无到有创建一棵二叉树Treel。
② 求根结点到二叉树中所有其他结点的路径及路径长度并打印输出。
3、 为便于观察程序的运行结果,设计的输出函数能在屏幕上以规范、直观的形
式输出计算结果。例如将路径输出成如下形式:1->2 -> 3 -> 4 -> 5
4、 为了增强程序的可读性,程序中要有适当的注释
函数部分:
typedef struct Binary_tree{ struct Binary_tree * left; int data; struct Binary_tree * right; }bt,*pbt; int str2int(string str){ int data_int=0; for(int i=0;i<str.length();i++) { data_int*=10; data_int+=(int(str[i])-48);//string 转 int } return data_int; } pbt create_Binary_tree(){ pbt p; string data; cout<<"please inupt data(if you want to stop,input *):"; cin>>data; if(data[0]=='*'){ p=NULL; return p; } else{ p=(pbt)malloc(sizeof(bt)); p->data=str2int(data); p->left=create_Binary_tree(); p->right=create_Binary_tree(); } return p; } void Preorder_traversal(pbt p){ if(p!=NULL){ cout<<p->data<<' '; Preorder_traversal(p->left); Preorder_traversal(p->right); } } void output_length(pbt p,int count,vector<int>data){ if(p!=NULL){ if(count!=0) { for(int i=0;i<count-1;i++) cout<<data[i]<<" -> "; cout<<data[count-1]; } if(count!=0) cout<<" -> "; cout<<p->data; cout<<" length: "<<count<<endl; data.push_back(p->data); output_length(p->left, count+1, data); output_length(p->right, count+1, data); } return; }
调用部分:
pbt head; vector<int>data; head=create_Binary_tree(); Preorder_traversal(head); cout<<endl; output_length(head, 0, data);