后序遍歷還沒有明白，繼續(xù)學習^_^，過幾天寫個huffman編碼的例子來玩玩，不多說了，看代碼吧，注意：程序申請的空間并沒有釋放^_^
/**//********************************************************************
created: 2005/12/30
created: 30:12:2005 10:39
filename: bintree.h
author: Liu Qi
purpose: 二叉樹的3種遍歷方式(包括非遞歸實現(xiàn)),前序，后序和中序，先訪問根節(jié)點就是
前序(部分書籍稱為先根遍歷,個人覺得該說法更好^_^)，類似的，最后訪問根節(jié)點就是后序
*********************************************************************/
#ifndef TREE_H
#define TREE_H
#include <stdio.h>
#include <malloc.h>
#include <stack>
#include <queue>
#include <assert.h>
using namespace std;
typedef int ElemType;
typedef struct treeT
{
ElemType key;
struct treeT* left;
struct treeT* right;
}treeT, *pTreeT;
/**//*===========================================================================
* Function name: visit
* Parameter: root:樹根節(jié)點指針
* Precondition:
* Description:
* Return value:
* Author: Liu Qi, //-
===========================================================================*/
static void visit(pTreeT root)
{
if (NULL != root)
{
printf(" %d\n", root->key);
}
}
/**//*===========================================================================
* Function name: BT_MakeNode
* Parameter: target:元素值
* Precondition: None
* Postcondition: NULL != pTreeT
* Description: 構造一個tree節(jié)點，置左右指針為空，并且返回指向新節(jié)點的指針
* Return value: 指向新節(jié)點的指針
* Author: Liu Qi, [12/30/2005]
===========================================================================*/
static 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:指向某一個節(jié)點的指針
* Precondition: NULL != ppTree
* Description: 插入target到pNode的后面
* Return value: 指向新節(jié)點的指針
* 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) //不允許出現(xiàn)相同的元素
{
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:樹根節(jié)點指針
* Precondition: None
* Description: 前序遍歷
* Return value: void
* Author: Liu Qi, [12/29/2005]
===========================================================================*/
void BT_PreOrder(pTreeT root)
{
if (NULL != root)
{
visit(root);
BT_PreOrder(root->left);
BT_PreOrder(root->right);
}
}
/**//*===========================================================================
* Function name: BT_PreOrderNoRec
* Parameter: root:樹根節(jié)點指針
* Precondition: Node
* Description: 前序(先根)遍歷非遞歸算法
* Return value: void
* Author: Liu Qi, [1/1/2006]
===========================================================================*/
void BT_PreOrderNoRec(pTreeT root)
{
stack<treeT *> s;
while ((NULL != root) || !s.empty())
{
if (NULL != root)
{
visit(root);
s.push(root);
root = root->left;
}
else
{
root = s.top();
s.pop();
root = root->right;
}
}
}
/**//*===========================================================================
* Function name: BT_InOrder
* Parameter: root:樹根節(jié)點指針
* Precondition: None
* Description: 中序遍歷
* Return value: void
* Author: Liu Qi, [12/30/2005]
===========================================================================*/
void BT_InOrder(pTreeT root)
{
if (NULL != root)
{
BT_InOrder(root->left);
visit(root);
BT_InOrder(root->right);
}
}
/**//*===========================================================================
* Function name: BT_InOrderNoRec
* Parameter: root:樹根節(jié)點指針
* Precondition: None
* Description: 中序遍歷,非遞歸算法
* Return value: void
* Author: Liu Qi, [1/1/2006]
===========================================================================*/
void BT_InOrderNoRec(pTreeT root)
{
stack<treeT *> s;
while ((NULL != root) || !s.empty())
{
if (NULL != root)
{
s.push(root);
root = root->left;
}
else
{
root = s.top();
visit(root);
s.pop();
root = root->right;
}
}
}
/**//*===========================================================================
* Function name: BT_PostOrder
* Parameter: root:樹根節(jié)點指針
* 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);
visit(root);
}
}
/**//*===========================================================================
* Function name: BT_PostOrderNoRec
* Parameter: root:樹根節(jié)點指針
* Precondition: None
* Description: 后序遍歷,非遞歸算法
* Return value: void
* Author: Liu Qi, // [1/1/2006]
===========================================================================*/
void BT_PostOrderNoRec(pTreeT root)
{
//學習中，尚未明白
}
/**//*===========================================================================
* Function name: BT_LevelOrder
* Parameter: root:樹根節(jié)點指針
* Precondition: NULL != root
* Description: 層序遍歷
* Return value: void
* Author: Liu Qi, [1/1/2006]
===========================================================================*/
void BT_LevelOrder(pTreeT root)
{
queue<treeT *> q;
treeT *treePtr;
assert( NULL != root );
q.push(root);
while (!q.empty())
{
treePtr = q.front();
q.pop();
visit(treePtr);
if (NULL != treePtr->left)
{
q.push(treePtr->left);
}
if (NULL != treePtr->right)
{
q.push(treePtr->right);
}
}
}
#endif
測試代碼
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include "tree.h"
#define MAX_CNT 5
#define BASE 100
int main(int argc, char *argv[])
{
int i;
pTreeT root = NULL;
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("PreOrder no recursion:\n");
BT_PreOrderNoRec(root);
printf("\n");
//中序
printf("InOrder:\n");
BT_InOrder(root);
printf("\n");
printf("InOrder no recursion:\n");
BT_InOrderNoRec(root);
printf("\n");
//后序
printf("PostOrder:\n");
BT_PostOrder(root);
printf("\n");
//層序
printf("LevelOrder:\n");
BT_LevelOrder(root);
printf("\n");
return 0;
} 如果有興趣不妨運行一下，看看效果^_^
另外請教怎樣讓二叉樹漂亮的輸出，即按照樹的形狀輸出