최소 노드, H 높이의 AVL 트리를 생성하는 프로그램

1294 단어
데이터 구조와 알고리즘 분석 - c 언어 설명 연습 4.30
재미있네.4.16 연습의 결론을 썼다.추이와 귀속을 결합하여 무작위 avl 트리를 생성합니다
#include"fatal.h"
#include<stdlib.h>

typedef int ElementType;

struct AvlNode;
typedef struct AvlNode *Position;
typedef struct AvlNode *AvlTree;

struct AvlNode {
	ElementType element;
	AvlTree left;
	AvlTree right;
	int isDeleted;
	int height;
};

int RandInt(int i, int j) {
	int temp;
	temp = (int)(i + (1.0*rand() / RAND_MAX)*(j - i));
	return temp;
}

AvlTree makeRandomAVLTree(int H) {
	if (H >= 0) {
		AvlTree t = malloc(sizeof(struct AvlNode));
		if (t == NULL)
			Error("OUT OF MEMORY");
		t->left = makeRandomAVLTree(H - 1);
		t->right = makeRandomAVLTree(H - 2);

		if (t->left == NULL&&t->right == NULL) {
			t->element = rand();
		}
		else if (t->left == NULL)
			t->element = RandInt(0, t->right->element);
		else if (t->right == NULL)
			t->element = RandInt(t->left->element, RAND_MAX);
		else
			t->element = RandInt(t->left->element, t->right->element);

		return t;
	}
	return NULL;
}

void dir(AvlTree t) {
	if (t) {
		printf("%d ", t->element);
		dir(t->left);
		dir(t->right);
	}
}

int main() {
	AvlTree t = makeRandomAVLTree(9);
	dir(t);
}

좋은 웹페이지 즐겨찾기