4.cpp

几个常用的数据结构算法：堆栈、链表、二叉树、图等。

#include<stdio.h>
#include<stdlib.h>
#define N   7
#define OVERFLOW   -2
#define  OK 1
typedef struct BiTNode {
	char data;
    struct	BiTNode *lchild,*rchild;
}BiTNode,*BiTree;

typedef struct {
	char data;
	int lchild,rchild;
}treenode;

int	CreateBiTree(BiTree &T);     //创建二叉树的二叉链表形式
int traverse(BiTree Q,treenode b[]);  //转换存储形式
static int j=0 ;
void main()
{   
	int i;
	BiTree P;
	treenode a[N + 1];
	a[0].data = 7;    //0号单元放节点的个数
	printf("按先序序列建立二叉树的二叉链表:\n");

	CreateBiTree(P);
	traverse(P,a);

	printf("本题的标号采用完全二叉树的形式，0表示该节点没有该孩子  \n");
	printf("输出二叉树的静态数组形式：\n");
	printf("下标  data  lchild  rchild\n");
	for(i =1 ;i < N + 1;i++)
		printf(" %d     %c      %d       %d\n",i,a[i].data,a[i].lchild,a[i].rchild);
}

int	CreateBiTree(BiTree &T)
{
	char ch;
    
	scanf("%c",&ch);
	if(ch==' ')  T = NULL;
	else 
	{
		if(!(T = (BiTNode *)malloc(sizeof(BiTNode))))
			exit(OVERFLOW);
        T->data = ch;             //生成根节点
    	CreateBiTree(T->lchild);  //构造左子树
	    CreateBiTree(T->rchild);  //构造右子树
	}
    return OK;
}
int traverse(BiTree Q,treenode b[])
{  int i;  ++j;
	i=j;
	if(Q){
		b[i].data = Q->data;
		printf("%c ",b[i].data);
		{
		b[i].lchild = traverse(Q->lchild,b);
		b[i].rchild = traverse(Q->rchild,b);
			return i;
		}
	}
	else  j--; return 0;
}