бинарное дерево С++
Добавлено: 06 ноя 2013, 12:51
Здравствуйте,не могли бы Вы помочь с задачей на бинарные деревья С++?(задача:назовем пару различных вершин дерева двойниками,если их значения и уровни совпадают.Найти всех двойников в данном целочисленном бинарном дереве.)Сделала ввод и вывод бинарного дерева,а как найти двойников?подсказали алгоритм,но ничего не выходит:осуществляем обратный обход дерева,берем k вершину с L уровня и снова перебираем с корня до этого уровня,если k==ai,то выводим пару двойников.
Код: Выделить всё
#include <iostream>
#include <conio.h>
#include <stdlib.h>
#include <stdio.h>
#include <clocale>
using namespace std;
struct node
{
int d;//элементы дерева
node *l, *r;//Левая и Правая часть дерева
};
//создание поддерева
void MakeSubTrees(node *leaf)
{
node *Top;int key;
cout<<"введите текущий узел"<<endl;
cin>>leaf->d;
cout<<leaf->d<<" имеет левое поддерево?"<<endl;
cin>>key;
if (key==1)
{
(Top)=new node;
leaf->l=Top;
MakeSubTrees(Top);
}
else
leaf->l=NULL;
cout<<leaf->d<<" имеет правое поддерево?"<<endl;
cin>>key;
if (key==1)
{
(Top)=new node;
leaf->r=Top;
MakeSubTrees(Top);
}
else
leaf->r=NULL;
}
//создание дерева
void MakeTree(node **Top)
{
(*Top)=new node;
MakeSubTrees(*Top);
}
void ViewTree(node *Top,int level)
{
if (Top){
ViewTree(Top->l,level+1);
for (int i=0;i<level;i++)
cout<<" ";
cout<<Top->d<<endl;
ViewTree(Top->r,level+1);
}
}
void main()
{
setlocale(LC_CTYPE, "Russian");
node *Top;
MakeTree(&Top);
ViewTree(Top,0);
getch();
return;
}