drzewa BST - dodawanie węzła i przechodzenie

Question

Napisałam funkcje, ktora ma dodawac elementy do drzewa a nastepnie funkcje ktora zajmuje sie przechodzeniem drzewa, co jest z nimi nie tak, ze jak uruchamiam program to nic mi sie nie wyswietla?

#include<iostream>
using namespace std;

struct node
{
	node* p;
	node* L;
	node* R;
	int val;
};


void insert_BST(node* root, int x, node* parent = NULL)
{
	if (root == NULL)
	{
		node* e = new node;
		e->val = x;
		e->p = parent;
		e->L = NULL;
		e->R = NULL;
		root = e;
	}
	else
	{
		if (x <= root->val)
			insert_BST(root->L, x, root);
		else
			insert_BST(root->R, x, root);
	}
}

void inorder(node* root)
{
	if (root != NULL)
	{
		inorder(root->L);
		cout << root->val << " ";
		inorder(root->R);
	}
}

int main()
{
	node* root = NULL;
	insert_BST(root, 20);
	insert_BST(root, 11);
	insert_BST(root, 10);
	insert_BST(root, 33);
	insert_BST(root, 15);
	insert_BST(root, 27);
	insert_BST(root, 47);
	insert_BST(root, 35);
	insert_BST(root, 49);
	insert_BST(root, 8);
	insert_BST(root, 2);
	insert_BST(root, 9);
	insert_BST(root, 19);
	insert_BST(root, 14);
	inorder(root);

	return 0;
}

 

Answer 1

Problem jest że przekazujesz do funkcji wskaźnik root. Następnie funkcja robi sobie kopię wskaźnika root wskazując na to samo co oryginalny wskaźnik. Później ustawiasz tą kopię, aby wskazywała na e (Nie jest to oryginalny root!)

Musisz do funkcji przekazać wskaźnik na wskaźnik do node, albo referencję na wskaźnik do node.

Nie polecam c++ ;)

Comments

ajj faktycznie racja dziękuję bardzo :) niestety taki język mamy na zajęciach ;)

---

a mam jeszcze takie pytanko, chcialabym zeby funkcja wyswietlala mi poprzednika danego wezla i dziala poprawnie do momentu, w ktorym chce wyswietlic poprzednika wezla e, ktory jest lewym synem y, tam nie wyswietla mi poprzednika tego wezla tylko jego rodzica (else if (e == y->L) - od tego momentu) :(

void prev(node* e)
{
	if (e->L != NULL)
		max(e->L);
	else
	{
		node* y = e->p;      //y-rodzic e
		if (y != NULL)
		{
			if (e = y->R)
				cout << y->val;
			else if (e == y->L)
			{
				while (y != NULL && e == y->L)
				{
					e = y;
					y = y->p;
				}
					cout << y;
			}
		}
	}
}

 

---

Dwie rzeczy:

if (e = y->R)

W cywilizowanym języku programowania taki zapis byłby niedozwolony.

max(e->L);

Rozumiem, że chodziło o prev(e->L)

Chcesz wyświetlić ścieżkę do lewego dolnego węzła?
Jeżeli tak to najprościej w ten sposób:

void prev(node* e)
{
    if (e->L != NULL){
      cout << e->val;  /// jezeli chcesz odwrócić kolejność to zamień miejscami te 2 linijki
      prev(e->L);
    }
    else
    {
       cout << e->val;
    }
}