二叉树的广义表形式(共3页)

1、精选优质文档-倾情为你奉上二叉树的广义表形式2009-06-12 22:15题目：假设二叉树采用二叉链表结构。设计并实现如下算法：输入某棵二叉树的广义表形式，建立该二叉树，并按层次遍历该二叉树。 本演示程序根据提示输入二叉树的广义表形式例如：a(b(c),d(e(f, g),h(,i) 在演示过程序中，用户敲击键盘，即可观看演示结果。 程序执行的命令包括：（1）构造树的广义表 （2）输出构造好的广义表 （3）层次比遍历该二叉树 源程序 (C语言) #include <stdio.h>#include <stdlib.h>#include <malloc.h>

2、#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 B

3、TreeNode *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;

4、 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 =

5、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

6、_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

7、 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,b); printf(&qu