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

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


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

Висновки

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


 

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

54587. Информационные процессы. Конспект урока по информатике 8 класс 68 KB
  Требования к знаниям и умениям: Знать: Информационные процессы; Виды памяти; Передача информации; Обработка информации. Уметь: Приводить примеры ситуаций являющихся источником информации приёмником информации; Приводить различные примеры процесса обработки информации. Что такое информация для человека Назовите некоторые источники получения информации.
54588. Новые педагогические технологии на уроках иностранного языка 92.5 KB
  Попрежнему основными трудностями являются недостаток активной устной практики в расчете на каждого ученика группы отсутствие необходимой индивидуализации и дифференциации обучения. Учитывая специфику предмета иностранный язык эти технологии могут обеспечить необходимые условия для активизации познавательной и речевой деятельности каждого ученика группы предоставляя каждому ученику возможность осознать осмыслить новый языковой материал получить достаточную устную практику для формирования необходимых навыков и умений. Если в таких...
54589. НТР. Її вплив на структуру та розміщення світового господарства 44 KB
  Мета: сформувати в учнів систему знань про вплив НТР на галузеву структуру та територіальну організацію виробництва. Обладнання: схема Вплив НТР на світове господарство політична карта світу атласи підручники.
54590. NURBS (Non-Uniform Rational B-Splines) 1.18 MB
  Изза особенности строения NURBS поверхности всегда гладкие у них нет острых краев присущих полигонам поэтому они широко используются в органическом моделировании подобном созданию растительных форм для создания моделей животных людей машин и т. NURBS поверхности не состоят из сетки прямоугольников разбиение поверхностей на многоугольники происходит лишь на этапе рендеринга и предполагает использование оптимального алгоритма для сохранения гладкости. Существует два типа NURBS кривых и поверхностей: Point рис.
54591. Рыночное равновесие и его нарушение 19.06 KB
  Объемы покупок и продаж на рынке всегда равны между собой, так как это две стороны сделки. Однако это не означает, что рынок находится в равновесном состоянии при любом значении цен. Цены могут отражать как избыточное, так и дефицитное состояние рынка.
54592. Сущность и функции денег, их виды 19.64 KB
  Деньги – это особый товар, играющий роль всеобщего эквивалента, кроме того, деньги — это самое ликвидное средство обмена, то есть товар способный обмениваться на любые продукты человеческого труда.
54593. О. Генри «Дороги, которые мы выбираем» 4.09 MB
  Цели: Учить задумываться над смыслом прочитанного, формировать гуманитарную компетентность, развивать межпредметные связи- синтезировать знания английского языка, зарубежной литературы, географии, биологии,...
54594. О каких уроках мечтают дети? 43 KB
  Педагоги Григорьевской средней школы Нытвинского района Пермской области во время осенних каникул откликнулись на предложение учащихся самостоятельно подготовить и провести такие уроки о которых мечтают дети. Учащиеся назвали эти уроки Уроками Будущего в настоящем где учителями добровольно стали ученики средних общеобразовательных школ села Григорьевское Нытвинского района Пермской области и №639 ЮАО г. Было предложено 10 уроков: Урок Радости Урок Здоровья Урок танца Урок Сна Урок Игры Урок рисования Урок психологии Урок...
54595. Правда о Святом Царе Иоанне Васильевиче (Грозном) 1.45 MB
  Речь Царя Иоанна Васильевича перед Собором епископов русских. 50 Царь грядет У гроба Грознаго Царя А. Деяния великого Царя и жидовские козни. Через 387 лет в этом храме 15 марта 1917 года в день насильственного отрешения от Власти последнего Русского Царя Николая II умученного от жидов 417 июля 1918 года в Екатеринбурге произошло явление иконы Божией Матери Державная.