7.3、二叉树的存储结构
二叉树的顺序存储
完全二叉树,实现一些基本操作,如果不是完全二叉树最好使用链表
#include <stdio.h>
#include <stdlib.h>
#include<math.h>
#define MaxSize 100
#define ElemType int
#define boolean int
#define true 1
#define false 0
typedef struct TreeNode{
ElemType val; //树的结点的值
boolean iSEmpty;//树是否为空
}TreeNode;
//初始化树的数组
boolean InitTree(TreeNode trees[]){
for(int i = 1 ;i < MaxSize;i++){//让0号下标空缺
trees[i].iSEmpty = true; //把所有的树都置为空
}
return true;
}
//第i个结点的左孩子
boolean GetLeftNode(TreeNode * left,TreeNode trees[],int i){
if(trees[2*i].iSEmpty) printf("第%d个结点没有左孩子\n",i);
else{
left->val = trees[2*i].val;
left->iSEmpty = false;
}
return true;
}
//第i个结点的右孩子
boolean GetRightNode(TreeNode * right,TreeNode trees[],int i){
if(trees[2*i+1].iSEmpty) {
printf("第%d个结点没有右孩子\n",i);
return false;
}
else{
right->val = trees[2*i+1].val;
right->iSEmpty = false;
}
return true;
}
//获取第i个结点的父结点
boolean GetFatherNode(TreeNode * father,TreeNode trees[],int i){
if(i == 1) {
printf("第1个结点没有父节点\n");
return false;
}else{
father->iSEmpty = false;
father->val = trees[i/2].val;
return true;
}
}
//获取第i个结点所在的层次
int GetNodeLevel(int i){
double d = log2(i+1);
int level = (int)d;
return level+1;
}
测试
int main(){
TreeNode trees[MaxSize];//定义一个数组来存储树的结点
InitTree(trees);
for(int i = 1;i <= 12;i++){//初始化树
trees[i].val = i;
trees[i].iSEmpty = false;
}
TreeNode left;
TreeNode right;
left.iSEmpty = true;
right.iSEmpty = true;
GetLeftNode(&left,trees,6);
GetRightNode(&right,trees,6);
if(!left.iSEmpty){
printf("第6个结点的左孩子:%d \n",left.val);
}
if(!right.iSEmpty){
printf("第6个结点的左孩子:%d \n",right.val);
}
TreeNode father;
father.iSEmpty = true;
GetFatherNode(&father,trees,5);
if(!father.iSEmpty){
printf("第5个结点的父结点:%d \n",father.val);
};
int level = GetNodeLevel(10);
printf("第10个结点的层次:%d \n",level);
return 0;
}
//结果:
第6个结点没有右孩子
第6个结点的左孩子:12
第5个结点的父结点:2
第10个结点的层次:4
7.4、二叉树的链式存储
#include <stdio.h>
#include <stdlib.h>
#include<math.h>
#define MaxSize 100
#define ElemType int
#define boolean int
#define true 1
#define false 0
typedef struct LinkTree{
ElemType data;
struct LinkTree *lchild,*rchild;
}*LinkTree,TreeNode;
//初始化一颗二叉树
boolean InitTree(LinkTree *root,ElemType data){
*root = (LinkTree)malloc(sizeof(TreeNode));
if(root == NULL) return false;
(*root)->data = data;
(*root)->lchild = NULL;
(*root)->rchild = NULL;
return true;
}
//添加一个左孩子
boolean AddLeftChild(ElemType data,TreeNode *Node){
TreeNode *lchild = (TreeNode *)malloc(sizeof(TreeNode));
if(lchild == NULL) return false;
lchild->data = data;
lchild->lchild = NULL;
lchild->rchild =NULL;
Node->lchild = lchild;
return true;
}
//添加一个右孩子
boolean AddRightChild(ElemType data,TreeNode *Node){
TreeNode *right = (TreeNode *)malloc(sizeof(TreeNode));
if(right == NULL) return false;
right->data = data;
right->lchild = NULL;
right->rchild =NULL;
Node->rchild = right;
return true;
}
测试
int main(){
LinkTree root;
InitTree(&root,1);
AddLeftChild(2,root);
AddRightChild(3,root);
printf("根结点的值为:%d \n",root->data);
printf("根结点的左孩子的值为:%d \n",root->lchild->data);
printf("根结点的右孩子的值为:%d \n",root->rchild->data);
}
//结果:
根结点的值为:1
根结点的左孩子的值为:2
根结点的右孩子的值为:3
原文地址:http://www.cnblogs.com/shuisanya/p/16849414.html
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,请务用于商业用途!
3. 如果你也有好源码或者教程,可以到用户中心发布,分享有积分奖励和额外收入!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!
7. 如遇到加密压缩包,默认解压密码为"gltf",如遇到无法解压的请联系管理员!
8. 因为资源和程序源码均为可复制品,所以不支持任何理由的退款兑现,请斟酌后支付下载
声明:如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性