бинарное дерево с прямым обходом

[Вечный_студент]

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

#include <iostream>
#include <ctime>
#include <cstdlib>
 
using namespace std;
 
template<class T> struct vertex
{
	T value;
	vertex* left;
	vertex* right;
};
 
template<class T> void insert(vertex<T>* head, T element)
{
	if(head->value == element) 
		return;
	else
	{
		if(head->value < element)
		{
			if(head -> left == NULL)
			{
				head -> left = new vertex<T>;
				head -> left -> value = element;
				head -> left -> left = NULL;
				head -> left -> right = NULL;
			}
			else
			{
				head = head->left;
				insert(head,element);
			}
		}
		else
			if(head->value > element)
			{
				if(head -> right == NULL)
				{
					head -> right = new vertex<T>;
					head -> right -> value = element;
					head -> right -> left = NULL;
					head -> right -> right = NULL;
				}
				else
				{
					head = head->right;
					insert(head,element);
				} 
			}
	}
}

template<typename T> int find (vertex<T>* head, T element, int *l)
{
	if(head==NULL)
	{
		*l=0;
		return *l;
	}
	if(head->value==element) 
		return *l;
	if (head->left) 
	{
		*l+=1;
		find(head->left, element, l);
	}
	if (head->right) 
	{
		l+=1; 
		find(head->right, element, l);
	}
}
 
template<typename T> void show_bin_tree (vertex<T>* head, int n) 
{ 
	if (head->left) 
		show_bin_tree(head->left, n+1); 

	for (int i = 0; i < n; i++) 
		cout << " "; 
	cout << head->value << '\n'; 
	
	if (head->right) 
		show_bin_tree(head->right, n+1); 
}
 
int main()
{
	cout<<"programma postroinia binarnogo dereva\n"<<endl;
	cout<<"c ego pramim obxodom"<<endl;
	vertex<char>* head = new vertex<char>;
	head->left = NULL;
	head->right = NULL;
	srand(time(NULL));
	head->value = (char)(rand()%('z'-'a')+'a');
	
	const int max=9;
	char arr[max], chr; int n=0;
	bool b;
	
	while (n<9)
	{
		b=true;
		chr=(char)(rand()%('z'-'a')+'a');
		for (int i=0; i<=n; i++)
			if (arr[i]==chr)
				b=false;
		if (b)
		{
			arr[n]=chr;
			++n;
		}
	}
	
	for(int i = 0; i<9; i++)
		insert(head,arr[i]);
 
	cout << endl;
	int l=0;
	cout << "viviod dereva\n"<<endl;
	show_bin_tree (head, l);
	cout << "vvidite iskomii simvol" <<endl;
	char ch;
	cin >> ch;
 
	if(find(head, ch, &l))
		cout << "Element found " << l;
	else 
		cout << "Element not found";
 
	system("pause");
	return 0;
}

вот что есть. как бы мне исправить код подскажите?

[alezha]

Что именно неправильно у Вас? не строит дерево? не находит элемент? или что?

[Вечный_студент]

не ищет элемент

и дерево не сбалансированное. судя по всему строит только 1 ветку(или я ошибаюсь)

[alezha]

на первом курсе писал лабу по дереву. Думаю поможет.

#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#include <locale.h>
struct der
{
	int inf;
	der *l,*r; // указатель на левое и правое поддерево
};
void del(der **,int );
der *sozd(der *);
void add(der *);
void out_tree(der *, int );
void inorder(struct der *);
void main(void)
{
	setlocale(LC_ALL,"Russian");
	der *dr;
	dr=NULL; // адрес корня бинарного дерева
	system("cls");
	int st;
	do
	{
		while(1)
		{
			puts("вид операции: \n 1-создать дерево");
			puts(" 2-Обойти дерево в симметричном порядке");
			puts(" 3-Вывод в виде перевернутого дерева");
			puts(" 4-добавление элементов в дерево");
			puts(" 5-удаление любого элемента из дерева");
			puts(" 6-выход");
			fflush(stdin);
			switch(getch())
			{
			case '1': dr=sozd(dr); break;
			case '2': inorder(dr); break;
			case '3': out_tree(dr,0); getch(); break;
			case '4': add(dr); break;
			case '5': 
				printf("\n Введите число для удаления");
	fflush(stdin);
	scanf("%d",&st);
	del(&dr,st);   break;
			case '6': return;
			}
			system("cls");
		}
		printf("Повторить y/n");
		fflush(stdin);
	}
	while(getch()=='y');
}
der *sozd(der *dr)  // создание бинарного дерева
{
	if (dr)
	{
		puts("Бинарное дерево уже создано");
		return (dr);
	}
	if (!(dr=(der*)calloc(1,sizeof(der))))
	{
		puts("Нет свободной памяти");
		getch();
		return NULL;
	}
	puts("Введите информацию в корень дерева");
	fflush(stdin);
	scanf("%d",&dr->inf);
	return dr;
}
void add(der *dr)  // функция добавления узлов в бинарное дерево
{
	der *dr1,*dr2;
	int k; // результат сравнения двух строк
	int ind, st;
	if (!dr)
	{
		puts("Нет корня дерева \n");
		getch();
		return;
	}
	do
	{
		puts("Введите информацию в очередной узел дерева (0 - выход)");
		fflush(stdin);
		scanf("%d",&st);
		if(!st) return; // выход в функцию main
		dr1=dr;
		ind=0; // 1 - признак выхода из цикла поиска
		do
		{
			if(!(k=st-dr1->inf))
				ind=1; // для выхода из цикла do ... while
			else
			{
				if (k<0) // введ. строка < строки в анализируемом узле
				{
					if (dr1->l) dr1=dr1->l; // считываем новый узел дерева
					else ind=1; // выход из цикла do ... while
				}
				else // введ. строка > строки в анализируемом узле
				{ 
					if (dr1->r) 
						dr1=dr1->r; // считываем новый узел дерева
					else ind=1; // выход из цикла do ... while
				}
			}
		}
		while(ind==0);
		if (k) // не найден узел с аналогичной информацией
		{
			if (!(dr2=(struct der *) calloc(1,sizeof(struct der))))
			{
				puts("Нет свободной памяти");
				return;
			}
			if (k<0) dr1->l=dr2; // ссылка в dr1 налево
			else dr1->r=dr2; // ............ направо
			dr2->inf=st; // заполнение нового узла dr2
		}
	}
	while(1); // любое условие т.к. выход из цикло по return
}
void del(der **dr,int st)  // функция удаления узла дерева
{
	if(!*dr)
	{
		printf("\n Дерево пустое");
		return;
	}
	if(st<(*dr)->inf) del(&(*dr)->l,st);
	else if(st>(*dr)->inf) del(&(*dr)->r,st);
	else 
	{
		der *lt, *rt;
		lt=(*dr)->l;
		rt=(*dr)->r;
		free(*dr);
		*dr=rt;
		while(*dr)
			dr=&(*dr)->l;
		*dr=lt;
	}
}
void out_tree(der *dr1, int level) 
{
	if(dr1)							//пока dr не равен нулю
	{
		out_tree(dr1->r,level+1);
		for(int i=0; i<level; i++)	//обозначение уровня
			printf("        ");
		printf("   ____\n");
		for(int i=0; i<level; i++)
			printf("        ");
		printf("->| %2d |\n",dr1->inf);
		for(int i=0; i<level; i++)
			printf("        ");
		printf("  |____|\n");
		out_tree(dr1->l,level+1);
	}
	
}
void inorder(struct der *root)
{
  if(!root) return;
  inorder(root->l);
  if(root->inf) printf("%d", root->inf);
  inorder(root->r);
}

[Вечный_студент]

как в консоле язык русский подключить?) плохо транслитом

[alezha]

У меня же все прописано.

setlocale(LC_ALL,"Russian");

[Вечный_студент]

MV C++ 2006 не работает почему то О_о

[alezha]

CharToOem попробуйте. А лучше поставьте новую версию Visual Studio.

[Вечный_студент]

char s[]="Привет всем!";
CharToOem(s,s);
printf("%s\n", s);

так?

и еще такой вопрос. Что изменить, чтобы в дерево можно было записывать буквы?

[alezha]

вроде так.
и для строк:

struct der
{
	char inf[];
	der *l,*r; // указатель на левое и правое поддерево
};