济南网站建设公司 推荐行知科技,毕业设计h5网站制作,教育机构网站制作模板,优秀网站开发目录 一、广义表的定义二、广义表的表头和表尾三、广义表的深度和长度四、广义表与二叉树#xff08;一#xff09;广义表表示二叉树#xff08;二#xff09;广义表表示二叉树的代码实现 一、广义表的定义
广义表是线性表的进一步推广#xff0c;是由n#xff08;n≥0一广义表表示二叉树二广义表表示二叉树的代码实现 一、广义表的定义
广义表是线性表的进一步推广是由nn≥0个数据元素组成的有限序列。线性表中的数据元素只能是单个元素原子它是不可分割的而广义表中的数据元素既可以是原子也可以是一个广义表包括空表和非空表广义表通过圆括号“()”括起来通过逗号“,”隔开表中的各个数据元素。 一个n维数组可以看成元素是n-1维数组的广义表广义表的元素都是n-1维数组。广义表满足线性表的特征只是其中的元素是原子或广义表子表分别只有一个表头元素和表尾元素表头元素有后继但是没有前驱表尾元素有前驱但是没有后继剩下每个元素都有唯一的前驱和后继。
二、广义表的表头和表尾
广义表是可以递归的一个广义表也可以是其自身的子表广义表中的第一个元素称为广义表的表头而剩余数据元素组成的表称为广义表的表尾广义表的表头和表尾可以看作通过函数head()和tail()对广义表操作。例如已知广义表S(((a)),(b),c,(a),(((d,e))))通过head()和tail()取出元素e的操作如下
head(tail(head(head(head(tail(tail(tail(tail(A)))))))))任何一个非空广义表表头可能是单个元素原子或广义表但表尾只可能是广义表其原因是广义表的取表尾tail()是非空广义表除去表头元素后剩余元素组成的表所以不可能是原子。 例如C(a,b,c,d,e,f,g)该广义表的表头是(a)表尾是(b,c,d,e,f,g) 例如D((a,b),((c,d,e),(f,g,h)))该广义表的表头是(a,b)表尾是((c,d,e),(f,g,h))。
另外若一个广义表为空则为一个空表。例如E( )F(( ))广义表E是一个空表只有非空广义表才能取表头广义表F的表头和表尾都是()。
三、广义表的深度和长度
广义表的深度通过括号的层数求得而长度是广义表中所含元素的个数。【深度层数长度个数】
例如一个空广义表G()括号层数为1所以广义表的深度为1而由于是空表所以广义表的长度为0 例如一个广义表H((a,b),(c,(d,e)))括号层数为3所以广义表的深度为3最高层为(c,(d,e))逗号隔开了原子( c )和广义表( d,e )元素个数为2所以广义表的长度为2。 例如一个广义表I((),(a),(b,c,(d),((d,f))))由于括号的最大层数为4所以广义表的深度为4可知广义表有三个元素分别是()、(a)、(b,c,(d),((d,f)))元素个数为3所以广义表的长度为3。 例如设广义表J(( ),( ))对广义表Jhead(J)( )tail(J)(( ))括号的最大层数为2所以广义表的深度为2广义表有两个元素分别是()、()元素个数为2所以广义表长度为2。 注这里的Tail(J)(( ))而不是( )。 四、广义表与二叉树
一广义表表示二叉树
根据广义表中“ 数据元素既可以是原子也可以是一个广义表包括空表和非空表) ”这一点可以来表示二叉树即通过(根结点根结点的广义表)的形式来表示其中可以嵌套。 例如下面是一个满二叉树 通过广义表表示该二叉树 (A , ( B , ( D , E ) ) , ( C , ( F , G ) ) ) ) 这个二叉树的解释如下 根结点是A它的左孩子是BB的左孩子是DB的右孩子是E。 根结点A的右孩子是CC的左孩子是FC的右孩子是G。
二广义表表示二叉树的代码实现
通过广义表来显示建立的二叉树一个非空的二叉树T当对于左孩子结点或右孩子结点时此时输出一个左括号“(”递归处理左子树输出一个“,”用于隔开结点然后递归处理右子树输出一个右括号“)”从而完成一个根结点以下的两个左/右结点处理代码如下
/*广义表输出二叉树*/
void ShowTree(BTree T) {if(T!NULL) {//当二叉树不为空时printf(%c,T-data); //输入出该结点的数据域if(T-lchild!NULL) { //若该结点的左子树不为空printf((); //输出一个左括号ShowTree(T-lchild); //通过递归继续输出结点的左子树结点下的各结点if(T-rchild!NULL) { //若该结点右子树不为空printf(,); //输出一个逗号ShowTree(T-rchild); //通过递归继续输出结点的右子树结点下的各结点}printf()); //输出一个右括号} else { //若左子树为空右子树不为空if(T-rchild!NULL) {printf((); //输出一个左括号ShowTree(T-lchild); //通过递归继续输出结点的左子树结点下的各结点if(T-rchild!NULL) { //若该结点的右子树不为空 printf(,); //输出一个逗号ShowTree(T-rchild); //通过递归继续输出结点的右子树结点下的各结点}printf()); //输出一个右括号}}}
}例如一个二叉树如下图通过链式存储结构实现建立二叉树并输出。 代码如下
#include stdio.h
#include malloc.h
/*1、二叉树的定义*/
typedef struct BNode {int data; //数据域struct BNode *lchild,*rchild; //左孩子、右孩子指针
} *BTree;/*2、二叉树的建立*/
BTree CreateTree() {BTree T;char ch;scanf(%c,ch);getchar(); //getchar()用于接收每次输入字符结点后的回车符从而以便输入下一个字符结点if(ch0) //当为0时将结点置空TNULL;else {T(BTree)malloc(sizeof(BTree)); //分配一个新的结点T-datach;printf(请输入%c结点的左孩子结点,T-data);T-lchildCreateTree(); //通过递归建立左孩子结点printf(请输入%c结点的右孩子结点,T-data);T-rchildCreateTree(); //通过递归建立右孩子结点}return T;
}/*3、广义表输出二叉树*/
void ShowTree(BTree T) {if(T!NULL) {//当二叉树不为空时printf(%c,T-data); //输入出该结点的数据域if(T-lchild!NULL) { //若该结点的左子树不为空printf((); //输出一个左括号ShowTree(T-lchild); //通过递归继续输出结点的左子树结点下的各结点if(T-rchild!NULL) { //若该结点右子树不为空printf(,); //输出一个逗号ShowTree(T-rchild); //通过递归继续输出结点的右子树结点下的各结点}printf()); //输出一个右括号} else { //若左子树为空右子树不为空if(T-rchild!NULL) {printf((); //输出一个左括号ShowTree(T-lchild); //通过递归继续输出结点的左子树结点下的各结点if(T-rchild!NULL) { //若该结点的右子树不为空 printf(,); //输出一个逗号ShowTree(T-rchild); //通过递归继续输出结点的右子树结点下的各结点}printf()); //输出一个右括号}}}
}/*主函数*/
int main() {BTree T;TNULL;printf(请输入二叉树的根结点);TCreateTree(); //建立二叉树printf(建立的二叉树如下\n);ShowTree(T); //通过广义表显示二叉树
}依次输入各个结点的左右孩子结点若结点不存在则输入0例如树中结点d的左孩子结点不存在结点f、g、h、i、j的左右孩子都不存在输入时都输入0。 运行结果如下结果通过广义表的定义显示
