创建1 2 3 4 5 6 7二进制排序树

全部展开

typedef enum {ERROR, OK, UNINITED}status;
typedef int ElemType;

typedef struct BiTree
{
	struct BiTree *left, *right;
	ElemType data;
}BiTree;

status CreateBiTree(BiTree **tree, ElemType *arr, int n)
{
	int found, i;
	BiTree *parent, *node;

	InitBiTree(tree);
	for (i = 0; i < n; i++)
	{
		searchNode(*tree, arr[i], &parent, &found);
		if (found)
			return ERROR;

		node = malloc(sizeof(BiTree));
		if (node == NULL)
			return ERROR;
		node->data = arr[i];
		node->left = node->right = NULL;

		if (*tree == NULL)
			*tree = node;
		else if (parent->data > arr[i])
		{
			if (parent->left && parent->left->data > arr[i])
				node->right = parent->left;
			else
				node->left = parent->left;
			parent->left = node;
		}
		else
		{
			if (parent->right && parent->right->data > arr[i])
				node->right = parent->right;
			else
				node->left = parent->right;
			parent->right = node;
		}
	}
	return OK;
}

BiTree *searchNode(BiTree *tree, ElemType data, BiTree **parent, int *found)
{	
	BiTree *ptemp = NULL;

	while (tree != NULL && tree->data != data)
	{
		ptemp = tree;
		if (data > tree->data)
			tree = tree->right;
		else
			tree = tree->left;
	}
	if (tree != NULL && tree->data == data)
		*found = 1;
	else
		*found = 0;

	*parent = ptemp;
	return tree;
}

这是用于创建二进制排序树的代码. 调用CreateBiTree创建一个二进制排序树. 第一个参数是一个指向树根的指针. 声明一个BiTree *类型并将其传递给它的地址. 第二个参数是数组，即您的1 2 3 4 5 6 7，第三个参数是数组元素的数量.

顺便说一句创建二叉排序树，您遇到的情况恰好是二进制排序树效率最低创建二叉排序树，而创建的结果是链. 在这种情况下，使用自平衡二叉树（例如AVL，红黑树）会更有效.

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-149390-1.html