DS之遍历二叉树 - 数据库编程

在二叉树的一些应用中，常常要求在树中查找具有某种特征的结点，或者对树中全部结点逐一进行某种处理。这就提出了一个遍历二叉树的问题，即如何按某条搜索路径巡访树中的每个结点，使得每个结点均被访问一次，而且仅被访问一次。

由二叉树的递归定义可知，二叉树是由三个基本单元构成的：根结点，左子树和右子树。若能依次遍历这三部分，便是遍历了整个二叉树。若限定先左后右的顺序，则遍历二叉树通常有三种算法：先序，中序，后序。

先序遍历二叉树的操作定义为：

若二叉树为空，则空操作；否则;

(1)访问根结点；(2)先序遍历左子树；(3)先序遍历右子树。

中序遍历二叉树的操作定义为：

若二叉树为空，则空操作；否则;

(1)中序遍历左子树；(2)访问根结点；(3)中序遍历右子树。

后序遍历二叉树的操作定义为：

若二叉树为空，则空操作；否则;

(1)后序遍历左子树；(2)后序遍历右子树；(3)访问根结点。

对于二叉树的遍历我们在二叉树的二叉链表上实现。在二叉树的二叉链表的基本操作中也介绍了四种遍历方法，我们就来实现前三种遍历方法。在遍历函数的参数中除了一个指针参数外，还有一个指向函数的指针参数。这个函数最简单的实现为Visit()函数。这个函数最简单的代码为：

Status printElement(TElemType e)//最简单的Visit()函数
{
	cout<
  
    再者就是需要构建二叉表(先序输入数据元素)的代码：
   Status CreateBiTree(BiTree &T)//按先序次序输入二叉树中结点的值（一个字符），空格字符表示空树，构造二叉链表表示的二叉树T
{
	int i=0;
    char a[100];
    cin>>a[i];
    if(a[i]=='#') T=NULL;
    else
	{
         if(!(T=(BiTNode *)malloc(sizeof(BiTNode)))) 
		 {
				  exit(OVERFLOW);
		 }
         T->data=a[i];//生成根结点
         CreateBiTree(T->lchild);   //构造左子树
         CreateBiTree(T->rchild);   //构造右子树
    }
    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;
				   }
			 }
            return ERROR;
		  }
      }
	 else
	 {
	    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;
			  }
		   }
          return ERROR;
	    }
    }
	else
	{
	   return OK;
	}
}

   完整的代码为：

   #include 
    
     
#include 
     
       using namespace std; #define OK 1 #define ERROR 0 #define OVERFLOW -2 typedef char TElemType; typedef int Status; typedef struct BiTNode { TElemType data; struct BiTNode *lchild,*rchild; //左右孩子指针 }BiTNode,*BiTree; Status CreateBiTree(BiTree &T)//按先序次序输入二叉树中结点的值（一个字符），空格字符表示空树，构造二叉链表表示的二叉树T { int i=0; char a[100]; cin>>a[i]; if(a[i]=='#') T=NULL; else { if(!(T=(BiTNode *)malloc(sizeof(BiTNode)))) { exit(OVERFLOW); } T->data=a[i];//生成根结点 CreateBiTree(T->lchild); //构造左子树 CreateBiTree(T->rchild); //构造右子树 } 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; } } return ERROR; } } else { 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; } } return ERROR; } } else { return OK; } } Status printElement(TElemType e)//最简单的Vi

DS之遍历二叉树(一)