头文件（searchTree.h）：
#pragmaonce
#include"binaryTree.h"
//通过Key值查找节点
binaryNode*findNodeByKey(binaryNode*T,intkey);
//取得节点平衡因子
intgetBalanceFactor(binaryNode*T);
//平衡左旋转
binaryNode*leftRotate(binaryNode*T);
//平衡右旋转
binaryNode*rightRotate(binaryNode*T);
//插入节点（平衡二叉查找树），返回新增节点
binaryNode*insertSearchTree(binaryNode*T,intkey,binaryElemType*data);
//删除节点（平衡二叉查找树），返回删除调整后的替换节点
binaryNode*deleteSearchTree(binaryNode*T,intkey);
程序文件（searchTree.c）：
#includestdlib.h
#include"searchTree.h"
//通过Key值查找节点
binaryNode*findNodeByKey(binaryNode*T,intkey)
{
if(!T)returnNULL;
binaryNode*p=T;
//遍历查找
while(p)
{
if(p-key==key)
{
returnp;
}
elseif(p-keykey)
{
p=p-left;
}
else
{
p=p-right;
}
}
returnNULL;
}
//取得节点平衡因子
intgetBalanceFactor(binaryNode*T)
{
if(!T)return0;
intleftHeight=0,rightHeight=0;
//取得左子树的高度
binaryNode*p=T-left;
if(p)leftHeight=heightBinaryList(p);
//取得右子树的高度
p=T-right;
if(p)rightHeight=heightBinaryList(p);
//计算平衡因子
return(leftHeight-rightHeight);
}
//平衡左旋转
binaryNode*leftRotate(binaryNode*T)
{
if((!T)
(!T-right))returnNULL;
//定义待调整的临时节点
binaryNode*bn=T,*parent=bn-parent,*right,*rightChildLeft;
//取得原先的节点位置
intisRight=bn-isRight;
//移除原先的父级节点关系
if(parent)removeBinaryNode(parent,bn);
right=bn-right;
//移除原先的右子树关系
removeBinaryNode(bn,right);
//取得原先右子树的左节点
rightChildLeft=right-left;
if(rightChildLeft)
{
//移除原先右子树的左节点关系
removeBinaryNode(right,rightChildLeft);
//判断原先右子树的右节点是否存在
if(right-right)
{
//建立和原先右子树的左节点之间的关系（右子节点）
addBinaryNode(bn,1,rightChildLeft);
//重新添加为原先右子树的左子节点
addBinaryNode(right,0,bn);
//建立原先父级节点和原先右子树之间的关系
if(parent)addBinaryNode(parent,isRight,right);
returnright;
}
else
{
//重新建立原先右子树的左节点和原先右子树的关系（右子节点）
addBinaryNode(rightChildLeft,1,right);
//重新添加为原先右子树的左节点的左子节点
addBinaryNode(rightChildLeft,0,bn);
//建立原先父级节点和原先右子树的左节点之间的关系
if(parent)addBinaryNode(parent,isRight,rightChildLeft);
returnrightChildLeft;
}
}
else
{
//重新添加为原先右子树的左子节点
addBinaryNode(right,0,bn);
//建立原先父级节点和原先左子树之间的关系
if(parent)addBinaryNode(parent,isRight,right);
returnright;
}
}
//平衡右旋转
binaryNode*rightRotate(binaryNode*T)
{
if((!T)
(!T-left))returnNULL;
//定义待调整的临时节点
binaryNode*bn=T,*parent=bn-parent,*left,*leftChildRight;
//取得原先的节点位置
intisRight=bn-isRight;
//移除原先的父级节点关系
if(parent)removeBinaryNode(parent,bn);
left=bn-left;
//移除原先的左子树关系
removeBinaryNode(bn,left);
//取得原先左子树的右节点
leftChildRight=left-right;
if(leftChildRight)
{
//移除原先左子树的右节点关系
removeBinaryNode(left,leftChildRight);
//判断原先左子树的左节点是否存在
if(left-left)
{
//建立和原先左子树的右节点之间的关系（左子节点）
addBinaryNode(bn,0,leftChildRight);
//重新添加为原先左子树的右子节点
addBinaryNode(left,1,bn);
//建立原先父级节点和原先左子树之间的关系
if(parent)addBinaryNode(parent,isRight,left);
returnleft;
}
else
{
//重新建立原先左子树的右节点和原先左子树的关系（左子节点）
addBinaryNode(leftChildRight,0,left);
//重新添加为原先左子树的右节点的右子节点
addBinaryNode(leftChildRight,1,bn);
//建立原先父级节点和原先左子树的右节点之间的关系
if(parent)addBinaryNode(parent,isRight,leftChildRight);
returnleftChildRight;
}
}
else
{
//重新添加为原先左子树的右子节点
addBinaryNode(left,1,bn);
//建立原先父级节点和原先左子树之间的关系
if(parent)addBinaryNode(parent,isRight,left);
returnleft;
}
}
//插入节点（平衡二叉查找树），返回新增节点
binaryNode*insertSearchTree(binaryNode*T,intkey,binaryElemType*data)
{
if(!T)returnNULL;
//取得二叉树节点的根节点（必须从根节点开始，才能保证平衡）
binaryNode*bn=getBinaryRoot(T),*parent=NULL;
intisRight=0;
//遍历查找
while(bn)
{
parent=bn;
//查找插入位置
if(bn-key==key)
{
//更新二叉树节点的数据内容
setBinaryNodeData(bn,data);
returnbn;
}
elseif(bn-keykey)
{
bn=bn-left;
isRight=0;
}
else
{
bn=bn-right;
isRight=1;
}
}
//插入二叉树的子节点（右：1；左：0）
binaryNode*child=insertBinaryNode(parent,isRight,key);
//设置二叉树节点的数据内容
setBinaryNodeData(child,data);
//定位父级节点
bn=parent;
intfactor;
//遍历平衡因子
while(bn)
{
//取得节点平衡因子
factor=getBalanceFactor(bn);
//父级节点平衡因子变为0，则表示高度不变，结束向上传导
if(factor==0)break;
//父级节点平衡因子变为1或-1，则继续向上传导
if((factor==1)
(factor==-1))
{
bn=bn-parent;
}
elseif(factor1)
{
//取得左子节点平衡因子
factor=getBalanceFactor(bn-left);
//右旋转之前，如果左子节点平衡因子小于0，则需要先对左子树进行左旋转
if(factor0)leftRotate(bn-left);
//平衡右旋转
rightRotate(bn);
//完成调整，则结束向上传导
break;
}
elseif(factor-1)
{
//取得右子节点平衡因子
factor=getBalanceFactor(bn-right);
//左旋转之前，如果右子节点平衡因子大于0，则需要先对右子树进行右旋转
if(factor0)rightRotate(bn-right);
//平衡左旋转
leftRotate(bn);
//完成调整，则结束向上传导
break;
}
}
returnchild;
}
//删除节点（平衡二叉查找树），返回删除调整后的父级替换节点
binaryNode*deleteSearchTree(binaryNode*T,intkey)
{
if(!T)returnT;
//取得二叉树节点的根节点（必须从根节点开始，才能保证平衡）
binaryNode*bn=getBinaryRoot(T);
//遍历查找
while(bn)
{
//查找删除位置
if(bn-key==key)break;
if(bn-keykey)
{
bn=bn-left;
}
else
{
bn=bn-right;
}
}
//没有找到待删除Key值，则退出
if(!bn)returnT;
//取得节点平衡因子、是否为右节点标记
intfactor=getBalanceFactor(bn),isRight=bn-isRight;
//取得父级节点
binaryNode*parent=bn-parent;
//移除原先的父级节点关系
if(parent)removeBinaryNode(parent,bn);
//取得节点的左子树和右子树
binaryNode*left=bn-left,*right=bn-right;
//定义替换节点
binaryNode*replaceNode,*replaceParent,*replaceChild;
//判断待删除节点的平衡因子
if(factor==0)
{
//取得右子树最小节点
replaceNode=getMinBinaryNode(right);
}
elseif(factor0)
{
//取得左子树最大节点
replaceNode=getMaxBinaryNode(left);
}
else
{
//取得右子树最小节点
replaceNode=getMinBinaryNode(right);
}
//移除原先的左子树关系
removeBinaryNode(bn,left);
//移除原先的右子树关系
removeBinaryNode(bn,right);
binaryNode*result;
//进行删除节点替换
if(replaceNode)
{
intreplaceIsRight=replaceNode-isRight;
//取得替换节点的父级节点
replaceParent=replaceNode-parent;
//取得替换节点的子级节点
if(replaceIsRight0)
{
replaceChild=replaceNode-left;
}
else
{
replaceChild=replaceNode-right;
}
//移除替换节点的父级关系
removeBinaryNode(replaceParent,replaceNode);
//移除替换节点的子级关系
removeBinaryNode(replaceNode,replaceChild);
//重新建立替换节点原先的父子级关系
addBinaryNode(replaceParent,replaceIsRight,replaceChild);
//建立替换节点和原先的左子树和右子树的关系
addBinaryNode(replaceNode,0,left);
addBinaryNode(replaceNode,1,right);
//建立原先父级节点和旋转后的父级节点的关系
if(parent)addBinaryNode(parent,isRight,replaceNode);
//替换节点之前的父级节点
result=replaceParent;
}
else
{
//无需替换，重新连接后直接删除
if(left)
{
//重新建立原先父级节点和左子树的关系
if(parent)addBinaryNode(parent,isRight,left);
}
elseif(right)
{
//重新建立原先父级节点和右子树的关系
if(parent)addBinaryNode(parent,isRight,right);
}
//父级节点
result=parent;
}
//释放二叉树节点
clearBinaryList(bn);
bn=result;
//遍历平衡因子
while(bn)
{
//取得节点平衡因子
factor=getBalanceFactor(bn);
//父级节点平衡因子变为1或-1，则表示高度不变，结束向上传导
if((factor==1)
(factor==-1))break;
if(factor1)
{
//取得左子节点平衡因子
factor=getBalanceFactor(bn-left);
//右旋转之前，如果左子节点平衡因子小于0，则需要先对左子树进行左旋转
if(factor0)leftRotate(bn-left);
//平衡右旋转
rightRotate(bn);
}
elseif(factor-1)
{
//取得右子节点平衡因子
factor=getBalanceFactor(bn-right);
//左旋转之前，如果右子节点平衡因子大于0，则需要先对右子树进行右旋转
if(factor0)rightRotate(bn-right);
//平衡左旋转
leftRotate(bn);
}
//删除节点需要继续向上传导
bn=bn-parent;
}
//返回删除调整后的替换节点
returnresult;
}
抽象结构优化（binaryTree.h、binaryTree.c）：
#defineBinaryTreeOrderBUFFER
typedefdoublebinaryElemType;
typedefstruct
{
intkey; //二叉树节点关键字（优先数）
binaryElemType*data; //数据内容
intdataSize; //数据内容的空间大小
structbinaryNode*parent; //父节点
structbinaryNode*left; //左节点
structbinaryNode*right; //右节点
intheight; //二叉树的高度（包括根节点）
intlength; //二叉树的节点数量（包括所有子节点）
intisRight; //如果是子节点，则是否为右节点（右：1；左：0）
}binaryNode;
//创建二叉树节点
binaryNode*createBinaryNode(intdataSize);
//设置二叉树节点的数据内容
voidsetBinaryNodeData(binaryNode*T,binaryElemType*e);
//是否为叶子节点返回1，否则返回0
intisLeafBinaryNode(binaryNode*T);
//二叉树的高度
intheightBinaryList(binaryNode*T);
//二叉树的高度（递归）
intheightBinaryListRecursion(binaryNode*T);
//二叉树的节点数量
intlengthBinaryList(binaryNode*T);
//二叉树的节点数量（递归）
intlengthBinaryListRecursion(binaryNode*T);
//取得二叉树节点的层级
intlevelBinaryNode(binaryNode*T);
//取得子节点的相对层级
intlevelBinaryChildNode(binaryNode*T,binaryNode*child);
//取得二叉树节点的根节点
binaryNode*getBinaryRoot(binaryNode*T);
//取得二叉树的最大节点
binaryNode*getMaxBinaryNode(binaryNode*T);
//取得二叉树的最小节点
binaryNode*getMinBinaryNode(binaryNode*T);
//插入二叉树的子节点（右：1；左：0）
binaryNode*insertBinaryNode(binaryNode*T,intisRight,intkey);
//添加二叉树的子节点（右：1；左：0）
binaryNode*addBinaryNode(binaryNode*T,intisRight,binaryNode*child);
//移除二叉树的子节点
intremoveBinaryNode(binaryNode*T,binaryNode*child);
//清空二叉树列表（递归）
voidclearBinaryList(binaryNode*T);
#includestdlib.h
#include"mystring.h"
#include"linkQueue.h"
#include"linkStack.h"
#include"binaryTree.h"
//创建二叉树节点
binaryNode*createBinaryNode(intdataSize)
{
//首先申请自己的内存空间
binaryNode*bn=(binaryNode*)malloc(sizeof(binaryNode));
if(!bn)returnNULL;
if(dataSize0)
{
bn-data=(binaryElemType*)malloc(sizeof(binaryElemType)*dataSize);
if(!bn-data)
{
//清空二叉树列表（递归）
clearBinaryList(bn);
returnNULL;
}
bn-dataSize=dataSize;
}
else
{
bn-data=NULL;
bn-dataSize=0;
}
bn-key=0;
bn-parent=NULL;
bn-left=NULL;
bn-right=NULL;
bn-height=1;
bn-length=1;
bn-isRight=0;
returnbn;
}
//设置二叉树节点的数据内容
voidsetBinaryNodeData(binaryNode*T,binaryElemType*data)
{
if((!T)
(!data))return;
//判断数据内容是否有效
if(T-data)
{
//是否包含数据内容
inti;
//设置数据内容
for(i=0;iT-dataSize;i++)
{
T-data=data;
}
}
}
//是否为叶子节点返回1，否则返回0
intisLeafBinaryNode(binaryNode*T)
{
if(!T)return-1;
return((!T-left)(!T-right));
}
//二叉树的高度
intheightBinaryList(binaryNode*T)
{
if(!T)return0;
//判断节点高度是否有效
if(T-height0)
{
returnT-height;
}
else
{
//二叉树的高度（递归）
returnheightBinaryListRecursion(T);
}
}
//二叉树的高度（递归）
intheightBinaryListRecursion(binaryNode*T)
{
if(!T)return0;
//二叉树的节点高度
intheight=1;
//递归记录左子树高度
intleftHeight=heightBinaryListRecursion(T-left);
//递归记录右子树高度
intrightHeight=heightBinaryListRecursion(T-right);
if(leftHeightrightHeight)
{
height+=leftHeight;
}
else
{
height+=rightHeight;
}
//更新节点高度
T-height=height;
returnheight;
}
//二叉树的节点数量
intlengthBinaryList(binaryNode*T)
{
if(!T)return0;
//判断节点数量是否有效
if(T-length0)
{
returnT-length;
}
else
{
//二叉树的节点数量（递归）
returnlengthBinaryListRecursion(T);
}
}
//二叉树的节点数量（递归）
intlengthBinaryListRecursion(binaryNode*T)
{
if(!T)return0;
//二叉树的节点数量
intlen=1;
//递归记录左子树数量
len+=lengthBinaryListRecursion(T-left);
//递归记录右子树数量
len+=lengthBinaryListRecursion(T-right);
//更新节点数量
T-length=len;
returnlen;
}
//取得二叉树节点的层级
intlevelBinaryNode(binaryNode*T)
{
if(!T)return-1;
//从0开始
intlevel=0;
binaryNode*bn=T;
//遍历父级节点
while(bn-parent)
{
level++;
//递归父级节点
bn=bn-parent;
}
returnlevel;
}
//取得子节点的相对层级
intlevelBinaryChildNode(binaryNode*T,binaryNode*child)
{
if((!T)
(!child))return-1;
//从0开始
intlevel=0;
binaryNode*bn=child;
//遍历节点
while(bn)
{
if(T==bn)returnlevel;
level++;
//递归父级节点
bn=bn-parent;
}
return-1;
}
//取得二叉树节点的根节点
binaryNode*getBinaryRoot(binaryNode*T)
{
if(!T)returnNULL;
binaryNode*bn=T;
//遍历父级节点
while(bn-parent)
{
//递归父级节点
bn=bn-parent;
}
returnbn;
}
//取得二叉树的最大节点
binaryNode*getMaxBinaryNode(binaryNode*T)
{
if(!T)returnNULL;
binaryNode*bn=T;
//遍历右节点
while(bn-right)
{
//递归右节点
bn=bn-right;
}
returnbn;
}
//取得二叉树的最小节点
binaryNode*getMinBinaryNode(binaryNode*T)
{
if(!T)returnNULL;
binaryNode*bn=T;
//遍历左节点
while(bn-left)
{
//递归左节点
bn=bn-left;
}
returnbn;
}
//重新设置节点高度
intresetHeightBinaryNode(binaryNode*T)
{
if(!T)return0;
//二叉树的节点高度
intheight=1;
//记录左子树高度
intleftHeight=heightBinaryList(T-left);
//记录右子树高度
intrightHeight=heightBinaryList(T-right);
if(leftHeightrightHeight)
{
height+=leftHeight;
}
else
{
height+=rightHeight;
}
//更新节点高度
T-height=height;
returnheight;
}
//插入二叉树的子节点（右：1；左：0）
binaryNode*insertBinaryNode(binaryNode*T,intisRight,intkey)
{
if(!T)returnNULL;
//判断是否已有左节点或右节点
if(isRight0)
{
if(T-right)returnNULL;
}
else
{
if(T-left)returnNULL;
}
//创建二叉树节点
binaryNode*child=createBinaryNode(T-dataSize);
if(!child)returnNULL;
//节点关键字（优先数）
child-key=key;
//父级节点
child-parent=T;
//判断插入左节点或右节点
if(isRight0)
{
T-right=child;
child-isRight=1;
}
else
{
T-left=child;
child-isRight=0;
}
//维护节点数量和高度
binaryNode*bn=T;
//遍历节点
while(bn)
{
bn-length++;
//重新设置节点高度
resetHeightBinaryNode(bn);
//递归父级节点
bn=bn-parent;
}
returnchild;
}
//添加二叉树的子节点（右：1；左：0）
binaryNode*addBinaryNode(binaryNode*T,intisRight,binaryNode*child)
{
if((!T)
(!child))returnNULL;
//判断是否已有左节点或右节点
if(isRight0)
{
if(T-right)returnNULL;
}
else
{
if(T-left)returnNULL;
}
//避免嵌套死循环，相对层级=0，则表示嵌套子级节点
if(levelBinaryChildNode(child,T)=0)returnNULL;
//移除原有的父级关系
removeBinaryNode(child-parent,child);
//父级节点
child-parent=T;
//判断添加左节点或右节点
if(isRight0)
{
T-right=child;
child-isRight=1;
}
else
{
T-left=child;
child-isRight=0;
}
//维护节点数量和高度
binaryNode*bn=T;
//遍历节点
while(bn)
{
bn-length+=child-length;
//重新设置节点高度
resetHeightBinaryNode(bn);
//递归父级节点
bn=bn-parent;
}
returnchild;
}
//移除二叉树的子节点
intremoveBinaryNode(binaryNode*T,binaryNode*child)
{
if((!T)
(!child))return-1;
//判断父级关系是否匹配
if(T!=child-parent)return-1;
intresult=-1;
//判断是否移除左节点
if(T-left==child)
{
T-left=NULL;
result=1;
}
//判断是否移除右节点
if(T-right==child)
{
T-right=NULL;
result=1;
}
if(result0)
{
child-parent=NULL;
//维护节点数量和高度
binaryNode*bn=T;
//遍历节点
while(bn)
{
bn-length-=child-length;
//重新设置节点高度
resetHeightBinaryNode(bn);
//递归父级节点
bn=bn-parent;
}
}
returnresult;
}
//清空二叉树列表（递归）
voidclearBinaryList(binaryNode*T)
{
if(!T)return;
//递归清空左节点
clearBinaryList(T-left);
//递归清空右节点
clearBinaryList(T-right);
//释放数据空间
if(T-data)free(T-data);
//释放自己
free(T);
}
预览时标签不可点收录于话题#个上一篇下一篇