1. 首页
  2. 文章中心
  3. 数据结构

二叉树的顺序存储结构

72 阅读 0 评论
我是靠谱客的博主 机灵煎饼，最近开发中收集的这篇文章主要介绍二叉树的顺序存储结构，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

#ifndef TREE_H
#define MAX_TREE_SIZE 20 /* 二叉树的最大结点数 */

#define OK 1
#define ERROR -1
typedef int Status ;
typedef  char TElemType ;
typedef TElemType SqBiTree[MAX_TREE_SIZE]; /* 0号单元存储根结点 */

 typedef struct
 {
   int level,order; /* 结点的层,本层序号(按满二叉树计算) */
 }position;
 /基本操作

Status InitBiTree(SqBiTree T);
void DestroyBiTree();
Status CreateBiTree(SqBiTree T);
Status BiTreeEmpty(SqBiTree T);
int BiTreeDepth(SqBiTree T);
Status Root(SqBiTree T,TElemType *e);
TElemType Value(SqBiTree T,position e);
Status Assign(SqBiTree T,position e,TElemType value);
TElemType Parent(SqBiTree T,TElemType e);
TElemType LeftChild(SqBiTree T,TElemType e);
TElemType RightChild(SqBiTree T,TElemType e);
TElemType LeftSibling(SqBiTree T,TElemType e);
TElemType RightSibling(SqBiTree T,TElemType e);
void Move(SqBiTree Q,int j,SqBiTree T,int i);
Status InsertChild(SqBiTree T,TElemType p,Status LR,SqBiTree c);
Status DeleteChild(SqBiTree T,position p,int LR);
void PreTraverse(SqBiTree T,int e);
Status PreOrderTraverse(SqBiTree T,Status(*Visit)(TElemType));
void InTraverse(SqBiTree T,int e);
Status InOrderTraverse(SqBiTree T,Status(*Visit)(TElemType));
void PostTraverse(SqBiTree T,int e);
Status PostOrderTraverse(SqBiTree T,Status(*Visit)(TElemType));
void LevelOrderTraverse(SqBiTree T,Status(*Visit)(TElemType));
void Print(SqBiTree T);
#endif


#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
#include "c6_1.h"


Status InitBiTree(SqBiTree T){
	/*构造空二叉树T,因为T是固定数组，不会改变,故不需要&*/
	int i ;
	for(i=0;i<MAX_TREE_SIZE;i++)
		T[i]=NULL;
	return OK;
}
void DestoryBiTree(SqBiTree T){
	/*由于SqBiTree 是定长的,无法销毁*/
}

Status CreateBiTree(SqBiTree T){
	/*按层次次输入二叉树中结点的值,(字符型),构造顺序存储结构的二叉树T*/
	int i =0;
	int l;
	char s[MAX_TREE_SIZE];
	printf("请按层次输入二叉树节点的值(字符),空格表示空结点,结点数<%d:n",MAX_TREE_SIZE);
	gets(s);      /*输入字符串*/
	l = strlen(s);/*求字符串的长度*/
	for(;i<l;i++){/*将字符串赋值给T*/
		T[i]=s[i];
		if(i!=0&&T[(i+1)/2-1]==NULL&&T[i]!=NULL){
			printf("出现无双亲的非根结点%cn",T[i]);
			exit(ERROR);
		}
	}
	for(i=l;l<MAX_TREE_SIZE;l++)/*将空值赋给l以后的值*/
		T[i]=NULL;
	return OK ;
}
#define ClearBiTree InitBiTree /* 在顺序存储结构中，两函数完全一样 */

Status BiTreeEmpty(SqBiTree T){
	/* 初始条件: 二叉树T存在 */
   /* 操作结果: 若T为空二叉树,则返回TRUE,否则FALSE */
	if(T[0]==NULL)
		return true;
	else
		return false;
}
int BiTreeDepth(SqBiTree T){ 
	/* 初始条件: 二叉树T存在。操作结果: 返回T的深度 */
   int i,j=-1;
   for(i=MAX_TREE_SIZE-1;i>=0;i--) /* 找到最后一个结点 */
     if(T[i]!=NULL)
       break;
   i++; /* 为了便于计算 */
   do
     j++;
   while(i>=pow(2,j));
   return j;
}

Status Root(SqBiTree T,TElemType *e){
   /* 初始条件: 二叉树T存在 */
   /* 操作结果:  当T不空,用e返回T的根,返回OK;否则返回ERROR,e无定义 */
	if(BiTreeEmpty(T))
		return ERROR;
	else{
		*e=T[0];
		return OK ;
	}
}

TElemType Value(SqBiTree T,position e){
   /* 初始条件: 二叉树T存在,e是T中某个结点(的位置) */
   /* 操作结果: 返回处于位置e(层,本层序号)的结点的值 */
	return T[(int)pow(2,e.level-1)+e.order-2];
}
Status Assign(SqBiTree T,position e,TElemType value){
   /* 初始条件: 二叉树T存在,e是T中某个结点(的位置) */
   /* 操作结果: 给处于位置e(层,本层序号)的结点赋新值value */

	int i = (int)pow(2,e.level-1)+e.order-2;/*计算出要插入的位置*/
	/*插入检查*/
	if(value!=NULL&&T[int((i+1)/2)-1]==NULL){
		printf("值不为空,但没有双亲结点n");
		return ERROR;
	}
	else if(value==NULL&&T[2*i+1]!=NULL&&T[2*i+2]!=NULL){
		printf("双亲不为空,但孩子都不为空n");
		return ERROR;
	}
	T[i]= value;
	return OK ;

}
TElemType Parent(SqBiTree T,TElemType e){
   /* 初始条件: 二叉树T存在,e是T中某个结点 */
   /* 操作结果: 若e是T的非根结点,则返回它的双亲,否则返回＂空＂ */
	int i;
	if(T[0]==NULL)/*空树*/
		return ERROR ;
	for(i=0;i<MAX_TREE_SIZE;i++){
		if(T[i]==e)
			return T[(int)(i+1)/2-1];
	}
	return NULL;
}
TElemType LeftChild(SqBiTree T,TElemType e){
	/*初始条件:二叉树T存在,e是T中的结点*/
	/*操作结果:返回e的左孩子*/
	int i ;
	if(T[0]==NULL)/*空树*/
		return ERROR;
	for(i=0;i<MAX_TREE_SIZE;i++){
		if(T[i]==e)
			return T[2*i+1];
	}
	return NULL;
}
TElemType RightChild(SqBiTree T,TElemType e){
	/*初始条件:二叉树T存在,e是T中的结点*/
	/*操作结果:返回e的右孩子*/
	int i ;
	if(T[0]==NULL)/*空树*/
		return ERROR;
	for(i=0;i<MAX_TREE_SIZE;i++){
		if(T[i]==e)
			return T[2*i+2];
	}
	return NULL;
}
TElemType LeftSibling(SqBiTree T,TElemType e){
   /* 初始条件: 二叉树T存在,e是T中某个结点 */
   /* 操作结果: 返回e的左兄弟。若e是T的左孩子或无左兄弟,则返回＂空＂ */
	int i;
	if(T[0]==NULL)
		return ERROR;
	for(i=0;i<MAX_TREE_SIZE;i++){
		if(T[i]==e&&i%2==0)/*找到e且其序号为偶数(是右孩子)*/
			return T[i-1];	
	}
	return NULL;
}
TElemType RightSibling(SqBiTree T,TElemType e){
	/*初始条件:二叉树T存在,e是T中的某个结点*/
	/*操作结果:返回e的右兄弟,若e是T的右孩子或是无右兄弟,则返回空*/
	int i ;
	if(T[0]==NULL)
		return NULL;
	for(i=0;i<MAX_TREE_SIZE;i++){
		if(T[i]==e&&i%2==1)/*找到e且其序号为偶数(是右孩子)*/
			return T[i+1];	
	}
	return NULL;
}
void Move(SqBiTree Q,int j,SqBiTree T,int i){
	/* 把从Q的j结点开始的子树移为从T的i结点开始的子树 */
	if(Q[2*j+1]!=NULL)   /*Q的左子树不为空*/
		Move(Q,(2*j+1),T,(2*i+1));
	if(Q[2*j+2]!=NULL)   /*Q的右子树不空*/
		Move(Q,(2*j+2),T,(2*i+2));/*把Q的j结点的右子树移为T的i结点的右子树*/
	T[i]=Q[j];
	Q[j]=NULL;
}
Status InsertChild(SqBiTree T,TElemType p,Status LR,SqBiTree c){
	/* 初始条件: 二叉树T存在,p是T中某个结点的值,LR为0或1,非空二叉树c与T */
    /*           不相交且右子树为空 */
    /* 操作结果: 根据LR为0或1,插入c为T中p结点的左或右子树。p结点的原有左或 */
    /*           右子树则成为c的右子树 */
	int i,k ;
	for(i=0;i<MAX_TREE_SIZE;i++){
		if(T[i]==p&&T[i]!=NULL)
			break;
	}
	k=2*i+1+LR;/*p的左孩子或是右孩子的位置*/
	if(T[k]!=NULL) /* p原来的左或右孩子不空 */
		Move(T,k,T,2*k+2); /* 把从T的k结点开始的子树移为从k结点的右子树开始的子树 */
    Move(c,i,T,k); /* 把从c的i结点开始的子树移为从T的k结点开始的子树 */
    return OK;

}
Status DeleteChild(SqBiTree T,position p,int LR){
   /* 初始条件: 二叉树T存在,p指向T中某个结点,LR为1或0 */
   /* 操作结果: 根据LR为1或0,删除T中p所指结点的左或右子树 */
	return OK;
}
 Status(*VisitFunc)(TElemType); /* 函数变量 */
 void PreTraverse(SqBiTree T,int e){ 
	 /* PreOrderTraverse()调用 */
   VisitFunc(T[e]);
   if(T[2*e+1]!=NULL) /* 左子树不空 */
     PreTraverse(T,2*e+1);
   if(T[2*e+2]!=NULL) /* 右子树不空 */
     PreTraverse(T,2*e+2);
 }

 Status PreOrderTraverse(SqBiTree T,Status(*Visit)(TElemType))
 { /* 初始条件: 二叉树存在,Visit是对结点操作的应用函数 */
   /* 操作结果: 先序遍历T,对每个结点调用函数Visit一次且仅一次。 */
   /*           一旦Visit()失败,则操作失败 */
   VisitFunc=Visit;
   if(!BiTreeEmpty(T)) /* 树不空 */
     PreTraverse(T,0);
   printf("n");
   return OK;
 }

 void InTraverse(SqBiTree T,int e)
 { /* InOrderTraverse()调用 */
   if(T[2*e+1]!=NULL) /* 左子树不空 */
     InTraverse(T,2*e+1);
   VisitFunc(T[e]);
   if(T[2*e+2]!=NULL) /* 右子树不空 */
     InTraverse(T,2*e+2);
 }

 Status InOrderTraverse(SqBiTree T,Status(*Visit)(TElemType))
 { /* 初始条件: 二叉树存在,Visit是对结点操作的应用函数 */
   /* 操作结果: 中序遍历T,对每个结点调用函数Visit一次且仅一次。 */
   /*           一旦Visit()失败,则操作失败 */
   VisitFunc=Visit;
   if(!BiTreeEmpty(T)) /* 树不空 */
     InTraverse(T,0);
   printf("n");
   return OK;
 }

 void PostTraverse(SqBiTree T,int e)
 { /* PostOrderTraverse()调用 */
   if(T[2*e+1]!=NULL) /* 左子树不空 */
     PostTraverse(T,2*e+1);
   if(T[2*e+2]!=NULL) /* 右子树不空 */
     PostTraverse(T,2*e+2);
   VisitFunc(T[e]);
 }

 Status PostOrderTraverse(SqBiTree T,Status(*Visit)(TElemType))
 { /* 初始条件: 二叉树T存在,Visit是对结点操作的应用函数 */
   /* 操作结果: 后序遍历T,对每个结点调用函数Visit一次且仅一次。 */
   /*           一旦Visit()失败,则操作失败 */
   VisitFunc=Visit;
   if(!BiTreeEmpty(T)) /* 树不空 */
     PostTraverse(T,0);
   printf("n");
   return OK;
 }

 void LevelOrderTraverse(SqBiTree T,Status(*Visit)(TElemType))
 { /* 层序遍历二叉树 ,相当于遍历数组*/
   int i=MAX_TREE_SIZE-1,j;
   while(T[i]==NULL)
     i--; /* 找到最后一个非空结点的序号 */
   for(j=0;j<=i;j++)  /* 从根结点起,按层序遍历二叉树 */
     if(T[j]!=NULL)
       Visit(T[j]); /* 只遍历非空的结点 */
   printf("n");
 }

void Print(SqBiTree T)
{ /* 逐层、按本层序号输出二叉树 */
   int j,k;
   position p;
   TElemType e;
   for(j=1;j<=BiTreeDepth(T);j++)
   {
     printf("第%d层: ",j);
     for(k=1;k<=pow(2,j-1);k++)
     {
       p.level=j;
       p.order=k;
       e=Value(T,p);
       if(e!=NULL)
         printf("%d:%c ",k,e);
     }
     printf("n");
   }
}

 Status visit(TElemType e){
   printf("%c ",e);
   return OK;
 }
void main(){
	SqBiTree T;
	InitBiTree(T);
//	if(BiTreeEmpty(T)){
//		printf("树为空n");
//	}
	CreateBiTree(T);
//	if(!BiTreeEmpty(T)){
//		printf("树不为空n");
//	}
//	printf("%dn",BiTreeDepth(T));
//	ClearBiTree(T);
//	if(BiTreeEmpty(T)){
//		printf("树为空n");
//	}
//	TElemType e ;
//	Root(T,&e);
//	printf("根为: %cn",e);
//	position p;
//	p.level=2;
//	p.order=1;
//	printf("%cn",Value(T,p));
//	Assign(T,p, '7');
//	printf("%cn",Value(T,p));

	printf("4 is parent = %cn",Parent(T,'4'));
	printf("5 is leftchild=%cn",LeftChild(T,'5'));
	printf("5 is RightChild=%cn",RightChild(T,'5'));
	printf("5 is LeftSibling=%cn",LeftSibling(T,'5'));
	printf("2 is RightSibling=%cn",RightSibling(T,'2'));
	
	Print(T);

	printf("层序遍历二叉树:n");
   LevelOrderTraverse(T,visit);
   printf("中序遍历二叉树:n");
   InOrderTraverse(T,visit);
   printf("后序遍历二叉树:n");
   PostOrderTraverse(T,visit);
}

总结：

用一组连续的存储单元依次自上而下，自左向右存储完全二叉树的节点元素。将完全二叉树中的第i个结点存储在一维数组中的第i-1的分量中。

对于二叉树的顺序存储结构适合存储完全二叉树，否则会浪费大量的存储空间，最坏的情况是，一个深度为k且只有k个结点的单支书需要2^k-1的一维数组。

主要参考：严蔚敏数据结构

http://www.cnblogs.com/cpoint/p/3479782.html，对此作者表示感谢，给我很大的帮助


最后

以上就是机灵煎饼为你收集整理的二叉树的顺序存储结构的全部内容，希望文章能够帮你解决二叉树的顺序存储结构所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。

本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
点赞(48)

相关文章

二叉树
二叉树
数据结构与算法 －二叉树的存储结构
数据结构与算法 －二叉树的存储结构
如何用Green定理求五星形曲线所围面积的
如何用Green定理求五星形曲线所围面积的"精确解"
《数据结构导论之二叉树》◆前言◆定义◆性质◆总结
《数据结构导论之二叉树》◆前言◆定义◆性质◆总结
二叉树的顺序存储结构
二叉树的顺序存储结构
技术问答-23 javabean创建一个二叉树，左右两个叶子节点 （1）要求每个结点都有两个叶子，每个叶子节点可以找到父节点也可以找到左右两个子节点 （2）提供2中遍历方法
技术问答-23 javabean创建一个二叉树，左右两个叶子节点 （1）要求每个结点都有两个叶子，每个叶子节点可以找到父节点也可以找到左右两个子节点 （2）提供2中遍历方法
周志华：“深”为什么重要，以及还有什么深的网络
周志华：“深”为什么重要，以及还有什么深的网络
二叉树遍历高级版
二叉树遍历高级版

评论列表共有 0 条评论

立即
投稿
返回
顶部