Ćwiczenia 11 - Struktury drzewiaste (2 pkt termin: 20:00:00 pierwsza środa po zajęciach)

/*poniższe wyjście jest tylko przykładem, program generuje losowe drzewo*/
STRUCT-TREE T
INIT(T) /*inicjuje zmienne*/
MAKE-TREE(T,10)
PRINT-TREE(T) //drzewo losowe przykładowe drzewo poniżej
//			1
//		3
//			2
//	6
//		7
//			4
//5
//		10
//	9
//		8
PREORDER-TREE(T) //5 6 3 1 2 7 4 9 10 8
INORDER-TREE(T) //1 3 2 6 7 4 5 10 9 8
POSTORDER-TREE(T) //1 2 3 4 7 6 10 8 9 5
CLEAR(T) /*zwalnia pamięć*/
PRINT-TREE(T) //

STRUCT-TREE
	root = NIL

STRUCT-NODE
	key = NIL
	p = NIL
	left = NIL
	right = NIL

MAKE-TREE(T,n)
	for i = 1 to n
		new.key = rand(1,100) //nowy NODE
		x = T.root
		p = NIL
		while x ≠ NIL
			p = x
			r = rand(1,2)
			if r = 1
				x = x.left
			else
				x = x.right
		new.p = p
		if T.root = NIL
			T.root = new
		else
			if r = 1
				p.left = new
			else
				p.right = new

PREORDER-TREE(T)
	PREORDER-WALK(T.root)

PREORDER-WALK(x)
	if x ≠ NIL
		write x.key
		PREORDER-WALK(x.left)
		PREORDER-WALK(x.right)

INORDER-TREE(T)
	INORDER-WALK(T.root)

INORDER-WALK(x)
	if x ≠ NIL
		INORDER-WALK(x.left)
		write x.key
		INORDER-WALK(x.right)

POSTORDER-TREE(T)
	POSTORDER-WALK(T.root)

POSTORDER-WALK(x)
	if x ≠ NIL
		POSTORDER-WALK(x.left)
		POSTORDER-WALK(x.right)
		write x.key

PRINT-TREE(T)
	WALK-TREE(T.root,0)
WALK-TREE(x,d)
	if x ≠ NIL
		WALK-TREE(x.left,d + 1)
		for i = 1 to d
			write " "
		write x.key
		WALK-TREE(x.right,d + 1)