v2_0

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <conio.h>
#include <math.h>
#define radix 10
#pragma warning(disable:4996)

char array[20][120] = { NULL }; //массив для дерева
int length;                 //длина пути
int i = 0, n = 0;
int m[10];

struct tree
{
	int info;                //значение элемента
	struct tree* left;       //левый "сын"
	struct tree* right;      //правый "сын"
};

struct tree* root;                                                     //начальная вершина дерева
struct tree* stree(struct tree* root, struct tree* r, int info); //добавление элемента в дерево
struct tree* dtree(struct tree* root, int key);                  //удаление элемента из дерева
void printtree(struct tree* root, int Len);                      //печать дерева в графическом режиме
void   inorder(struct tree* root, int i, int& max);                           //симметричный обход дерева
void   WriteArray(int step, int lvl, struct tree* root);        //запись элементов в массив строк

void main()
{
	int choose = -1;
	root = NULL; //инициализация корня дерева

	  //вывод меню
	while (choose != 5)
	{
		printf("1. Add element to tree\n");
		printf("2. Print a tree structure\n");
		printf("3. Max depth\n");
		printf("4. Exit\n");
		printf("Your choise: ");
		scanf("%d", &choose);
		printf("\n");

		switch (choose)
		{
		case  1: {
			int value;
			printf("Enter integer value: ");
			scanf("%d", &value);
			root = stree(root, root, value);
			break;
		}
		case  2: {printtree(root,0);  break; }
		case  3: {
			int max = 0;
			inorder(root, 0, max);
			printf("max= %d\n", max);
			break; }
		default: break;
		}
	}
	_getch();
}
//
//Добавление элемента в дерево
//struct tree *root - корень дерева
//struct tree *r    - вр. "корень"
//int info - вносимый элемент
struct tree* stree(struct tree* root, struct tree* r, int info)
{
	//если исходный элемент пуст, то...
	if (!r)
	{
		//выделяем память под новый элемент
		r = (struct tree*)malloc(sizeof(struct tree));
		//если нет доступной памяти, то вывод ошибки
		if (!r)
		{
			printf("Не хватает памяти\n");
			exit(0);
		}
		//если все прошло успешно, то записываем данные
		r->left = NULL; //левая вершина пустая
		r->right = NULL; //права вершина пустая
		r->info = info; //заносим данные в корень
		//если "главный" корень пуст, то на его месте будет наш новый элемент
		if (!root) return r;
		//иначе продвигаемся по дереву, а затем делаем "внос" вершины
		if (info < root->info) root->left = r;
		else root->right = r;
		return r;
	}

	//продвижение по дереву слева, чтобы занести элемент
	if (info < r->info)
		stree(r, r->left, info);
	//продвижение по дереву справа, чтобы занести элемент
	else
		stree(r, r->right, info);

	return root;
}


//Удаление элемента из дерева
//struct tree *root - корень дерева
//int key - удаляемый элемент
struct tree* dtree(struct tree* root, int key)
{
	struct tree* p, * p2;

	//если дерево пустое, то поиск невозможен
	if (!root) return root;
	//удаление корня
	if (root->info == key)
	{
		//это означает пустое дерево
		if (root->left == root->right)
		{
			free(root);
			return NULL;
		}
		//или если левое поддерево пустое
		else if (root->left == NULL)
		{
			p = root->right;
			free(root);
			return p;
		}
		//или если правое поддерево пустое
		else if (root->right == NULL)
		{
			p = root->left;
			free(root);
			return p;
		}
		//или у нас имеются оба поддерева
		else
		{
			p2 = root->right;
			p = root->right;
			while (p->left) p = p->left;
			p->left = root->left;
			free(root);
			return p2;
		}
	}
	if (root->info < key) root->right = dtree(root->right, key);
	else root->left = dtree(root->left, key);
	return root;
}


//Печать дерева в графическом режиме
//struct tree *root - корень дерева
void printtree(struct tree* root, int Len)
{
	if (root != NULL)
	{
		printtree(root->right, Len + 1);
		for (int i = 0; i < Len; i++)
			printf("    ");
		printf("%2d\n", root->info);
		printtree(root->left, Len + 1);
	}
}

//Вычисление максимальной глубины дерева
void inorder(struct tree* root, int i, int& max)
{
	//если дерево пустое, то обход невозможен
	if (!root) return;
	//иначе начинаем обход
	inorder(root->left, i + 1, max);
	if (root->left == NULL)
	{
		if (root->right == NULL) {
			if (max < i)
				max = i;
		}
	}
	inorder(root->right, i + 1, max);
}