二叉树的顺序存储
1.定义树结点 2.初始化所有结点 3.存入一些数据 4.查找左孩子 5.查找右孩子 6.查找父节点 7.判断i所在的层次 8.判断i是否为叶子结点 9.main函数测试 10.输出结果 所用编译器:Visual Studio Code 1.42.1 C++环境
#include
#include //其中floor()函数为向下(左)取整,ceil()函数为向上(右)取整
#define MaxSize 10
typedef int ElemType;
//定义树结点
typedef struct{
ElemType data;
bool isEmpty;
}TreeNode;
//初始化所有结点
void InitTree(TreeNode T[]){
for(int i=0;i
int j=3;
for(int i=1;i
if(i>=MaxSize)
return false;
if(2*i>=MaxSize||T[2*i].isEmpty==true)
return false;
else{
e=T[2*i].data;
}
return true;
}
//查找右孩子
bool Outrchild(TreeNode T[],int i,ElemType &e){
if(i>=MaxSize)
return false;
if(2*i+1>=MaxSize||T[2*i+1].isEmpty==true)
return false;
else{
e=T[2*i+1].data;
}
return true;
}
//查找父节点
bool OutFather(TreeNode T[],int i,ElemType &e){
if(i>=MaxSize)
return false;
if(i/2>=MaxSize||T[i/2].isEmpty==true)
return false;
else{
e=T[i/2].data;
}
return true;
}
//判断i所在的层次
int TreeNodefloor(TreeNode T[],int i){
int m=2,n;
double a=floor(log(i)/log(m))+1;//自定义的:以m为底的log(i)
if(i>=MaxSize)
return -1;
else
return a;
}
//判断i是否为叶子结点
bool isLeaf(TreeNode T[],int i){
if(i>(MaxSize-1)/2)
return true;
else
return false;
}
//main函数测试
int main(){
TreeNode T[MaxSize];
InitTree(T);
InputData(T);
int i=3;
ElemType e;
//查找左孩子
if(Outlchild(T,i,e))
printf("左孩子查找成功\n");
else
printf("左孩子查找失败\n");
printf("%d\n",e);
//查找右孩子
if(Outrchild(T,i,e))
printf("右孩子查找成功\n");
else
printf("右孩子查找失败\n");
printf("%d\n",e);
//查找父节点
if(OutFather(T,i,e))
printf("父节点查找成功\n");
else
printf("父节点查找失败\n");
printf("%d\n",e);
//判断i所在的层次
int floor=TreeNodefloor(T,i);
printf("a=%d\n",floor);
//判断是否为叶子结点
if(isLeaf(T,i))
printf("叶子结点\n");
else
printf("分支结点\n");
}
//输出结果
左孩子查找成功
13
右孩子查找成功
15
父节点查找成功
3
a=2
分支结点
|