Advertisement
TShiva

wtf

Jan 12th, 2015
367
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 4.27 KB | None | 0 0
  1. #include<istream>
  2. #include<fstream>
  3. #include <string>  
  4. #include<iostream>
  5. #include <sstream>  
  6. using namespace std;
  7.  
  8.  
  9.  
  10. struct TreeElem
  11. {
  12.     double info; //info - Число, которое я буду записывать в дерево
  13.     TreeElem *left, *right; //Адресные поля. Адрес левой части и Адрес правой части
  14. };
  15.  
  16. void PrintTree(TreeElem *root) //Функция обхода
  17. {
  18.     if (root) //Пока не встретится пустое звено
  19.     {
  20.         cout << root->info << " "; //Отображаем корень дерева
  21.         PrintTree(root->left); //Рекурсивная функция для вывода левого поддерева
  22.         PrintTree(root->right); //Рекурсивная функци для вывода правого поддерева
  23.     }
  24. }
  25.  
  26. void AddElem(TreeElem *&root, int i) //Функция добавления звена в дерево
  27. {
  28.     if (!root)
  29.     {
  30.         root = new TreeElem; //Выделяем память под звено дерева
  31.         root->info = i; //Записываем данные в звено
  32.         root->left = root->right = 0; //Подзвенья инициализируем пустотой во избежание ошибок
  33.         return;
  34.     }
  35.     if (i<root->info) AddElem(root->left, i);
  36.     if (i>root->info) AddElem(root->right, i);
  37.     else return;
  38. }
  39.  
  40. void DelTree(TreeElem*& root){
  41.     if (!root)
  42.         return;
  43.     DelTree(root->left);
  44.     DelTree(root->right);
  45.     delete root;
  46.     root=0;
  47. }
  48.  
  49.  
  50. TreeElem* Make(istream& in, int curspaces, string& str){
  51.  
  52.  
  53.  
  54.     TreeElem* root = 0;
  55.     root = new TreeElem;
  56.  
  57.     std::stringstream ss;
  58.     ss << str;
  59.     ss >> root->info;
  60.  
  61.     root->left = 0;
  62.     root->right = 0;
  63.  
  64.     getline(in, str);
  65.     int count = 0;
  66.     char a = str[0];
  67.     for (int i = 0; i<str.length() && str[i] == ' '; ++i){
  68.         count++;
  69.     }
  70.  
  71.     if (count > curspaces){
  72.         root->left = Make(in, count, str);
  73.         int count2 = 0;
  74.         for (int i = 0; i<str.length() && str[i] == ' '; ++i){
  75.             count2++;
  76.         }
  77.         if (count2 > curspaces){
  78.             root->right = Make(in, count, str);
  79.  
  80.         }
  81.         return root;
  82.     }
  83.     else if (count == curspaces){
  84.         return root;
  85.     }
  86.     else {//count < spaces
  87.         return root;
  88.     }
  89.  
  90.  
  91. }
  92.  
  93.  
  94.  
  95. TreeElem* MakeTreeFromFile(string FileName){
  96.     ifstream name(FileName.c_str());
  97.     TreeElem* root = 0;
  98.  
  99.  
  100.     string str = "";
  101.     getline(name, str);
  102.     int count = 0;
  103.     for (int i = 0; i<str.length() && str[i] == ' '; ++i){
  104.         count++;
  105.     }
  106.     root = Make(name, count, str);
  107.     return root;
  108. }
  109.  
  110. int NodeCount(TreeElem * root)
  111. {
  112.     if (root->left == 0 && root->right == 0)
  113.         return 1;
  114.     int l, r;
  115.     if (root->left != 0)
  116.         l = NodeCount(root->left);
  117.     else
  118.         l = 0;
  119.     if (root->right != 0)
  120.         r = NodeCount(root->right);
  121.     else
  122.         r = 0;
  123.  
  124.     return l+r+1;
  125. }
  126.  
  127. int HeightOfTree(TreeElem * root)
  128. {
  129.     if(root == 0)
  130.         return 0;
  131.     int l, r;
  132.     if (root->left != 0) {
  133.         l = HeightOfTree(root->left);
  134.     }else
  135.         l = -1;
  136.     if (root->right != 0) {
  137.         r = HeightOfTree(root->right);
  138.     }else
  139.         r = -1;
  140.     int max = l > r ? l : r;
  141.     return max+1;
  142.  
  143. }
  144.  
  145.  
  146.  
  147. void PrintTreeLvl(TreeElem * root,int level){
  148.     if(root==0) return;
  149.     if (level == 1)
  150.     {
  151.         cout << root->info << " ";
  152.     }
  153.         PrintTreeLvl(root->left,level+ 1 );
  154.         PrintTreeLvl(root->right,level +1 );
  155.        
  156. }
  157. /*
  158. void PrintChain(TreeElem * root,int x){
  159.     if(!root) return 0;
  160.     if (root->info==x) return 1;
  161.       z;
  162. }*/
  163.  
  164.  
  165. int main(int argc, char** argv) {
  166.  
  167.     /*
  168.     char* FileName= "1.txt";
  169.  
  170.     TreeElem *Tree=0;
  171.  
  172.  
  173.     for (int i=0;i<5;i++) {AddElem(Tree,i);}
  174.  
  175.     PrintTree(Tree); //Вызов функции обхода дерева;
  176.     cin.get(); //Обычная задержка перед выходом;
  177.     */
  178.     string FileName = "1.txt";
  179.     TreeElem *Tree = 0;
  180.     Tree = MakeTreeFromFile(FileName);
  181.     PrintTree(Tree); //Вызов функции обхода дерева;  
  182.         int count = NodeCount(Tree);
  183.         cout<<"The number of nodes " << count<<endl;
  184.         int hght = HeightOfTree(Tree);
  185.         cout <<"Height of Tree " << hght<<endl;
  186.         DelTree(Tree);
  187.         cout <<"Enter the lvl"<<endl;
  188.         int level;
  189.         cin>> level;
  190.         PrintTreeLvl(Tree,level);
  191.     //return 0;
  192. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement