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

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


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

Висновки

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


 

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

11406. Чтение и изучение фольклорных жанров на уроках литературы в специальной (коррекционной) школе III-IV вида (на материале пословиц и поговорок, былины) 18.31 KB
  Лабораторное занятие № 6 Чтение и изучение фольклорных жанров на уроках литературы в специальной коррекционной школе IIIIV вида на материале пословиц и поговорок былины. Задания для подготовки Выявите по словарям литературоведческих терминов значение понятий
11407. УСТНОЕ НАРОДНОЕ ТВОРЧЕСТВО БЫЛИНЫ 53 KB
  УСТНОЕ НАРОДНОЕ ТВОРЧЕСТВО БЫЛИНЫ Занятия по фольклору в седьмом классе начинаются с рассказов учащихся об известных им жанрах устного народного творчества с пересказов полюбившихся им сказок пословиц поговорок загадок. Они могут быть проведены в виде св...
11408. УСТНОЕ НАРОДНОЕ ТВОРЧЕСТВО Обрядовый фольклор 58 KB
  УСТНОЕ НАРОДНОЕ ТВОРЧЕСТВО Обрядовый фольклор 2 часа Урок 8 Обряды и обрядовый фольклор. Произведения календарнообрядового цикла: колядки веснянки масленичные летние песни осенние обрядовые песни. Эстетическое значение обрядового фольклора
11409. ЦИКЛИЧЕСКИЕ ВЫЧИСЛИТЕЛЬНЫЕ ПРОЦЕССЫ 71.5 KB
  Лабораторная работа ЦИКЛИЧЕСКИЕ ВЫЧИСЛИТЕЛЬНЫЕ ПРОЦЕССЫ Цель работы; ознакомление и приобретение навыков алгоритмизации задач методом структурной декомпозиции использования основных арифметикологических и управляющих операторов языка С/С и отладки пр...
11411. ОБРАБОТКА МАССИВОВ ДАННЫХ С ИСПОЛЬЗОВАНИЕМ ПОЛЬЗОВАТЕЛЬСКИХ ФУНКЦИЙ 50.5 KB
  Лабораторная работа ОБРАБОТКА МАССИВОВ ДАННЫХ С ИСПОЛЬЗОВАНИЕМ ПОЛЬЗОВАТЕЛЬСКИХ ФУНКЦИЙ Цель работы: ознакомление с принципами описания и алгоритмизации обра ботки массивов однотипных данных средствами языка С/С и приобретение навыков работы и отладки...
11413. Нормализация баз данных 36 KB
  Лабораторная работа № 1. Нормализация баз данных. Задание: 1. Спроектировать реляционную базу данных состоящую из четырех связанных отношений. 2. Произвести нормализацию БД до третьей нормальной формы. Нормализация данных Один и тот же набор данных в реляцио...
11414. Запросы определения данных SQL 59.5 KB
  Лабораторная работа № 2. Запросы определения данных SQL. Задание: 1. Определить схемы разработанных отношений на SQLсервере. Обосновать выбор типов данных атрибутов отношений. 2. Определить произвольный двух или трехзначный атрибут пол статус и т.д. и ввести его в одн