编辑代码

/********************算法6.1 二叉树建立（129页）***********************
函数功能：层次输入法创建二叉链表
函数输入：无
函数输出：二叉链表根结点
键盘输入：按完全二叉树结点编号规则顺序输入结点值，
空结点为@，#为结束符
***************************************************/
#include <stdio.h>
#include <stdlib.h>
#define maxsize 1024
typedef  char datatype;

typedef struct node {
	datatype  data;
	struct node *lchild, *rchild;
} bitree;

bitree *CreaTree() {            //建立二叉树函数，返回根结点指针
	char ch;                   //结点信息变量
	bitree *q[maxsize];       // 设立指针类型数组来构成队列，放树结点地址
	int front, rear;         // 队头指针和队尾指针变量
	bitree *root, *s;        //根结点指针和中间指针变量
	root = NULL;             //二叉树置空
	front = 1;
	rear = 0;              //设置队列的指针变量初值

	while ((ch = getchar()) != '#') { //输入一个字符，#为结束符
		s = NULL;
		if (ch != '@') {           //@表示虚节点。若非虚，则建立新结点
			s = (bitree *)malloc(sizeof(bitree));
			s->data = ch;
			s->lchild = NULL;
			s->rchild = NULL;
		}
		rear++;           //尾指针加1，指向新结点地址应存放的单元
		q[rear] = s;     //将新结点地址入队或虚结点指针NULL入队
		if (rear == 1)
			root = s;         // 输入的第一个结点为根结点
		else {
			if (s && q[front])      // 孩子和双亲结点都不是虚结点
				if (rear % 2 == 0)
					q[front]->lchild = s; // rear为偶数，新结点为左孩子
				else
					q[front]->rchild = s; //rear为奇数且不等于1，新结点为右孩子
			if (rear % 2 == 1)  //结点*q[front]的两个孩子处理完毕，出队
				front++;  //队头指针指向下一个待链接的双亲结点
		}
	}
	return root;
}

int main() {
	bitree *tPtr;
	printf("层次输入法创建二叉链表\n");
	printf("按完全二叉树结点编号规则顺序输入结点值，空结点为@，#为结束符。\n");
	printf("如输入 ABCDE@F@@@G@@H@#  (教材第131页图6.10中的二叉树，层次输入结点)。\n");
	tPtr = CreaTree();

	return 0;
}

//举例  ABCDE@F@@@G@@H@#  (教材第131页图6.10中的二叉树，层次输入结点)