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 ------------------------------------------------------------------------------------

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


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

Висновки

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


 

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

3588. Сценарій Вернісаж особистостей 14.63 KB
  Сценарій Вернісаж особистостей Ведуча: шановні учні, вчителі! Сьогодні ми зібрались в цій залі, щоб подумати, помріяти, відпочити і підтримувати учасників «Вернісаж особистостей». У конкурсі приймають участь 15 учасників. Ведучий: і як водиться, на ...
3589. Випускний вечір 2012 118.5 KB
  Випускний вечір 2012 Святково прибрана актова зала. Під тиху музику ведуча звертається до присутніх. Ведуча: Доброго вам вечора, шановні батьки, вчителі, гості! Здається, що тільки вчора пролунав останній дзвоник, позаду - напружена пора іспитів, і ...
3590. Відпрацювання навиків розв’язування вправ на застосування відсоткових відношень 112.5 KB
  Відпрацювання навиків розв’язування вправ на застосування відсоткових відношень. розвивати елементи логічного мислення, виховувати культуру математичної мови та запису. Обладнання: ілюстрації до задач, картки із самостійною роботою у вигл...
3591. Використання комп’ютерних мереж у навчальному процесі 114.5 KB
  Використання комп’ютерних мереж у навчальному процесі Відомий американський вчений науковець Джон Нейсбіт в минулому виконавчий директор ІБМ (IBM - International Business Machine Corp., одна з найвідоміших корпорацій у світі, яка займається вип...
3592. Свято зі сльозами на очах 97 KB
  Свято зі сльозами на очах… Сценарій до дня Перемоги. На сценi розвішено плакати часiв Другої світової війни, звучить мелодія пісні «День Перемоги» Ведуча Для юних — це вже давнина Минуло мирних 65 роки. Як з нашої землi ненависна вiйна Втікала ...
3593. Перше ознайомлення з базами даних. СКБД. Моделі, об'єкти баз даних. СКБД Ассеss 295.67 KB
  Перше ознайомлення з базами даних. СКБД. Моделі, об'єкти баз даних. СКБД Ассеss. Проектування бази даних у середовищі СКБД Access. Створення таблиць БД. Сформувати уявлення про бази даних, їх призначення та основних етапів їх створення, формування пізнавальних здібностей, розвиваюча: розвивати логічне мислення, розвиток пам'яті, розвиток уважності
3594. Редагування структури таблиці й даних БД. Впорядкування, пошук та фільтрація даних 151.39 KB
  Редагування структури таблиці й даних БД. Впорядкування, пошук та фільтрація даних Мета: ознайомити учнів із можливостями обробки інформації в базі даних, навчити використовувати команди СКБД Access для зміни структури таблиці, додавання, знищення, ...
3595. Типи зв'язків у таблицях. Створення зв'язків між елементами в таблицях. Запити. Створення запитів 363.27 KB
  Типи зв'язків у таблицях. Створення зв'язків між елементами в таблицях. Запити. Створення запитів. Навчити учнів встановлювати зв’язки між таблицями, створювати запити, Розвивати логічне мислення, розвиток пам'яті, вміння працювати з масивами інформації
3596. Об'єкт БД — форми. Способи створення форм 397.5 KB
  Об'єкт БД — форми. Способи створення форм. Мета: навчальна: ознайомити учнів із типами форм та способами їх створення, розвиваюча: розвивати вміння роботи з БД, логічне мислення, розвиток уважності, виховна: формування навичок зібраності, уважності, акуратності в роботі з табличними даними.