数据结构上机实习-树图及其应_r_n 用（唯一地确定一棵二叉树）.c

几个C语言数据结构算法的例子

/*************************************************************************
   -------问题描述--------
   唯一地确定一棵二叉树
   　　如果给出了遍历二叉树的前序序列和中序序列，则可以构造出唯一的一棵
   二叉树。试编写实现上述功能的程序。

   -------基本要求--------
   已知一棵二叉树的前序和中序序列，试设计完成下列任务的一个算法：
   1.构造一棵二叉树。
   2.证明构造正确。(即分别以前序和中序遍历该树，将得到的结果与给出的序列
     进行进行比较)

   -------测试数据--------
   前序序列为ABDEGCFHIJ
   中序序列为DBGEAHFIJC

   -------实现提示-------
   1.用两个一维数组A和B分别存放前序和中序序列。
   2.根据定义，前序序列中第一个元素一定是树根，在中序序列中该元素之前的
     所有元素一定在左子树中，其余元素一定则在右子树中。所以，首先从数组A
      中取出第一个元素A[0]作为根结点，然后在数组B中找到A[0]，以它为界，在
      其前面的是左子树中序序列，在它后面的是右子树中序序列。
   3.若左子树不为空，沿前序序列向后移动，找到左子树根结点，转2。
   4.左子树构造完毕后，若右子树不为空，沿前序序列向后移到，找到右子树根结点，
   　转2
   5.前序序列中各元素取完则二叉树构造完毕。
   6.对二叉树进行前序和中序遍历，并将结果分别与数组A和B进行比较。若相同，则
   　证明二叉树构造正确。

**************************************************************************/
#include <stdio.h>
#define MAXLONG 20
#define NULL 0

typedef char elemtype;

char A[MAXLONG], B[MAXLONG];

typedef struct node {
     elemtype Data;
     struct node * LChild;
     struct node * RChild;
} treenode;

/* 初始化某结点 */
void Initiate(treenode * t) {
     t->Data=0;
     t->LChild = NULL;
     t->RChild = NULL;
}

void pre(treenode * head) {
     if(head==NULL)
               return;
     
     printf("%c",head->Data);
     pre(head->LChild);
     pre(head->RChild);
}

void zhong(treenode * head) {
     if(head==NULL)
          return;

     zhong(head->LChild);
     printf("%c",head->Data);
     zhong(head->RChild);
}
     
treenode *  bintree(int i, int j, int u, int v){
     int k;
     treenode * head, * s;

     printf(" %d, %d, %d, %d\n",i,j,u,v);
     head= NULL;
     if(i<=j) {
          head=(treenode * )malloc(sizeof(treenode));
          head->Data = A[i];
          k = u;
          while(B[k]!=A[i]) k++;
          if(k==u) head->LChild = NULL;
          else {
               printf("left  ");
               s=bintree(i+1, i+k-u, u, k-1);
               head->LChild = s;
          }

          if(k==v) head->RChild = NULL;
          else {
               printf("right ");
               s = bintree(i+k+1-u, j, k+1, v);
               head->RChild = s;
          }
     }
     return head;
}

main() {
     int i, j;
     int strlength=0;
     treenode * head;

     clrscr();
     printf("Input Qianxu (less than 20) :");
     scanf("%s",A);
     printf("Input Zhongxu(less than 20) :");
     scanf("%s",B);
     printf("\nQianxu is  : %s\nZhongxu is : %s\n",A, B);

     while(A[strlength]!='\0') {
          strlength++;
          printf("%d ",strlength);
     }
     strlength--;

     printf("\n\nhead  ");
     head=bintree(0, strlength, 0, strlength);

     printf("\n");
     pre(head);
     printf("\n");
     zhong(head);
}