二叉树遍历的递归算法程序

69 阅读 0 评论 46 点赞

我是靠谱客的博主爱听歌砖头，最近开发中收集的这篇文章主要介绍二叉树遍历的递归算法程序，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

二叉树的遍历是典型的递归算法。所谓树的遍历是指按某条搜索路径访问树中每个结点，使得每个结点均被访问一次，而且仅被访问一次。我的程序给出了二叉树的先序遍历，中序遍历，后序遍历和求二叉树的深度。程序如下：

#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
#define OK 1
#define ERROR 0
#define OVERFLOW -2
#define MAX(a,b) (a>b?a:b)

typedef char TElemType;
typedef int Status;

//二叉树的二叉链表存储结构
typedef struct BiTNode{
TElemType data;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;

//先序遍历生成二叉树
Status CreatBiTree(BiTree &T){
  TElemType ch,temp;
  printf("输入一个元素: ");
  scanf("%c",&ch);
  temp=getchar(); //结束回车
  if(ch==' ') T=NULL; //输入空格表示结点为空树
  else{
    if(!(T=(BiTree)malloc(sizeof(BiTNode)))) exit(OVERFLOW);
    T->data=ch; //生成根结点
    CreatBiTree(T->lchild); //构造左子树
    CreatBiTree(T->rchild); //构造右子树
  }
  return OK;
}

//打印元素
Status PrintElem(TElemType e){
printf("%c ",e);
return OK;
}

//先序遍历二叉树
Status PreOrderTraverse(BiTree T,Status (* Visit)(TElemType e)){
  if(T){ //二叉树不为空时
    if(Visit(T->data)) //访问根结点
      if(PreOrderTraverse(T->lchild,Visit)) //先序遍历左子树
        if(PreOrderTraverse(T->rchild,Visit)) return OK; //先序遍历右子树
    return ERROR;
  }
  else return OK;
}

//中序遍历二叉树
Status InOrderTraverse(BiTree T,Status (* Visit)(TElemType e)){
  if(T){
    if(InOrderTraverse(T->lchild,Visit))
      if(Visit(T->data))
        if(InOrderTraverse(T->rchild,Visit)) return OK;
    else return ERROR;
  }
  return OK;
}

//后序遍历二叉树
Status PostOrderTraverse(BiTree T,Status (* Visit)(TElemType e)){
  if(T){
    if(PostOrderTraverse(T->lchild,Visit))
      if(PostOrderTraverse(T->rchild,Visit))
        if(Visit(T->data)) return OK;
    else return ERROR;
  }
  return OK;
}

//求二叉树的深度
int BiTreeDepth(BiTree T){
  if(!T) return 0; //二叉树为空树时
  int Dl=0,Dr=0;
  if(T->lchild) Dl=BiTreeDepth(T->lchild); //求左子树深度
  if(T->rchild) Dr=BiTreeDepth(T->rchild); //求右子树深度
  return MAX(Dl,Dr)+1;
}

//主函数
void main()
{
  BiTree T;
  Status (* Visit)(TElemType);
  Visit=PrintElem;
  CreatBiTree(T);
  printf("/n先序遍历:");
  PreOrderTraverse(T,Visit);
  printf("/n中序遍历:");
  InOrderTraverse(T,Visit);
  printf("/n后序遍历:");
  PostOrderTraverse(T,Visit);
  printf("/n二叉树深度为%d",BiTreeDepth(T));
  printf("/n程序结束./n");
}

输出结果为（红色为键盘输入的数据，输入的空格没有显示出来）：

输入一个元素: A
输入一个元素: B
输入一个元素: C
输入一个元素:
输入一个元素:
输入一个元素: D
输入一个元素: E
输入一个元素:
输入一个元素: G
输入一个元素:
输入一个元素:
输入一个元素: F
输入一个元素:
输入一个元素:
输入一个元素: