бинарное дерево С++

[fkty]

Здравствуйте,нужна помощь в задаче:назовем пару различных вершин дерева двойниками,если их значения и уровни совпадают.Найти всех двойников в данном целочисленном бинарном дереве.
Как сделать ввод с клавиатуры?и как реализовать поиск двойников,если в моем коде не может быть одинаковых значений?

//Программа формирует дерево из массива целых чисел и выводит его на экран
//root - корень дерева
#include <iostream>
#include <conio.h>
using namespace std;
struct Node{
        int d;         //Данные элемента
        Node *left;    //Ссылка на левое поддерево
        Node *right;   //Ссылка на правое поддерево
};
Node *first(int d);                    //Формирование первого элемента
Node *search_insert(Node *root,int d); //Поиск с включением
void print_tree(Node *root,int l);     //Обход дерева
 
//-------------------------------------------
int main()
{
        int b[]={10,25,20,6,21,8,1,30}; 
        Node *root=first(b[0]);    //Формируем корень дерева
      //Ищем место куда вставить и вставляем новые элементы
       for(int i=1;i<8;i++)search_insert(root,b[i]); 
        print_tree(root,0);            //вывод дерева на экран
		getch();
        return 0;
}
 
//--------------------------------------------
//Формирование первого элемента
Node *first(int d){
Node *pv =new Node;   //Создаём элемент
pv->d=d;              //Присваиваем значение элементу поля
pv->left=0;           //Ссылка на левое поддерево равна NULL
pv->right=0;          //Ссылка на правое поддерево равна NULL
return pv;            //Возвращаем адрес элемента
}
 
//---------------------------------------------
 
//Поиск с включением
Node *search_insert(Node *root,int d){
Node*pv=root,*prev;
bool found = false;    //Переменная отвечающая за то что нашли ли элемент или нет
/*Ниже приведён алгоритм поиска короче если нашли такой же элемент то мы его не вставляем в дерево выходим из функции возвратив адрес совпавшего элемента*/
while(pv&&!found){
        prev=pv;                       //получаем адрес элемента от которого будем пускать корни
        if(d==pv->d)found=true;        //совпадение выходим из цикла
        else if(d<pv->d)pv=pv->left;   //Всовываемя в левое поддерево
        else pv=pv->right;             //Всовываемя в правое поддерево 
//Выход из цикла осуществляется, тогда когда нашли свободный адрес : ссылку у дерева : для вставки нового узла */
}
//---------------------------
/*Если совпало значение элемента со значением элемента который хотим вставить то выходим из функции возвращая адрес элемента
с которым совпало */
if(found)return pv;               
//Создание нового узла
Node *pnew =new Node;
pnew->d=d;
pnew->left=0;
pnew->right=0;
if(d<prev->d)
//Присоединение к левому поддереву предка
prev->left=pnew;
else 
//присоединяем к правому поддереву предка
prev->right=pnew;
return pnew;
}
//---------------------------------------
//Обход дерева
void print_tree(Node *p,int level){
        if(p){
               print_tree(p->right,level+1);          //Перемещение по правым поддеревьям     
                for(int i=0;i<level;i++)cout<<"   ";
                cout<<p->d<<'\n';                      //вывод значений дерева
				  print_tree(p->left,level+1);           //Перемещение по левым поддеревьям
                
     }
}

[fkty]

все переделала,но выводит неправильно.

#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<<"введите текущий узел";
	cin>>leaf->d;
	cout<<"он имеет левое поддерево?";
	cin>>key;
	if (key==1)
	{
		(Top)=new node;
		leaf->l=Top;
		MakeSubTrees(Top);
	}
	else
		leaf->l=NULL;
	cout<<"он имеет правое поддерево?";
    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);
}

int High(node *Top)
{ 
	int Highleft,Highright,H;
	if (Top==NULL)
		H=0;
	else
	{
		Highleft=High(Top->l);
		Highright=High(Top->r);
		if (Highleft>Highright)
			H=Highleft+1;
		else
		H=Highright+1;
	}
	return H;
}
void WayHoriz(node *Top,int level)
{
	if (Top!=NULL)
		if (level==1)
			cout<<Top->d;
		else
		{
			WayHoriz(Top->l,level-1);
			WayHoriz(Top->r,level-1);
		}
}
void ViewTree(node Top)
{
	int i,HighTree;
	HighTree=High(&Top);
	for (int i=0;i<HighTree;i++)
	{
		WayHoriz(&Top, i);
	}
}
void main()
{
	setlocale(LC_CTYPE, "Russian");
	node *Top;
	MakeTree(&Top);
	ViewTree(*Top);
	getch();
	return;
}

[fkty]

вот итоговый вариант ввода,вывода.помогите пожалуйста с двойниками

//назовем пару различных вершин дерева двойниками,если их значения и уровни совпадают.найти 
//всех двойников в данном целочисленном бинарном дереве
#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;
}

[fkty]

помогите пожалуйста с двойниками....вот приблизительный план:обходим дерево(например обратный обход);берем какую-нибудь вершину k с уровня L;снова перебираем с корня до этого уровня L;если k==ai,то выводим пару двойников

[fkty]

вот функция прямого обхода

void WayUpDown(node *Top)
{ 
	if (Top==NULL)
		return;
	cout<<Top->d;
	WayUpDown(Top->l);
	WayUpDown(Top->r);
}

[SaLoKiN]

функция прямого обхода

не пойдет...прямой обход это есть ничто иное как обход в глубину.
для вашей задачи нужен обход в ширину, но при этом нужно использовать еще одну структуру-очередь.
вот как предлагают это делать

Пустая Очередь <== корень;
while
(Очередь != пусто){ Очередь ==> t; Посетить t;
for(x∈сыновья(t))Очередь <== x;}


Обозначение: for (x∈S) . . . - цикл, выполняемый для каждого элементаx из множества S (∈- "принадлежит")

[SaLoKiN]

или вот еще

Двоичное дерево задается следующей структурой:

typedef struct _t {
    int data; /* данные в узле */
    struct _t *left, *right; /* указатели на левого и правого сыновей */
} t;

t *root; /* корень дерева */

Приведем пример процедуры, которая выводит на экран узлы дерева в порядке обхода в ширину. Считаем, что определены три функции:

void add(t *elem); /* добавляет в конец очереди элемент elem */
t *del(); /* удаляет из очереди первый элемент и возвращает указатель на него */
int empty(); /* возвращает 1, если очередь пуста, и 0 в противном случае */
Тогда процедура обхода будет иметь следующий вид:

void width(t *root)
{
    if (!root)
        return;
    add(root);
    while (!empty()) {
        t *curr = del();
        printf("%d ", curr->data);
        if (curr->left)
            add(curr->left);
        if (curr->right)
            add(curr->right);
    }
}

[SaLoKiN]

называется я тебя слепила из того что было...
реализован обход в ширину. теперь осталось дело за малым...

//назовем пару различных вершин дерева двойниками,если их значения и уровни совпадают.найти 
//всех двойников в данном целочисленном бинарном дереве
#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<<"введите текущий узел";
    cin>>leaf->d;
    cout<<leaf->d<<" имеет левое поддерево?";
    cin>>key;
    if (key==1)
    {
        (Top)=new node;
        leaf->l=Top;
        MakeSubTrees(Top);
    }
    else
        leaf->l=NULL;
    cout<<leaf->d<<" имеет правое поддерево?";
    cin>>key;
    if (key==1)
    {
        (Top)=new node;
        leaf->r=Top;
        MakeSubTrees(Top);
    }
    else
        leaf->r=NULL;
}
// обход в глубину
void WayUpDown(node *Top)
{ 
if (Top==NULL)
return;
cout<<Top->d;
WayUpDown(Top->l);
WayUpDown(Top->r);
}

//создание дерева
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;
        ViewTree(Top->r,level+1);
    }
}

//*************************** ОЧЕРЕДЬ ******************
struct QUEUE //структура очередь
{
    node *info;
    QUEUE *next;
};

int EmptyQ(QUEUE *first) //проверка пустоты очереди
{
    if (first==NULL)
    return 1;
    else
    return 0;
}
 
void AddQ(QUEUE **first,QUEUE **last,node *elem) //добавление элемента
{
	
    QUEUE *tmp = new QUEUE;
    tmp->info=elem; //Временное запоминание принятого параметра 
    tmp->next=NULL; //Указание, что следующее звено новосозданной структуры пока пустое

  
        (*last)->next=tmp; //Указание, что следующее звено списка это новосозданная структура
        *last=tmp;    
        if(EmptyQ(*first))*first=(*last)=tmp;
        
        //cout<<"ELEM D"<<elem->d<<endl;
}

void DelQ(QUEUE **first, node **elem) //удаление из очереди
{
	if (first!=NULL)  //Если список не пустой
    {
        QUEUE *temp= *first; //Обращаемся к началу списка с помощью вспомогательного указателя
       // cout<<"ЭЛЕМЕНТ "<<(*first)->info->d<<" ВЫШЕЛ"<<endl;
       *elem=(*first)->info;
        *first=(*first)->next; //Сдвиг начала списка
        delete temp; //Освобождение памяти от предыдущего звена списка
    }
    
}

void ShowQ(QUEUE *first) //просмотр очереди
{
    QUEUE *tmp=first;
    while(tmp!=NULL)
    {
        cout<<tmp->info->d<<endl;
        tmp=tmp->next;
    }
}

void Obhod(node *Top)
{
QUEUE *first, *last;

    if (!Top)  return;
    
    first= new QUEUE;
    first->next=NULL;
    first->info=Top;
    cout<<first->info->d;
    node *curr;
    last=first;
    //addQ(Top);
    while (!EmptyQ(first)) {
        
        //node *curr = DelQ(&first);
        DelQ(&first,&curr);
        cout<<"--------------------------";
        cout <<endl<< "VERSH = "<<curr->d<<endl;
      // printf("%d ", curr->d);
        if ((curr->l)!=NULL){
            AddQ(&first,&last,curr->l);
            cout<<" L = "<<curr->l->d;
            }
        if (curr->r){
            AddQ(&first,&last,curr->r);
            cout<<" R = "<<curr->r->d<<endl;
            
       }
        
        cout<<endl; }
}


int main()
{
 
node *Top;
 MakeTree(&Top);
 Obhod(Top);

 
//WayUpDown(Top); 



    return 0;
}

входная строка
1 1 2 1 4 0 0 1 5 0 0 1 3 1 6 0 0 1 7 0 0
для дерева
1
2 3
4 5 6 7

[fkty]

а где идет проверка двойников?они же не выводятся?

[SaLoKiN]

Сообщение от fkty

а где идет проверка двойников?они же не выводятся?

я же сказал что чуть еще нужно

реализован обход в ширину. теперь осталось дело за малым...