《广义表二叉树复习》由会员分享，可在线阅读，更多相关《广义表二叉树复习（12页珍藏版）》请在金锄头文库上搜索。
1、广义表 (General Lists ) 广义表的概念 n ( 0 )个表元素组成的有限序列，记作LS = (a0, a1, a2, , an-1)LS是表名，ai是表元素，它可以是表 (称为子表)，可以是数据元素(称为原子)。表的第一个表元素称为广义表的表头 (head)，除此之外，其它表元素组成的表 称为广义表的表尾(tail)。 表结点Tag=1 hp tp广义表存储结构(头尾链表表示)原子结点Tag=0 atomtypedef struct GLNode int tag; union char atom; struct structGLNode hp,*yp;ptr; ; 表结点tag
2、=1 hp tp广义表存储结构(扩展线形链表表示)原子结点Typedef enumATOM,LISTElemtag; / 0 ;1 Typedef struct GLNodeElemtag tag; /公共部分unionAtomType atom;struct GLNode *hp;struct GLNode *tp; *GList;tag=0 atom tp5.30 按表头、表尾的分析方法重写求广义 表深度的算法 int GList_Getdeph(GList L) if (!L-tag) return 0; /原子的深度为0else if (!L) return 1; / 空表的深度为1m
3、 = GList_Getdeph(L-ptr.hp)+1;n = GList_Getdeph(L-ptr.tp);return mn ？m : n; / GList_Getdeph5.31 按5.5节图5.10所示节点结构编写复制广义表 的递归算法 void GList_Copy(GList A,GList B-atom = A-atom; else / 节点为子表 B-tag = 1;if (A-ptr.hp) /复制表头 B-ptr.hp = malloc(sizeof(GLNode);GList_Copy(A-ptr.hp,B-ptr.hp); if (A-ptr.tp) /复制表尾 B
4、-ptr.tp = malloc(sizeof(GLNode);GList_Copy(A-ptr.tp,B-ptr.tp); /else/GList_Copy5.37 删除广义表中所有值等于x的原子项 void GList_DelElem(GList else if (!A-ptr.hp-tag A=A-ptr.tp; /删去员素值为x的表头free(q); GList_DelElem(A,x);if (A-ptr.tp) GList_DelElem(A-ptr.tp,x); /GList_DelElem 二叉树 链表表示lChild data rChilddatalChildrChild二叉
5、链表含两个指针域的结点结构lChild data parent rChild含三个指针域的结点结构 parentdatalChildrChild 三叉链表二叉树链表表示的示例 AAABBBCCCDDDFFFEEErootrootroot二叉树 二叉链表 三叉链表typedef char TreeData;/结点数据类型typedef struct node /结点定义TreeData data; struct node * leftChild, * rightchild; BinTreeNode;typedef BinTreeNode * BinTree;/根指针 二叉链表的定义6.42 计算
6、二叉树中叶子节点的数目int LeafCount_BiTree(BiTree T)if (!T) return 0; /空树没有叶子else if (!T-lchild /叶子else return Leaf_Count(T-lchild) + Leaf_Count (T-rchild); /左右子树叶子节点数相加 /LeafCount_BiTree6.69 以二叉链表存储的二叉树中，每个 节点所含数据元素均为单字母，编写算 法，按树状打印二叉树。 如： void Print_BiTree(BiTree T, int i) / i 表示节点所在的层次， 初值 = 0if (T-rchild) Print_BiTree(T-rchild,i+1)for (j =1; jdata);if (T-lchild) Print_BiTree(T-lchild,i+1);/Print_BiTree
