二叉树的广义表形式.doc

二叉树的广义表形式2009-06-12 22:15题目：假设二叉树采用二叉链表结构。设计并实现如下算法：输入某棵二叉树的广义表形式，建立该二叉树，并按层次遍历该二叉树。 本演示程序根据提示输入二叉树的广义表形式例如：a(b(c),d(e(f, g),h(,i) 在演示过程序中，用户敲击键盘，即可观看演示结果。 程序执行的命令包括：（1）构造树的广义表 （2）输出构造好的广义表 （3）层次比遍历该二叉树 源程序 (C语言) #include #include #include #define STACK_MAX_SIZE 30#define QUEUE_MAX_SIZE 30typedef struct BTreeNodechar data;struct BTreeNode *lchild;struct BTreeNode *rchild;BTreeNode;void initBTree(BTreeNode* *bt) /* 初始化二叉树 */ *bt = NULL; void createBTree(BTreeNode* *bt, char *a) /*建立二叉树(根据a所指向的二叉树广义表字符串建立) */struct BTreeNode *p;struct BTreeNode *sSTACK_MAX_SIZE; /*定义s数组为存储根结点指针的栈使用 */int top = -1;int k; /*用k作为处理结点的左子树和右子树，k = 1处理左子树，k = 2处理右子树 */int i = 0;*bt = NULL;while(ai != 0)switch(ai)case : break;case (: if(top = STACK_MAX_SIZE - 1) printf(stack size full！n); exit(1); top+;stop = p; k = 1; break;case ): if(top = -1) printf(btree biao error!n); exit(1); top-; break;case ,: k = 2; break;default: p = (BTreeNode *)malloc(sizeof(BTreeNode); p-data = ai; p-lchild = p-rchild = NULL; if(*bt = NULL) *bt = p; else if( k = 1) stop-lchild = p; else stop-rchild = p; i+; /*while end*/void levelOrder(BTreeNode *bt) /* 按层遍历 */ struct BTreeNode *p;struct BTreeNode *qQUEUE_MAX_SIZE;int front = 0, rear = 0;if(bt != NULL) /* 将树根指针进队 */rear = (rear + 1) % QUEUE_MAX_SIZE; qrear = bt;while(front != rear) /* 队列非空 */ front = (front + 1) % QUEUE_MAX_SIZE; /* 使队首指针指向队首元素 */ p = qfront; printf(%c , p-data); if(p-lchild != NULL) /* 若结点存在左孩子，则左孩子结点指针进队 */ rear = (rear + 1) % QUEUE_MAX_SIZE; qrear = p-lchild; if(p-rchild != NULL) /* 若结点存在右孩子，则右孩子结点指针进队 */ rear = (rear + 1) % QUEUE_MAX_SIZE; qrear = p-rchild; void printBTree( BTreeNode *bt) /*广义表形式输出二叉树*/ if(bt != NULL) /* 树为空时结束递归，否则执行如下操作 */ printf(%c, bt-data); /* 输出根结点的值 */ if(bt-lchild != NULL | bt-rchild!= NULL) printf(); printBTree(bt-lchild); if(bt-rchild != NULL) printf(,); printBTree(bt-rchild); printf(); void main()struct BTreeNode *bt;char *b; /* 用于存入二叉树广义表的字符串 */initBTree(&bt);printf(input the btree biao: example a(b,c)n); scanf(%s, b); /*b=a(b(c),d(e(f, g),h(,i);*/ createBTree(&bt