75667

Дерева. Бінарні дерева. Пошук

Лабораторная работа

Информатика, кибернетика и программирование

В основі метода для пошуку листів лежить звичайний обхід бінарного дерева, виконаний за допомогою рекурсії. Функція викликає саму себе двічі: для правого і лівого піддерев. При цьому кожен з цих викликів також містить рекурсію для вже своїх піддерев.

Украинкский

2015-01-24

338.97 KB

1 чел.

Міністерство  освіти  і  науки України

Вінницький національний технічний університет

Інститут інформаційних технологій та комп’ютерної інженерії

Кафедра ПЗ

Лабораторна робота №7 варіант №9

з дисципліни Алгоритми та структури даних

Виконала: ст. гр. 1 ПІ-13б                            Лілик Л. С.

Перевірив:                                                       Власюк В. Х.

Вінниця, 2013

Тема: Дерева. Бінарні дерева. Пошук.

Мета: набуття навичок програмування дерев.

Завдання:

Розробити засоби динамічного збереження дерев та виконання дій над ними згідно варіанту.

Варіант № 9.

Вивести на друк листи дерева.

Складність алгоритму

Складність алгоритму дорівнює O(  2N + 4 ) від Т, де:

Т - час виконання;
Nкількість вузлів дерева.

Опис алгоритму

В основі метода для пошуку листів лежить звичайний обхід бінарного дерева, виконаний за допомогою рекурсії. Функція викликає саму себе двічі: для правого і лівого піддерев. При цьому кожен з цих викликів також містить рекурсію для вже своїх піддерев.


Блок-схема алгоритму

Лістинг фрагментів програми 

 //---Node.h—------------------------------------------------------------------------------------

#include <vector>

using namespace std;

#pragma once

class Node

{

public:

int data;

int x;

int y;

Node *right;

Node *left;

Node *parent;

Node(void);

Node(int _data, int _x, int _y);

Node(const Node &arg);

~Node(void);

void Show(HDC hdc);

int ChangeX(int _x);

int ChangeY(int _y);

void InputData(int _data);

static void Push(int a, int _x, int _y, Node **node, int ChooseBranch);

static void ShowTree(Node *tr,  HDC hdc);

static Node Traversal(Node *tr);

static Node* FindThisNode(Node *tr, int mdx, int mdy);

int PressedArea(int mdx, int mdy);

int UpMouseArea(int mux, int muy);

bool PressedNode(int mdx, int mdy);

static void FindLeaves(Node *tr, vector<int> &leaves);

};

//---Node.cpp ------------------------------------------------------------------------------------

#include "StdAfx.h"

Node::Node(void)

{

data=0;

right=0;

left=0;

parent=0;

x=300;

y=50;

}

Node::Node(int _data, int _x, int _y):data(_data), x(_x), y(_y)

{

right=0;

left=0;

parent=0;

}

Node::Node(const Node &arg)

{

data=arg.data;

x=arg.x;

y=arg.y;

right=0;

left=0;

parent=0;

}

Node::~Node(void)

{

}

void Node::Show(HDC hdc)

{

HPEN hNodePen, hRightPen, holdpen;

HBRUSH hNodeBrush, holdbrush;

 

hNodePen = CreatePen(PS_SOLID, 4, RGB(255, 128, 0));

hRightPen = CreatePen(PS_SOLID, 4, RGB(7, 100, 255));

holdpen = (HPEN)SelectObject(hdc, hNodePen);

 

hNodeBrush = CreateSolidBrush(RGB(255, 128, 0));

holdbrush = (HBRUSH)SelectObject(hdc, hNodeBrush);

 

if (left!=0)

{

 if (((left->x)<x)&&((left->y)>y))

 {

  POINT pnt;

  ::MoveToEx(hdc, x, y+10, &pnt);

  ::LineTo(hdc, left->x, left->y-10);

 }

}

if (right!=0)

{

 if (((right->x)>x)&&((right->y)>y))

 {

  holdpen = (HPEN)SelectObject(hdc, hRightPen);

  POINT pnt;

  ::MoveToEx(hdc, x, y+10, &pnt);

  ::LineTo(hdc, right->x, right->y-10);

 }

}

holdpen = (HPEN)SelectObject(hdc, hNodePen);

Ellipse(hdc, x-30, y-30, x+30, y+30);

char buffer[20];

itoa (data,buffer,10);

::TextOutA(hdc, x-5, y-7, (LPCSTR) buffer, strlen(buffer) );

  

::DeleteObject(hNodePen);

::DeleteObject(hRightPen);

::DeleteObject(hNodeBrush);

}

int Node::ChangeX(int _x)

{

x=_x;

return x;

}

int Node::ChangeY(int _y)

{

y=_y;

return y;

}

void Node::InputData(int _data)

{

data=_data;

}

void Node::Push(int a, int _x, int _y, Node **tr, int ChooseBranch)  // push new element to the binary tree

{

   if (*tr==NULL)

   {

       (*tr) = new Node;

       (*tr)->data = a;

 (*tr)->x = _x;

 (*tr)->y = _y;

       ((*tr)->left) = ((*tr)->right) = 0;

       return;

   }

   if (ChooseBranch == 2)

 Push(a, _x, _y, &((*tr)->right), ChooseBranch);

   else  if (ChooseBranch == 1)

 Push(a, _x, _y, &((*tr)->left), ChooseBranch);

}

void Node::ShowTree(Node *tr,  HDC hdc)  // prints tree

{

   if (tr==NULL)  // return if the tree is empty

       return;

   else  // if tree exists and not empty

   {

       ShowTree(tr->left, hdc);

 tr->Show(hdc); // prints one node

   }

   ShowTree(tr->right, hdc);

}

Node Node::Traversal (Node *tr)  // traverses the tree

{

   if  (tr!=NULL)

   {

       Traversal((*tr).left);

       Traversal((*tr).right);

       //(*tr).data;

 return (*tr);          

   }

}

int Node::PressedArea(int mdx, int mdy)

{

if (mdx>(x-30)&&mdx<x&&mdy<(y+30)&&mdy>(y-30)) return 1;   // left child

else if (mdx<(x+30)&&mdx>x&&mdy<(y+30)&&mdy>(y-30)) return 2; // right child

else return -1;

}

int Node::UpMouseArea(int mux, int muy)

{

if (mux<(x-10)&&muy>(y+10)) return 1;   // left child

else if (mux>(x+10)&&muy>(y+10)) return 2; // right child

else return -1;

}

bool Node::PressedNode(int mdx, int mdy)

{

if (mdx>(x-30)&&mdx<(x+30)&&mdy<(y+30)&&mdy>(y-30)) return true;   

else return false;

}

Node* Node::FindThisNode(Node *tr, int mdx, int mdy)  // traverses the tree

{

   if  (tr!=NULL)

   {

  if(tr->PressedNode(mdx, mdy))

      return tr;

  Node *temp = NULL;

  if(tr->left!=NULL)

 {

    temp = FindThisNode(tr->left, mdx, mdy);

    if(temp!=NULL)

     return temp;

 }

  if(tr->right!=NULL)

 {

    temp = FindThisNode(tr->right, mdx, mdy);

    if(temp!=NULL)

  return temp;

 }

 return temp;

}

}

void Node::FindLeaves(Node *tr, vector<int> &leaves)

{

if  (tr!=NULL)

   {

       FindLeaves(((*tr).left), leaves);

       FindLeaves(((*tr).right), leaves);

       if ((((*tr).right)==0)&&(((*tr).left)==0))

  leaves.push_back((*tr).data);

  

   }

}

// ------ stdafx.h: ------------------------------------------------------------------------------------

#pragma once

#include "targetver.h"

#define WIN32_LEAN_AND_

#include <windows.h>

#include <stdlib.h>

#include <malloc.h>

#include <memory.h>

#include <tchar.h>

#include "Main.h"

#include "Node.h"

#include <vector>

using namespace std;

//---- Main.cpp ------------------------------------------------------------------------------------

У цьому файлі міститься графічне моделювання дерева, функції малювання, роботи з вікном, створення вікон тощо.


Результат виконання 

Висновки

Набуто навички програмування дерев. В результаті виконання лабораторної роботи створено програму для побудови дерева і виведення листків дерева.


 

А также другие работы, которые могут Вас заинтересовать

32466. Направление технического прогресса в СКС и Т 27.5 KB
  Современная индустрия туризма за последние годы притерпела вестма существенные изменения в связи с внедрением новых компьютерных технологий успешное функционирование любой фирмы на рынке туристского бизнеса практически не мыслимо без использования современных информационных технологий. Современные компьютерные технологии активно внедряются в сферу туристского бизнеса и их применение становится неотъемлемым условием повышения конкурентоспособности любого туристского предприятия. Возможность формирования новых маркетинговых каналов...
32467. Инфраструктура предприятий сервиса. Технические средства предприятий (организаций) социально-культурного сервиса и туризма 31 KB
  Тип гостиничной телефонной станции зависит от количества абонентных точек назначения гостиницы и ее расположения. Для облегчения связи с работниками управления и администрации гостиницы телефонное оборудование может быть укомплектовано телефонной системой. Устройство внутренней связи: важный фактор эффективности работы гостиницы. Телетайпфакс представляет собой систему письменной телекоммуникации обслуживающую как администрацию гостиницы так и клиентов.
32468. Задачи технического и технологического оснащения предприятий 27.5 KB
  Технология совокупность методов обработки изготовления изменения состояния свойств формы сырья материала или полуфабриката применяемых в процессе производства для получения готовой продукции наука о способах воздействия на сырье материалы и полупродукты соответствующими орудиями производства. Развитие науки и техники способствует совершенствованию средств массового производства туристских услуг материальнотехнической базы в гостиничном хозяйстве на транспорте в бюро путешествий.
32469. Модернизация технических средств предприятий СКС и Т 26 KB
  Бурное развитие туристкой индустрии в последнее десятилетие связано в 2мя факторами: развитием гражданской авиации и созданием компьютерных систем бронирования. В свою очередь увеличение числа авиалиний самолетов а так же рост объемов авиаперевозок закономерно привели к необходимости создания и использования компьютерных систем бронированияCRS которые стали основным инструментом для резервирования авиабилетов. Теперь в системах бронирования заложена информация не только о наличие мест но и общая информация о рейсах.
32470. Технология художественных изделий из керамики 498.54 KB
  Обжиг керамических изделий 3й разряд Сформировать знания о процессе обжига керамических изделий его видах и способах. Назначение и суть обжига керамических изделий. Виды и способы обжига. Объясняет назначение обжига керамических изделий виды и способы обжига правила загрузки и выгрузки изделий устройство обжиговых печей.
32471. Формование керамических изделий и его виды 103.77 KB
  Способы формования керамических изделий Исходя из содержания воды в формовочной массе различают следующие основные способы формовки: способ литья содержание воды 25–34; пластический способ воды 16–25 – это свободная лепка формование на гончарном круге ручной оттиск в форме формование по вращающейся гипсовой форме с помощью шаблона или ролика; полусухой способ 7–16 влажности; сухой способ 2–7 влажности. Литье Этот способ широко применяется в производстве художественных керамических изделий что объясняется возможностью...
32472. Ручная роспись керамических изделий, подготовка, инструменты 32.21 KB
  Пером расписывают изделия прошедшие утельный или политой обжиг. Кистью можно наносить на изделия цветные массы ангобы глазурь. Роспись на изделиях можно производить без нанесения предварительного контура и по заранее нанесенному припорохом рисунку. На отводку поступают изделия предварительно оформленные основным декором.
32473. Декорирование изделий в сыром виде 15.92 KB
  Способы нанесения декора на керамический материал Декорирование является важным этапом в общем цикле технологического процесса по изготовлению художественных керамических изделий. Декорирование керамических изделий можно вести как живописным так и скульптурным методом. К живописному относят роспись изделий а также нанесение на них сплошных или частичных декоративных покрытий керамическими красками глазурями ангобами люстрами и эмалями.
32474. Сушка изделий, ее назначение, виды сушки 13.79 KB
  Сушка керамических изделий полуфабрикатов может быть естественной на открытом воздухе под навесами в сараях и т. К недостаткам туннельных сушилок относятся: большое количество вагонеток и необходимость их пополнения подверженность металлических изделий вагонеток коррозии неравномерность сушки изделий по поперечному сечению туннеля вверху температура теплоносителя выше чем внизу и необходимость круглосуточной загрузки и разгрузки вагонеток. Недостатки камерных сушилок: неравномерная сушка изделий изза различной температуры...