2-3-4 strom v C – C / C++ – Fórum – Programujte.com

Dobrý den, 

za úkol mám naprogramovat 2-3-4 strom, vkládat postupně 100, 300, 1000, 3000, 10000, 30000, 100000 prvků a vypsat následující věci: 

- počet uložených čísel
- průměrný počet čísel uložených v jednom uzlu na 2 desetinná místa
- výšku stromu
- na 2 desetinná místa hodnotu:  výška_stromu / log2(počet_uložených_čísel)

Zde jsou pseudokody:

https://www.dropbox.com/s/94c2vlx8v1x533y/2-3-4.pdf

A zde můj výtvor:

// Alm_Zapocet_2-3-4-tree.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int pocet_uzlu = 0;
int static counter = 0;

double logaritmus2 (int n)
{

    double x;

    x=(log(double(n)))/(log(double(2)));
    return x;
}

typedef struct Node
{
	int order;
	int item[3];
	struct Node *child[4];
	
}Uzel;



Uzel *Create_Node (int x, Uzel * v, Uzel * w)
{
	Uzel *u = (Uzel*)malloc(sizeof(Uzel));

	pocet_uzlu++;

	u->order = 2;
	u->item[0] = x;
	u->child[0] = v;
	u->child[1] = w;
	u->child[2] = NULL;
    u->child[3] = NULL;

	return u;
}

Uzel * Split_Node (Uzel * u, Uzel * v)
{
	int i;

	if (v == NULL)
	{
		u->child[0] = Create_Node(u->item[0], u->child[0], u->child[1]);
		u->child[1] = Create_Node(u->item[2], u->child[2], u->child[3]);
		
		u->order = 2;
		u->item[0] = u->item[1];
		return u;
	}

	i = v->order - 1;

	while ((i > 0) && (u->item[1] < v->item[i-1]))
	{
		v->item[i] = v->item[i-1];
		v->child[i+1] = v->child[i];
		i--;
	}

	v->item[i] = u->item[1];
	v->child[i] = u;
	u->order = 2;
	v->child[i+1] = Create_Node(u->item[2], u->child[2], u->child[3]);
	//pocet_uzlu++;
	v->order = v->order + 1;
	return v;
}


bool Insert(Uzel **Tree, int x)
{
	Uzel *u = *Tree;
	

	int i, j;

	if (u == NULL)
	{
		*Tree = Create_Node(x, NULL, NULL);
		//pocet_uzlu++;
		return true;
	}

	Uzel *v = NULL;
	while (true)
	{
		if (u->order == 4)
		{
			u = Split_Node(u, v);
			
		}

		i = 0;

		while ((i < (u->order - 1)) && (x >= u->item[i]))
		{
			if (x == u->item[i])
			{
				return false;
			}

			i++;
		}

		if (u->child[i] != NULL)
		{
			v = u;
			u = u->child[i];
		}
		else
		{
			j = u->order - 1;

			while (j > i)
			{
				u->item[j] = u->item[j-1];
				j--;
			}

			u->item[i] = x;

			u->order = u->order + 1;
			return true;
				
		}
	}
}



void Inorder_Traversal (Uzel * Tree)
{
	int i;
	
	if (Tree == NULL)
	{
		return;
	}

	Inorder_Traversal(Tree->child[0]);

	i = 0;

	do
	{ 
		if ((counter < 200) || (counter > 18))
		{
			printf("%i ", Tree->item[i]);
			counter++;
			i++;
			Inorder_Traversal(Tree->child[i]);
		}
		else
		{
			i++;
			counter++;	
			Inorder_Traversal(Tree->child[i]);
		}
		
		
	} while (i < (Tree->order -1));
}

int Height (Uzel * koren)
{
	if (koren == NULL)
	{
		return -1;
	}
	else
	{
		return Height (koren->child[0]) + 1;
	}
}

void vystup (int n)
{
	int i;
	Uzel *Tree = NULL;


	for (i = 0; i <= n; i++)
	{
		Insert(&Tree, rand());
	}

	int vyska = Height(Tree);

	printf("|%6d |", n);
	printf(" %4.2f |", double(n)/double(pocet_uzlu));
	printf("%5d |",vyska);
	printf("%5.2f |", double(vyska)/logaritmus2(n));
	printf("\n");
	
}



int _tmain()
{
	printf("\n\t2-3-4 Tree - ALM2\n\n");
	printf("  Pocet  Prumer  Vyska  Podil\n");
    printf("------------------------------\n");

	vystup(100);

	vystup(300);

	vystup(1000);

	vystup(3000);

	vystup(10000);

	vystup(30000);

	vystup(50000);

	vystup(100000);
	printf("------------------------------\n");

	int i;
	Uzel * Tree = NULL;
	for (i = 0; i <= 20; i++)
	{
		Insert(&Tree, rand()%100);
	}

	Inorder_Traversal(Tree);

	

	system("pause");
	return 0;
}

Dole zkouším vložit 20 prvků do stromu, ale vypisuji mi to pouze 19 prvků. 

Předem děkuji za radu