tree.cpp

附件是一个关于树的遍历的例子的源代码程序

//BiTree.h

//二叉树的二叉链结构

#include<malloc.h>
#include<process.h>

typedef struct Node
{
DataType_Tree data;                   //数据域
struct Node *leftChild;       //左孩子指针域
struct Node *rightChild;      //右孩子指针域
}BiTree;

typedef BiTree DataType_Stack;
#include "Stack.h"

//初始化
void Initiate_Tree(BiTree **root)
{
if(NULL==((*root)=(BiTree *)malloc(sizeof(BiTree))))
   exit(0);

(*root)->leftChild=NULL;
(*root)->rightChild=NULL;
}

//插入左子树
BiTree *InsertLeftChild(BiTree *curr,DataType_Tree x)
{
BiTree *s;

if(NULL==(s=(BiTree *)malloc(sizeof(BiTree))))
   exit(0);
s->data=x;
s->leftChild=curr->leftChild;
s->rightChild=NULL;
curr->leftChild=s;

return s;
}

//插入右子树
BiTree *InsertRightChild(BiTree *curr,DataType_Tree x)
{
BiTree *s;

if(NULL==(s=(BiTree *)malloc(sizeof(BiTree))))
   exit(0);
s->data=x;
s->leftChild=NULL;
s->rightChild=curr->rightChild;
curr->rightChild=s;

return s;
}

//删除左子树
BiTree *DeleteLeftChild(BiTree *curr)
{
if(NULL==curr||NULL==curr->leftChild)
   return NULL;
free(curr->leftChild);
curr->leftChild=NULL;

return curr;
}

//删除右子树
BiTree *DeleteRightChild(BiTree *curr)
{
if(NULL==curr||NULL==curr->rightChild)
   return NULL;
free(curr->rightChild);
curr->rightChild=NULL;

return curr;
}

//定义visit()
void visit(DataType_Tree item)
{
printf("%c\t",item);
}

//二叉树的前序遍历
void PreOrder(BiTree *root,void (* visit)(DataType_Tree item))
{
if(NULL!=root)
{
   (* visit)(root->data);
   PreOrder(root->leftChild,visit);
   PreOrder(root->rightChild,visit);
}
}

//二叉树的中序遍历
void InOrder(BiTree *root,void (* visit)(DataType_Tree itme))
{
if(NULL!=root)
{
   InOrder(root->leftChild,visit);
   (* visit)(root->data);
   InOrder(root->rightChild,visit);
}
}

//二叉树的后序遍历

void PostOrder(BiTree *root,void (* visit)(DataType_Tree itme))
{
if(NULL!=root)
{
   PostOrder(root->leftChild,visit);
   PostOrder(root->rightChild,visit);
   (* visit)(root->data);
}
}

//二叉树的销毁
void Dstroy(BiTree **root)
{
if(NULL!=(*root)&&NULL!=(*root)->leftChild)
   Dstroy(&(*root)->leftChild);
if(NULL!=(*root)&&NULL!=(*root)->rightChild)
   Dstroy(&(*root)->rightChild);
free(*root);
}

//二叉树前序遍历的堆栈算法
void Nr_PreOrder(BiTree *root,void (* visit)(DataType_Tree itme))
{
LSNode *head;
BiTree *t=root;
DataType_Stack **s;

if(NULL==(s=(DataType_Stack **)malloc(sizeof(DataType_Stack *))))
   exit(0);
Initiate_Stack(&head);
while((NULL!=t)||(NULL!=head->next))
{
   while(NULL!=t)
   {
     (* visit)(t->data);
     Push_Stack(head,t);
     t=t->leftChild;
   }
    if(NULL!=head->next)
   {
        Pop_Stack(head,s);
        t=*s;
        t=t->rightChild;
   }
}

free(s);
}

//二叉树中序遍历的堆栈算法
void Nr_InOrder(BiTree *root,void (* visit)(DataType_Tree itme))
{
LSNode *head;
BiTree *t=root;
DataType_Stack **s;

if(NULL==(s=(DataType_Stack **)malloc(sizeof(DataType_Stack *))))
   exit(0);
Initiate_Stack(&head);
while((NULL!=t)||(NULL!=head->next))
{
   while(NULL!=t)
   {
     Push_Stack(head,t);
     t=t->leftChild;
   }
    if(NULL!=head->next)
   {
        Pop_Stack(head,s);
        t=*s;
    (* visit)(t->data);
        t=t->rightChild;
   }
}

free(s);
}

//Stack.h

//链式堆栈

typedef struct snode
{
DataType_Stack *data;
struct snode *next;
}LSNode;

//初始化
void Initiate_Stack(LSNode **head)
{
if(NULL==((*head)=(LSNode *)malloc(sizeof(LSNode))))
   exit(0);
(*head)->next=NULL;
}

//非空否
int NotEmpty_Stack(LSNode *head)
{
if(NULL==head->next)
   return 0;
else
   return 1;
}

//入栈
int Push_Stack(LSNode *head,DataType_Stack *x)
{
LSNode *s;

if(NULL==(s=(LSNode *)malloc(sizeof(LSNode))))
   exit(0);

s->data=x;
s->next=head->next;
head->next=s;

return 1;
}

//出栈
int Pop_Stack(LSNode *head,DataType_Stack **x)
{
LSNode *s;

if(NULL==head->next)
   return 0;

s=head->next;
*x=head->next->data;
head->next=head->next->next;
free(s);

return 1;
}

//取栈顶元素
int Top_Stack(LSNode *head,DataType_Stack **x)
{
if(NULL==head->next)
   return 0;

*x=head->next->data;
return 1;
}

//销毁栈
void Dstroy(LSNode *head)
{
LSNode *s,*ss;

s=head;
while(NULL!=s)
{
   ss=s;
   s=s->next;
   free(ss);
}
}

//Tree.cpp

//树

#include<stdio.h>
typedef char DataType_Tree;
#include "BiTree.h"

void main()
{
BiTree *root,*p,*pp;
void (* vs)(DataType_Tree);

vs=visit;
Initiate_Tree(&root);
p=InsertLeftChild(root,'A');
p=InsertLeftChild(p,'B');
p=InsertLeftChild(p,'D');
p=InsertRightChild(p,'G');
p=InsertRightChild(root->leftChild,'C');
pp=p;
InsertLeftChild(p,'E');
InsertRightChild(pp,'F');
printf("二叉树前序遍历递归算法:");
PreOrder(root->leftChild,vs);
putchar('\n');
printf("二叉树中序遍历递归算法:");
InOrder(root->leftChild,vs);
putchar('\n');
printf("二叉树后序遍历递归算法:");
PostOrder(root->leftChild,vs);
putchar('\n');
printf("二叉树前序遍历堆栈算法:");
Nr_PreOrder(root->leftChild,visit);
putchar('\n');
printf("二叉树中序遍历堆栈算法:");
Nr_InOrder(root->leftChild,visit);
putchar('\n');
Dstroy(&root);
}