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