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

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


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

Висновки

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


 

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

16751. Роль агломерации в процессе кучного выщелачивания золота 71.5 KB
  Роль агломерации в процессе кучного выщелачивания золота Д. Е. Толстов Г. 2000 г. УДК 669.213:66.094.6 Технология кучного выщелачивания это одно из наиболее перспективных направлений в производстве золота в настоящее время. Внедрение этой технологии позволило вовлечь в произ
16752. Специальные и комбинированные методы обогащения 68 KB
  Специальные и комбинированные методы обогащения. В МИСиСе Павлов А.В. Корчагин К.А. Дубачев А.В. 2003 разработаны основы комплексной технологии пирометаллургического обогащения титанокремнистых концентратов Ярегского месторождения. Предложен принципиально новый п
16753. Скважинная гидротехнология — экологически чистая технология освоения земных недр 65.5 KB
  Скважинная гидротехнология экологически чистая технология освоения земных недр В странах СНГ после распада СССР произошло резкое сокращение объемов производства минерального сырья причем не столько вследствие экономических обстоятельств сколько в силу политиче
16754. Кучное выщелачивание золота, зарубежный опыт и перспективы развития 1.98 MB
  Справочник Кучное выщелачивание золота зарубежный опыт и перспективы развития. Рецензент вицепрезидент Международной академии минеральных ресурсов А.И. Кривцов. Справочник составлялся под патронажем Межправительственного совета стран СНГ по разведке...
16755. Флотационная переработка золотосодержащих руд 43 KB
  Флотационная переработка золотосодержащих руд Абдурахмонов С.А. зав. кафедрой Металлургия АГМФ НГГИ докт техн наук профессор; Муталов А.М. доцент кафедры Горное дело и горная электромеханика АГМФ НГГИ канд. техн наук; Муталова М.А. доцент кафедры...
16756. ЦЕЛЕСООБРАЗНОСТЬ ПРИМЕНЕНИЯ БИОВЫЩЕЛАЧИВАНИЯ ДЛЯ ПЕРЕРАБОТКИ БЕДНЫХ СИЛИКАТНЫХ НИКЕЛЕВЫХ РУД 36 KB
  ЦЕЛЕСООБРАЗНОСТЬ ПРИМЕНЕНИЯ БИОВЫЩЕЛАЧИВАНИЯ ДЛЯ ПЕРЕРАБОТКИ БЕДНЫХ СИЛИКАТНЫХ НИКЕЛЕВЫХ РУД Крылова Л.Н. МИСиС Ким Е.А. МИСиС Адамов Э.В. МИСиС В условиях истощения запасов сульфидных никелевых руд оставшихся только в Канаде и России и наличия единственного в ...
16757. Цианид ртуть и кислотные стоки ядовитые спутники золота 199.5 KB
  Цианид чаще других химических элементов используется в производстве золота при извлечении желтого металла из золотоносной руды, несмотря на то, что разливы и утечки цианида чрезвычайно токсичны для рыбы, растительных форм жизни и человека. В последние несколько лет в штате Монтана, США и Турции вместо данной практики применяются иные технологии, что должны быть приняты на вооружение другими золотодобывающими предприятиями во всем мире
16759. Вопросы влияния ультразвука, магнитных полей и электрического тока на флотацию золота 126.5 KB
  К вопросу изучения влияния ультразвука магнитных полей и электрического тока на флотацию золота С.И. Черных О.И. Рыбакова Н.M. Лебедев Т.И. Жирнова ФГУП Институт ГИНЦВЕТМЕТ ЧГТУ ООО АлександраПлюс Ультразвуковая обработка Использование ультразвука в те...