Создать список из вершин дерева: Решение

Опубликовано Dec 26, 2011 в Деревья и графы, Связанные списки | 2 коммент.

,

В этом посте мы приводим два варианта решения задачи “Создать список из вершин дерева.”

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
#include "stdafx.h"
#include <vector>
#include 
 
using namespace std;
//Описание структуры узла
  struct tree_node
        {
           tree_node* left;
           tree_node* right;
           int data;
 
           tree_node (int Data) : left(NULL), right(NULL), data(Data){
           }
 
           tree_node () : left(NULL), right(NULL), data(0){
           }
        };
 
  //ПЕРВЫЙ ВАРИАНТ (без использования STL). Ответ на второй вопрос - ДА.
  //Результат - односвязный динамический список list_header.        
 
  void nodes_on_level(const tree_node* root, int &curr_level, int level,
                tree_node* &list_header, tree_node* &cur_list_node)
  {
    if(root)
    {
      if (curr_level == level)
      {
        tree_node* new_list_node = new tree_node(root->data);
 
        if (list_header)
          cur_list_node->left = new_list_node;
        else
          list_header = new_list_node;
 
        cur_list_node = new_list_node;
      }
      curr_level++;
      if(root->left && curr_level left,curr_level,level,list_header,cur_list_node);
      }
      if(root->right && curr_level right, curr_level,level,list_header,cur_list_node);
      }
      curr_level--;
    }
  }
 
//Метод для очистки памяти, динамически выделенной под линейный список - ОБЯЗАТЕЛЕН!
   void remove_linked_list(tree_node* &list_header)
   {
     tree_node* deleted_node;
     do
     {
       cout << list_header->data<< endl; //Для проверки, что удаление прошло
       deleted_node = list_header;
       list_header = list_header->left;
       delete deleted_node;
     }
     while (list_header);
   }
/*--------------------------------------------------------------------------------------*/
 
  //ВТОРОЙ ВАРИАНТ (с использованием STL).
  //Результат - вектор vector
<tree_node>& nodes_list.   
 
void nodes_on_level_stl(const tree_node* root,  int& curr_level, int level,
                        vector& nodes_list, tree_node& curr_list_node)
{
  if(root)
  {
    tree_node cur_list_node(root->data);
    if (curr_level == level)
    {
      nodes_list.push_back(cur_list_node);
    }
    curr_level++;
    if (curr_level left)
      {
        nodes_on_level_stl(root->left,curr_level,level, nodes_list, cur_list_node);
      }
      if(root->right)
      {
        nodes_on_level_stl(root->right, curr_level,level,nodes_list,cur_list_node);
      }
    }
    curr_level--;
  }
};
 
//Обертка вокруг основного метода реализована для сокрытия вспомогательных параметров,
//нужных для организации рекурсии. Это полезно сделать и для первого варианта.
 
std::vector
 nodes_on_level_stl_CALL(const tree_node* root, int level)
{
  vector
 nodes_list;//вместо списка tree_node* &list_header
  int cur_level = 0;
  tree_node level_nodes_;
  nodes_on_level_stl(root, cur_level, level,nodes_list, level_nodes_);
  return nodes_list;
}
 
/*--------------------------------------------------------------------------------------*/
int main()
{
  //ТЕСТОВЫЕ ДАННЫЕ
  //Бинарное дерево заданно
  //                5
  //        3               7
  //    1      4       6       8
  //             10
  //           12  13
  //Для номера уровня 2 результат 1 -> 4 -> 6 -> 8
 
tree_node Node0(5);
tree_node Node1(3); tree_node Node2(7);
tree_node Node3(1); tree_node Node4(4); tree_node Node5(6); tree_node Node6(8);
tree_node Node7(10);
tree_node Node8(12); tree_node Node9(13);
 
      Node0.left = &Node1;
      Node0.right = &Node2;
      Node1.left = &Node3;
      Node1.right = &Node4;
      Node2.left = &Node5;
      Node2.right = &Node6;
      Node4.right = &Node7;
      Node7.left = &Node8;
      Node7.right = &Node9;
/*------------------------------------------------------------------*/
 
//Вызов для варианта с использованием STL
  vector
 nodes_list = nodes_on_level_stl_CALL(&Node0, 2);
 
/*------------------------------------------------------------------*/
//Вызов для варианта с без STL
 tree_node* list_header = NULL;
 tree_node* cur_list_node = NULL;
 int cur_level = 0;
 nodes_on_level(&Node0, cur_level, 2, list_header, cur_list_node);
//Очистить память, выделенную в куче для создания списка узлов
  remove_linked_list(list_header);
}

Автор публикации:

2 Коммент. : “Создать список из вершин дерева: Решение”

  1. Денис says:

    хмммм… а почему код не рабочий выставлен?

Оставить комментарий

Ваш адрес email не будет опубликован.


*