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

创建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、红黑树）效率比较高。