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

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


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

Висновки

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


 

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

30293. Основные методы художественной литературы. Реализм. Многообразие подходов к проблеме реализма в литературоведении. Просветительский реализм 29 KB
  Реализм. Многообразие подходов к проблеме реализма в литературоведении. Просветительский реализм. 1 Реализм это художественное направление имеющее целью возможно ближе передавать действительность стремящееся к максимальному правдоподобию.
30294. Основные методы художественной литературы. Модернизм - идейные основы и творческая практика. Основные течения. Идейные основы и художественная практика акмеизма 29.5 KB
  Идейные основы и художественная практика акмеизма. Для акмеизма была характерна крайняя аполитичность полное равнодушие к злободневным проблемам современности. Но если в поэзии символизма определяющим фактором являлась мимолетность сиюминутность бытия некая тайна покрытая ореолом мистики то в качестве краеугольного камня в поэзии акмеизма был положен реалистический взгляд на вещи. Главные идеи акмеизма были изложены в программных статьях Н.
30295. Основные методы художественной литературы. Модернизм - идейные основы и творческая практика. Основные течения. Идейные основы и художественная практика футуризма 23.5 KB
  Философскими предпосылками появление модернистического исва считаются: труды философа Нитше а также исследования Шопенгауэра. По мнению Нитше вся система миров культуры находится в состоянии глубочайшего кризиса. Нитше для активации духовн исканий чела создает острую словесную провокацию: он пишет о мифич сверхчеле кот должен прийти на смену обычному челу слабому потребителю. Для Нитше это норма а совершить усилия – это сверхнорма.
30296. Типология реализма в историческом аспекте (первобытный, ренессансный). Характеристика каждого этапа развития метода реализма 22.5 KB
  Идейная основа: Сознание эпохи перехода от Средневековья к Новому времени соотносимой с вызреванием капиталистического строя в недрах феодального Доминанта: Абсолютизация человеческой личности в ее целостности; представление о человеке как о единстве разумного и чувственного как о свободном существе с беспредельными творческими возможностями Основа эстетики: Антропоцентризм принцип Человек – мера всех вещей Характерные черты: Гиперисторизм идеалов связанный с концепцией родового человека; стихийный синкретизм мировосприятия выражающийся...
30297. Типология реализма в историческом аспекте. Классический реализм 19 века 26 KB
  Классический реализм 19 века. В тридцатые годы XIX века в ряде европейских литератур утверждаются эстетические принципы критического реализма XIX века. Открытием критического реализма XIX века было изображение социального характера создание образа воплощавшего типические черты современного общества. Однако такое документально точное изображение среды реализма XIX века означало собой лишь подготовительную стадию в художественном освоении жизненных обстоятельств.
30298. Типология реализма в историческом аспекте. Социалистический реализм 26.5 KB
  Социалистический реализм являясь основным методом советской художественной литературы и литературной критики требует от художника правдивого историческиконкретного изображения действительности в её революционном развитии. Причём правдивость и историческая конкретность художественного изображения действительности должны сочетаться с задачей идейной переделки и воспитания в духе социализма. В изображении действительности показать процесс исторического развития который в свою очередь должен соответствовать материалистическому пониманию...
30299. Основные методы художественной литературы. Сентиментализм. Идейные основы и художественная практика 32.5 KB
  Первостепенное место в представлениях сентименталистов занимают чувства или как говорили в России в XVIII в. В России сентиментализм зарождается в 60е годы но лучшие его произведения Путешествие из Петербурга в Москву Радищева Письма русского путешественника и повести Карамзина относятся к последнему десятилетию XVIII в. в Западной Европе и России подготовленное кризисом просветительского рационализма см. В России представителями С.
30300. Основные методы художественной литературы. Модернизм - идейные основы и творческая практика. Основные течения. Идейные основы и художественная практика символизма 29 KB
  Идейные основы и художественная практика символизма МОДЕРНИЗМ общее обозначение всех авангардистских направлений в культуре 20 века программно противопоставивших себя традиционализму в качестве единственно истинного искусства современности или искусства будущего . В более строгом историческом смысле ранние стилистические тенденции такого направления импрессионизм постимпрессионизм символизм стиль модерн в которых разрыв с традицией еще не был так резок и принципиален как позднее. Символизм европейское литературнохудожественное...