ch5_1.c

本内容为清华大学严蔚敏版数据结构部分算法实现代码

#include<stdio.h>
#include<stdlib.h>
typedef struct node                      /* 树状结构的声明 */
{
  int data;                                      /* 结点数据 */
  struct node *LCHILD;                 /* 指向左子树的指针 */
  struct node *RCHILD;                 /* 指向右子树的指针 */
}Btree;
Btree *insert(Btree *,int);
Btree *create(int *,int);
void preorder(Btree *);
void inorder(Btree *);
void postorder(Btree *);
void main()                                        /* 主程序 */
{
  Btree *root=NULL;                             /* 树根指针 */
  int data[7]={4, 2, 6, 1, 3, 5, 7};   /* 二叉树结点数据 */
  root=create(data, 7);                      /* 建立二叉树 */
  printf("前序遍历的结果:\n");          /* 前序法遍历二叉树 */
  preorder(root);
  printf("\n中序遍历的结果:\n");
  inorder(root);                         /* 中序法遍历二叉树 */
  printf("\n后序遍历的结果:\n");
  postorder(root);                       /* 后序法遍历二叉树 */
}
Btree *insert(Btree *root, int value)
{                                            /* 插入二叉树的结点 */
  Btree *newnode;                               /* 新结点指针 */
  Btree *current;                          /* 目前树结点指针 */
  Btree *parent;                               /* 父结点指针 */
    newnode=(Btree *)malloc(sizeof(Btree));  /* 建立新结点 */
  newnode->data=value;                       /* 保存结点内容 */
  newnode->LCHILD=NULL;                /* 左子树指针初值设定 */
  newnode->RCHILD=NULL;                /* 右子树指针初值设定 */
  if(root==NULL)                              /* 是否为根结点 */
  {
    return newnode;                       /* 返回新结点的位置 */
  }
  else
  {
    current=root;                     /* 保留目前树状结构指针 */
    while(current!=NULL)
    {
      parent=current;                      /* 保留父结点指针 */
      if(current->data>value)                /* 比较结点值 */
        current=current->LCHILD;                 /* 左子树 */
      else
        current=current->RCHILD;                 /* 右子树 */
    }
    if(parent->data>value)                   /* 将数据加入 */
      parent->LCHILD=newnode;                    /* 左子树 */
    else
    parent->RCHILD=newnode;                      /* 右子树 */
  }
  return root;                               /* 返回树根指针 */
}
Btree *create(int *data, int len)            /*建立二叉树*/
{
  Btree *root=NULL;                                /*树根指针*/
  int i;
  for(i=0; i<len; i++)                  /*用循环建立树状结构*/
    root=insert(root, data[i]);
  return root;
}
void preorder(Btree *T)                   /* 二叉树前序遍历 */
{
  if(T!=NULL)                                     /* 终止条件 */
  {
    printf("%2d", T->data);                /* 输出结点内容 */
    preorder(T->LCHILD);                      /* 遍历左子树 */
    preorder(T->RCHILD);                      /* 遍历右子树 */
  }
}
void inorder(Btree *T)                 /* 二叉树的中序遍历 */
{
  if(T!=NULL)                                    /* 终止条件 */
  {
    inorder(T->LCHILD);                       /* 遍历左子树 */
    printf("%2d", T->data);                /* 输出结点内容 */
    inorder(T->RCHILD);                       /* 遍历右子树 */
  }
}
void postorder(Btree *T)               /* 二叉树的后序遍历 */
{
  if(T!=NULL)                                    /* 终止条件 */
  {
    postorder(T->LCHILD);                    /* 遍历左子树 */
    postorder(T->RCHILD);                    /* 遍历右子树 */
    printf("%2d", T->data);                /* 输出结点内容 */
  }
}