二叉树的3种遍历方式,前序，后序和中序，先访问根节点就是
前序，类似的，最后访问根节点就是后序。运行结果如下，如果不明白，不妨自己动手构造。
代码比较简单，如下：
/**//********************************************************************
created: 2005/12/30
created: 30:12:2005 10:39
filename: bintree.h
author: Liu Qi
purpose: 二叉树的3种遍历方式,前序，后序和中序，先访问根节点就是
前序，类似的，最后访问根节点就是后序
*********************************************************************/
#ifndef BINTREE_H
#define BINTREE_H
#include <stdio.h>
#include <malloc.h>
#include <assert.h>
#include "bintree.h"
typedef int ElemType;
typedef struct treeT
{
ElemType key;
struct treeT* left;
struct treeT* right;
}treeT, *pTreeT;
/**//*===========================================================================
* Function name: BT_MakeNode
* Parameter: target:元素值
* Precondition: None
* Postcondition: NULL != pTreeT
* Description: 构造一个tree节点，置左右指针为空，并且返回指向新节点的指针
* Return value: 指向新节点的指针
* Author: Liu Qi, [12/30/2005]
===========================================================================*/
pTreeT BT_MakeNode(ElemType target)
{
pTreeT pNode = (pTreeT) malloc(sizeof(treeT));
assert( NULL != pNode );
pNode->key = target;
pNode->left = NULL;
pNode->right = NULL;
return pNode;
}
/**//*===========================================================================
* Function name: BT_Insert
* Parameter: target:要插入的元素值, pNode:指向某一个节点的指针
* Precondition: NULL != ppTree
* Description: 插入target到pNode的后面
* Return value: 指向新节点的指针
* Author: Liu Qi, [12/29/2005]
===========================================================================*/
pTreeT BT_Insert(ElemType target, pTreeT* ppTree)
{
pTreeT Node;
assert( NULL != ppTree );
Node = *ppTree;
if (NULL == Node)
{
return *ppTree = BT_MakeNode(target);
}
if (Node->key == target) //不允许出现相同的元素
{
return NULL;
}
else if (Node->key > target) //向左
{
return BT_Insert(target, &Node->left);
}
else
{
return BT_Insert(target, &Node->right);
}
}
/**//*===========================================================================
* Function name: BT_PreOrder
* Parameter: root:树根节点
* Precondition: None
* Description: 前序遍历
* Return value: void
* Author: Liu Qi, [12/29/2005]
===========================================================================*/
void BT_PreOrder(pTreeT root)
{
if (NULL != root)
{
printf(" %d\n", root->key);
BT_PreOrder(root->left);
BT_PreOrder(root->right);
}
}
/**//*===========================================================================
* Function name: BT_InOrder
* Parameter: root:树根节点
* Precondition: None
* Description: 中序遍历
* Return value: void
* Author: Liu Qi, [12/30/2005]
===========================================================================*/
void BT_InOrder(pTreeT root)
{
if (NULL != root)
{
BT_InOrder(root->left);
printf(" %d\n", root->key);
BT_InOrder(root->right);
}
}
/**//*===========================================================================
* Function name: BT_PostOrder
* Parameter: root:树根节点
* Precondition: None
* Description: 后序遍历
* Return value: void
* Author: Liu Qi, [12/30/2005]
===========================================================================*/
void BT_PostOrder(pTreeT root)
{
if (NULL != root)
{
BT_PostOrder(root->left);
BT_PostOrder(root->right);
printf(" %d\n", root->key);
}
}
#endif
上面的代码中有个地方需要注意，那就是BT_Insert,参数使用的是指针的指针。
下面是测试代码：
#include <stdio.h>
#include <stdlib.h>
#include "bintree.h"
#include <time.h>
#define MAX_CNT 5
#define BASE 100
int main(int argc, char *argv[])
{
int i;
pTreeT root = NULL;//BT_MakeNode(100);
srand( (unsigned)time( NULL ) );
for (i=0; i<MAX_CNT; i++)
{
BT_Insert(rand() % BASE, &root);
}
printf("PreOrder:\n");
BT_PreOrder(root);
printf("\n");
printf("InOrder:\n");
BT_InOrder(root);
printf("\n");
printf("PostOrder:\n");
BT_PostOrder(root);
printf("\n");
return 0;
}