#include <stdio.h>
#include <stdlib.h>
#include <time.h>
/*
*avl树数据结构及相关操作
*/
/*内存释放*/
#define xfree(p) free(p)
struct AVLTree
{
unsigned int nData /*存储数据*/
struct AVLTree* pLeft /*指向左子树*/
struct AVLTree* pRight /*指向右子树*/
int nHeight /*树的平衡度*/
}
/*申请内存*/
inline void *xalloc(int size)
{
void *p
p = (void *)malloc(size)
/*申请失败*/
if(p == NULL)
{
printf("alloc error\n")
exit(1)
}
return p
}
int Max(int a, int b)
{
return (a >b ? a : b)
}
/*返回节点的平衡度*/
int Height(struct AVLTree* pNode)
{
if (NULL == pNode)
return -1
return pNode->nHeight
}
/********************************************************************
pNode pNode->pLeft
/ \
pNode->pLeft ==>pNode
\ /
pNode->pLeft->pRight pNode->pLeft->pRight
*********************************************************************/
struct AVLTree* SingleRotateWithLeft(struct AVLTree* pNode)
{
struct AVLTree* pNode1
pNode1 = pNode->pLeft
pNode->pLeft = pNode1->pRight
pNode1->pRight = pNode
/*结点的位置变了, 要更新结点的高度值*/
pNode->nHeight = Max(Height(pNode->pLeft), Height(pNode->pRight)) + 1
pNode1->nHeight = Max(Height(pNode1->pLeft), pNode->nHeight) + 1
return pNode1
}
/********************************************************************
pNode pNode->pRight
\ /
pNode->pRight ==>pNode
/ \
pNode->pRight->pLeft pNode->pRight->pLeft
*********************************************************************/
struct AVLTree* SingleRotateWithRight(struct AVLTree* pNode)
{
struct AVLTree* pNode1
pNode1 = pNode->pRight
pNode->pRight = pNode1->pLeft
pNode1->pLeft = pNode
/*结点的位置变了, 要更新结点的高度值*/
pNode->nHeight = Max(Height(pNode->pLeft), Height(pNode->pRight)) + 1
pNode1->nHeight = Max(Height(pNode1->pRight), pNode->nHeight) + 1
return pNode1
}
struct AVLTree* DoubleRotateWithLeft(struct AVLTree* pNode)
{
pNode->pLeft = SingleRotateWithRight(pNode->pLeft)
return SingleRotateWithLeft(pNode)
}
struct AVLTree* DoubleRotateWithRight(struct AVLTree* pNode)
{
pNode->pRight = SingleRotateWithLeft(pNode->pRight)
return SingleRotateWithRight(pNode)
}
struct AVLTree* insert_tree(unsigned int nData, struct AVLTree* pNode)
{
if (NULL == pNode)
{
pNode = (struct AVLTree*)xalloc(sizeof(struct AVLTree))
pNode->nData = nData
pNode->nHeight = 0
pNode->pLeft = pNode->pRight = NULL
}
else if (nData <pNode->nData)/*插入到左子树中*/
{
pNode->pLeft = insert_tree(nData, pNode->pLeft)
if (Height(pNode->pLeft) - Height(pNode->pRight) == 2)/*AVL树不平衡*/
{
if (nData <pNode->pLeft->nData)
{
/*插入到了左子树左边, 做单旋转*/
pNode = SingleRotateWithLeft(pNode)
}
else
{
/*插入到了左子树右边, 做双旋转*/
pNode = DoubleRotateWithLeft(pNode)
}
}
}
else if (nData >pNode->nData)/*插入到右子树中*/
{
pNode->pRight = insert_tree(nData, pNode->pRight)
if (Height(pNode->pRight) - Height(pNode->pLeft) == 2)/*AVL树不平衡*/
{
if (nData >pNode->pRight->nData)
{
/*插入到了右子树右边, 做单旋转*/
pNode = SingleRotateWithRight(pNode)
}
else
{
/*插入到了右子树左边, 做双旋转*/
pNode = DoubleRotateWithRight(pNode)
}
}
}
pNode->nHeight = Max(Height(pNode->pLeft), Height(pNode->pRight)) + 1
return pNode
}
/*中序遍历打印树的所有结点, 因为左结点 <父结点 <右结点, 因此打印出来数据的大小是递增的*/
void print_tree(struct AVLTree* pRoot)
{
if (NULL == pRoot)
return
static int n = 0
print_tree(pRoot->pLeft)
//printf("[%d]nData = %u\n", ++n, pRoot->nData)
printf(" %u ", pRoot->nData)
print_tree(pRoot->pRight)
}
/*先序遍历打印树的所有结点 */
void print_tree_first(struct AVLTree* pRoot)
{
if (NULL == pRoot)
return
static int n = 0
printf(" %u ", pRoot->nData)
//printf("[%d]nData = %u\n", ++n, pRoot->nData)
print_tree_first(pRoot->pLeft)
print_tree_first(pRoot->pRight)
}
/*删除树*/
void delete_tree(struct AVLTree** ppRoot)
{
if (NULL == ppRoot || NULL == *ppRoot)
return
delete_tree(&((*ppRoot)->pLeft))
delete_tree(&((*ppRoot)->pRight))
xfree(*ppRoot)
*ppRoot = NULL
}
int main()
{
int i,j
AVLTree* pRoot = NULL
printf("平衡二叉树演示：请输入若干个正整数，以 -1 结束：\n")
j=0
for (i = 1j != -1++i)
{
printf("\n请输入第%d个数， -1代表结束：",i)
scanf("%d", &j)
if(j == -1)break
pRoot = insert_tree(j, pRoot)
printf("\n插入第%d个元素后，\n中序遍历输出：",i )
print_tree(pRoot)
printf("\n 先序遍历输出：")
print_tree_first(pRoot)
}
printf("\n 再见！")
delete_tree(&pRoot)
return 0
}
这是我前几天写的，看了下应该可以满足要求，由于测试还不够，不知道有没有bug。第一点你自己改改，2、3都达到了，至于第四，不用说肯定是平衡了的二叉树相对查找效率要高一些，平衡，随机插入，打乱插入等操作都是为了防止最差情况的线性树的出现。测试的话用rand()生成随机数外加time.h里的几个函数，配合使用下就出来了。
#include <stdio.h>
#include <stdlib.h>
// binary search tree
typedef struct BST
{
int data
struct BST* lhs
struct BST* rhs
}BST
// 插入一个节点
BST* BSTInsertNode(BST* root, int elem)
{
BST* node
node = (BST*)malloc(sizeof(BST))
node->data = elem
node->lhs = node->rhs = 0
if(!root)
return node
while(1)
{
if(node->data <root->data)
{
if(root->lhs)
root = root->lhs
else
{
root->lhs = node
return root->lhs
}
}
else
{
if(root->rhs)
root = root->rhs
else
{
root->rhs = node
return root->rhs
}
}
}
}
// 获得父节点
BST* BSTGetParentNode(BST* root, BST* node)
{
if(root == node)
return 0
if(root->lhs &&node->data <root->lhs->data)
return BSTGetParentNode(root->lhs, node)
else if(root->rhs &&node->data >root->rhs->data)
return BSTGetParentNode(root->rhs, node)
else
return root
}
// 删除一个节点
BST* BSTDeleteNode(BST* root, BST* node)
{
BST* parent
BST** whichNode
BST* temp
if(root != node)
{
parent = BSTGetParentNode(root, node)
whichNode = parent->lhs == node ? &parent->lhs : &parent->rhs
}
else
whichNode = &root
if(!node->lhs &&!node->rhs)
*whichNode = 0
else if(!((node->lhs ? 1 : 0) ^ (node->rhs ? 1 : 0)))
*whichNode = node->lhs ? node->lhs : node->rhs
else
{
temp = node->rhs
while(temp->lhs)
temp = temp->lhs
temp->lhs = node->lhs
*whichNode = node->rhs
}
free(node)
return *whichNode
}
// 删除树
void BSTDeleteTree(BST* node)
{
if(node)
{
BSTDeleteTree(node->lhs)
BSTDeleteTree(node->rhs)
free(node)
}
}
// 建造树，从数组构造
BST* BSTBuildTree(int* beg, int* end)
{
BST* root
if(beg >= end)
return 0
root = (BST*)malloc(sizeof(BST))
root->data = *beg++
root->lhs = root->rhs = 0
while(beg != end)
BSTInsertNode(root, *beg++)
return root
}
// 查找节点
BST* BSTSearchNode(BST* root, int elem)
{
if(root)
{
if(elem <root->data)
return BSTSearchNode(root->lhs, elem)
else if(elem >root->data)
return BSTSearchNode(root->rhs, elem)
else
return root
}
else
return 0
}
// 获得最小值
BST* BSTGetMinimumNode(BST* root)
{
while(root->lhs)
root = root->lhs
return root
}
// 获得最大值
BST* BSTGetMaximumNode(BST* root)
{
while(root->rhs)
root = root->rhs
return root
}
// 前序遍历
void BSTPreorderTraverse(BST* node)
{
if(node)
{
printf("%d ", node->data)
BSTPreorderTraverse(node->lhs)
BSTPreorderTraverse(node->rhs)
}
}
// 中序遍历
void BSTInorderTraverse(BST* node)
{
if(node)
{
BSTInorderTraverse(node->lhs)
printf("%d ", node->data)
BSTInorderTraverse(node->rhs)
}
}
// 后序遍历
void BSTPostorderTraverse(BST* node)
{
if(node)
{
BSTPostorderTraverse(node->lhs)
BSTPostorderTraverse(node->rhs)
printf("%d ", node->data)
}
}
// 获得前继值
BST* BSTGetPredecessor(BST* root, BST* node)
{
BST* predecessor
BST* rightCld
if(node->lhs)
return BSTGetMaximumNode(node->lhs)
predecessor = rightCld = node
while((predecessor = BSTGetParentNode(root, predecessor)))
if(predecessor->rhs == rightCld)
return predecessor
else
rightCld = predecessor
return 0
}
// 获得后继值
BST* BSTGetSuccessor(BST* root, BST* node)
{
BST* successor
BST* leftCld
if(node->rhs)
return BSTGetMinimumNode(node->rhs)
successor = leftCld = node
while((successor = BSTGetParentNode(root, successor)))
if(successor->lhs == leftCld)
return successor
else
leftCld = successor
return 0
}
// 获得树高
int BSTGetTreeHeight(BST* root)
{
int l
int r
if(root)
{
l = BSTGetTreeHeight(root->lhs)
r = BSTGetTreeHeight(root->rhs)
return 1 + (l >r ? l : r)
}
else
return -1
}
// 计算子节点数
int BSTGetSubtreeNodeNum(BST* node)
{
if(node)
return BSTGetSubtreeNodeNum(node->lhs)
+ BSTGetSubtreeNodeNum(node->rhs)
+ 1
else
return 0
}
// 用于打乱数组，交换
inline void Swap(int* a, int* b)
{
int temp
temp = *a
*a = *b
*b = temp
}
// 用于打乱数组，qsort的比较用过程
inline int CMP(const void* lhs, const void* rhs)
{
return *(const int*)lhs - *(const int*)rhs
}
// 数组有序?
int IsOrdered(int* beg, int* end)
{
int attri
int cmpVal
if(beg >= end)
return 0
if(end - beg <= 2)
return 1
if(*beg <*(beg + 1))
attri = 1
else
attri = 0
cmpVal = *beg++
while(++beg != end)
{
if(attri)
{
if(cmpVal >*beg)
return 0
}else
{
if(cmpVal <*beg)
return 0
}
}
return 1
}
// 高层次打乱数组
void HighlyUnorderArray(int* beg, int* end)
{
int* mid = beg + (end - beg)/2
int* folk
if(!IsOrdered(beg, end))
qsort(beg, end - beg, sizeof(int), CMP)
if((mid - beg) &1)
Swap(beg++, mid)
folk = beg + 2
while(folk <mid)
{
Swap(beg++, folk++)
Swap(beg++, folk++)
}
folk = mid + 2
while(folk <end)
{
Swap(folk, folk - 1)
folk += 2
}
}
// 中序遍历结果输出到数组
void BSTInorderWalkToArray(BST* root, int** p)
{
if(root)
{
BSTInorderWalkToArray(root->lhs, p)
**p = root->data
(*p)++
BSTInorderWalkToArray(root->rhs, p)
}
}
// 平衡树，返回平衡好的新树
BST* BSTBalanceTree(BST* root)
{
int size = BSTGetSubtreeNodeNum(root)
int* a = (int*)malloc(sizeof(int) * size)
int* end = a
BST* balancedTree
BSTInorderWalkToArray(root, &end)
HighlyUnorderArray(a, end)
balancedTree = BSTBuildTree(a, end)
free(a)
return balancedTree
}
int main()
{
int a[] = {5,6,3,7,9,8,1,0,4,2}
int c[] = {50,17,76,9,23,54,14,19,72,12,67}
BST* bstTree = BSTBuildTree(a, a + sizeof(a)/sizeof(a[0]))
BSTPreorderTraverse(bstTree)
putchar('\n')
BSTInorderTraverse(bstTree)
putchar('\n')
BSTPostorderTraverse(bstTree)
printf("\n\n")
BST* balancedTree = BSTBalanceTree(bstTree)
printf("%d %d\n", BSTGetTreeHeight(bstTree), BSTGetTreeHeight(balancedTree))
BSTDeleteTree(bstTree)
BSTDeleteTree(balancedTree)
}
