数据结构基础(六).二叉树

#include <stdio.h>
#include <malloc.h> //要使用到动态内存分配的时候得带上这个头文件
#define MAXSIZE 100

typedef struct tree //定义一个树的结构体
{
  int data;
  struct tree *l; //左子树指针
  struct tree *r; //右子树指针
}TN,*TP; //重命名此结构体结点为TN，重命名指针为TP

TP initTree() //初始化二叉树，手动生成一个简单的二叉树
{
  TP pa,pb,pc,pd,pe,pf; //定义六个节点的指针
  pa=(TP)malloc(sizeof(TN));
  pb=(TP)malloc(sizeof(TN));
  pc=(TP)malloc(sizeof(TN));
  pd=(TP)malloc(sizeof(TN));
  pe=(TP)malloc(sizeof(TN));
  pf=(TP)malloc(sizeof(TN)); //分别分配六段内存
  
  pa->l=pb;
  pa->r=pc;
  pa->data='A'; //初始化A节点

  pb->l=pd;
  pb->r=pe;
  pb->data='B'; //初始化B节点
  
  pc->l=pf;
  pc->r=NULL;
  pc->data='C'; //初始化C节点
  
  pd->l=NULL;
  pd->r=NULL;
  pd->data='D'; //初始化D节点
  
  pe->l=NULL;
  pe->r=NULL;
  pe->data='E'; //初始化E节点
  
  pf->l=NULL;
  pf->r=NULL;
  pf->data='F'; //初始化F节点
  
  return pa;  //反馈a节点作为根节点
}

void preOrder(TP root) //前序遍历
{
  if(NULL == root) return; 
  printf("%c",root->data); //先打印节点值
  preOrder(root->l); //再依次进行左子树递归
  preOrder(root->r); //再依次进行右子树递归

}

void inOrder(TP root) //中序遍历
{
  if(NULL == root) return;
  inOrder(root->l);  //先进行左子树递归
  printf("%c",root->data); //再打印节点值
  inOrder(root->r);  //再依次进行右子树递归
}

void postOrder(TP root) //后序遍历
{
  if(NULL == root) return;
  postOrder(root->l); //先进行左子树递归
  postOrder(root->r); //再依次进行右子树递归
  printf("%c",root->data); //再打印节点值
}

void noOrder(TP root) //层次遍历
{
  TP que[MAXSIZE]; //定义一个节点的指针数组
  int e=0,h=0; //定义队列首尾的下标
  if(NULL == root) return; 
  for(e=0;e<MAXSIZE;e++)que[e]=NULL; //初始化为空
  h=e=0; //首尾置0
  que[e]=root; //将根存入第一个数组元素中
  while (NULL != que[h]) //如果队首节点不为空就循环执行下列代码
  {
    printf("%c",que[h]->data);  //打印出节点值
    if(NULL != que[h]->l) //如果左子叶存在则将其存入队列尾部
      que[++e]=que[h]->l;
    if(NULL != que[h]->r) //如果右子叶存在则将其存入队列尾部
      que[++e]=que[h]->r;
    h++; //处理完一个节点，就向队列中下一个节点移动
  }
}

int main()
{
  TP root=initTree(); //初始化测试
  preOrder(root); //前序遍历测试
  printf("\n");
  inOrder(root); //中序遍历测试
  printf("\n");
  postOrder(root); //后序遍历测试
  printf("\n");
  noOrder(root); //层次遍历测试
  printf("\n");
  return 0;
}

emacs@ubuntu:~/c$ alias gtc
alias gtc='gcc -Wall -g -o'
emacs@ubuntu:~/c$ gtc tree.x tree.c
emacs@ubuntu:~/c$ ./tree.x 
ABDECF
DBEAFC
DEBFCA
ABCDEF
emacs@ubuntu:~/c$