头文件
ElemType.h
/****ElemType.h - ElemType的定义*****/
#ifndef ELEMTYPE_H#define ELEMTYPE_H
typedef char ElemType;
int compare(ElemType x, ElemType y);void visit(ElemType e);
#endif /* ELEMTYPE_H */DynaLnkBiTree.h
/****DynaLnkBiTree.h - 动态链式二叉树的定义*****/
#if !defined(DYNALNKBITREE_H)#define DYNALNKBITREE_H
#include "ElemType.h"
/*------------------------------------------------------------// 二叉树结构的定义------------------------------------------------------------*/
typedef struct BiNode{ ElemType data; // 结点数据元素 struct BiNode *l; // 结点的左孩子指针 struct BiNode *r; // 结点的右孩子指针} BinTNode, *BinTree;
enum LR {LEFT, RIGHT};
/*------------------------------------------------------------// 二叉树的基本操作------------------------------------------------------------*/
bool InitBinTree(BinTree *T);void DestroyBinTree(BinTree *T);bool CreateBinTree(BinTree *T);void ClearBinTree(BinTree *T);bool BinTreeEmpty(BinTree T);int BinTreeDepth(BinTree T);BinTNode *Root(BinTree T);bool NodeExist(BinTree T, BinTNode* n);ElemType Value(BinTree T, BinTNode* n);void Assign(BinTree T, BinTNode* n, ElemType e);BinTNode* Parent(BinTree T, BinTNode* n);BinTNode* LeftChild(BinTree T, BinTNode* n);BinTNode* RightChild(BinTree T, BinTNode* n);BinTNode* LeftSibling(BinTree T, BinTNode* n);BinTNode* RightSibling(BinTree T, BinTNode* n);void InsertNode(BinTree T, BinTNode* p, LR d, BinTNode* n);void DeleteNode(BinTree T, BinTNode* p, LR d);void PreOrderTraverse(BinTree T, void (*fp)(ElemType));void InOrderTraverse(BinTree T, void (*fp)(ElemType));void PostOrderTraverse(BinTree T, void (*fp)(ElemType));void LevelOrderTraverse(BinTree T, void (*fp)(ElemType));
#endif /* DYNALNKBITREE_H */
主函数
Lab.cpp
#include <stdio.h>#include <stdlib.h>#include "DynaLnkBiTree.h"
int main(){ BinTree T,V; InitBinTree(&T); InitBinTree(&V); CreateBinTree(&T); system("pause"); return 0;}
#include <iostream>using namespace std;
int main(void){
system("pause"); return 0;}
实现函数
ElemType.cpp
/****ElemType.cpp - ElemType的实现*****/
#include <stdio.h>#include "ElemType.h"
int compare(ElemType x, ElemType y){ return(x-y);}
void visit(ElemType e){ printf("%cn", e);}DynaLnkBiTree.cpp
/****DynaLnkBiTree.cpp - 动态链式二叉树，即二叉树的动态链式存储实现***题目：实验6-1 二叉树的动态链式存储实现******/
#include <stdlib.h>#include <stdio.h>#include <malloc.h>#include <memory.h>#include <assert.h>#include "DynaLnkBiTree.h"
/*------------------------------------------------------------操作目的： 初始化二叉树初始条件： 无操作结果： 构造空二叉树函数参数： BinTree *T 待初始化的二叉树返回值： bool 操作是否成功------------------------------------------------------------*/bool InitBinTree(BinTree *T){
*T = NULL; return true;
}
/*------------------------------------------------------------操作目的： 销毁二叉树初始条件： 二叉树T已存在操作结果： 销毁二叉树函数参数： BinTree *T 待销毁的二叉树返回值： 无------------------------------------------------------------*/void DestroyBinTree(BinTree *T){ assert(T != NULL);
DestroyBinTree(&(*T)->l); DestroyBinTree(&(*T)->r); free(T); *T = NULL;}
/*------------------------------------------------------------操作目的： 创建二叉树初始条件： 二叉树T已存在操作结果： 销毁二叉树函数参数： BinTree *T 二叉树T返回值： bool 操作是否成功参考提示： 请按照教材131页算法6.4的方式来创建二叉树。------------------------------------------------------------*/bool CreateBinTree(BinTree *T){ char c=NULL; scanf("%c",c); fflush(stdin); if (c == ' ') { *T = NULL; return true; } else { T = (BinTree*)malloc(sizeof(BinTNode)); if (*T == NULL) { return false; } (*T)->data = c;
CreateBinTree(&(*T)->l); CreateBinTree(&(*T)->r); } return true;}
/*------------------------------------------------------------操作目的： 清空二叉树初始条件： 二叉树T已存在操作结果： 清空二叉树函数参数： BinTree *T 待清空的二叉树返回值： 无------------------------------------------------------------*/void ClearBinTree(BinTree *T){ assert( T != NULL); ClearBinTree(&(*T)->l); ClearBinTree(&(*T)->r); T = NULL;
}
/*------------------------------------------------------------操作目的： 二叉树判空初始条件： 二叉树T已存在操作结果： 若T为空，则返回true；否则返回false函数参数： BinTree T 二叉树T返回值： bool 二叉树是否为空------------------------------------------------------------*/bool BinTreeEmpty(BinTree T){ if (T) { return false; } return true;}
/*------------------------------------------------------------操作目的： 二叉树求深度初始条件： 二叉树T已存在操作结果： 返回二叉树T的深度函数参数： BinTree T 二叉树T返回值： int 二叉树的深度------------------------------------------------------------*/int BinTreeDepth(BinTree T){ int l,r; if (T == NULL) { return 0; } if (T->l == NULL && T->r == NULL) { return 1; }
l = BinTreeDepth(T->l) + 1; r = BinTreeDepth(T->r) + 1; return l>r ? l:r;}
/*------------------------------------------------------------操作目的： 得到二叉树的根结点初始条件： 二叉树T已存在操作结果： 返回二叉树T的根结点函数参数： BinTree T 二叉树T返回值： BinTNode* 二叉树的根结点指针------------------------------------------------------------*/BinTNode *Root(BinTree T){
assert(T != NULL); return T;}
/*------------------------------------------------------------操作目的： 判断结点n是否为树T的合法结点初始条件： 二叉树T已存在操作结果： n为T的结点返回true，否则返回false函数参数： BinTree T 二叉树T BinTNode* n 二叉树的结点n返回值： bool 结点n是否存在与二叉树T中------------------------------------------------------------*/bool NodeExist(BinTree T, BinTNode* n){ assert(T != NULL); assert(n != NULL); if (T == n) { return true; } else if (NodeExist(T->l,n)) { return true; } else if (NodeExist(T->r,n)) { return true; } else { return false; }
}
/*------------------------------------------------------------操作目的： 得到二叉树指定结点的值初始条件： 二叉树T已存在，n是二叉树T中的结点操作结果： 返回结点n的值函数参数： BinTree T 二叉树T BinTNode* n 二叉树结点n返回值： ElemType 结点n的值------------------------------------------------------------*/ElemType Value(BinTree T, BinTNode* n){ assert(n != NULL);
if (NodeExist(T,n)) { return n->data; }}
/*------------------------------------------------------------操作目的： 对二叉树的指定结点赋值初始条件： 二叉树T已存在，n是二叉树T中的结点操作结果： 操作成功返回true，操作失败返回false函数参数： BinTree T 二叉树T BinTNode* n 二叉树结点n ElemType e 结点值返回值： 无------------------------------------------------------------*/void Assign(BinTree T, BinTNode* n, ElemType e){ assert(T !=NULL); assert(n != NULL); if (NodeExist(T,n)) { T->data = e;
}
}
/*------------------------------------------------------------操作目的： 得到二叉树指定结点的父结点初始条件： 二叉树T已存在，n是二叉树T中的结点操作结果： 如果二叉树结点n有父结点则返回父结点指针，否则返回NULL函数参数： BinTree T 二叉树T BinTNode* n 二叉树结点n返回值： BinTNode* 父结点指针------------------------------------------------------------*/BinTNode* Parent(BinTree T, BinTNode* n){ assert(n!=NULL); //空、 if (T==NULL) { return NULL; } if (T->l == NULL && T->r == NULL) { return NULL; } if(T->l == n || T->r == n) { return T; } //3.有左右 BinTree tmp; if (tmp == Parent(T->l,n)!=NULL) { return tmp; } if (tmp == Parent(T->r,n)!=NULL) { return tmp; }
}
/*------------------------------------------------------------操作目的： 得到二叉树指定结点的左孩子初始条件： 二叉树T已存在，n是二叉树T中的结点操作结果： 如果二叉树结点n有左孩子则返回左孩子结点指针，否则返回NULL函数参数： BinTree T 二叉树T BinTNode* n 二叉树结点n返回值： BinTNode* 左孩子结点指针------------------------------------------------------------*/BinTNode* LeftChild(BinTree T, BinTNode* n){ assert(T != NULL); assert(n != NULL);
if (LeftChild(T->l,n)) { return T->l; } return NULL;}
/*------------------------------------------------------------操作目的： 得到二叉树指定结点的右孩子初始条件： 二叉树T已存在，n是二叉树T中的结点操作结果： 如果二叉树结点n有右孩子则返回右孩子结点指针，否则返回NULL函数参数： BinTree T 二叉树T BinTNode* n 二叉树结点n返回值： BinTNode* 右孩子结点指针------------------------------------------------------------*/BinTNode* RightChild(BinTree T, BinTNode* n){ assert(T != NULL); assert(n != NULL);
if (RightChild(T->r,n)) { return T->r; } return NULL;}
/*------------------------------------------------------------操作目的： 得到二叉树指定结点的左兄弟初始条件： 二叉树T已存在，n是二叉树T中的结点操作结果： 如果二叉树结点n有左兄弟则返回左兄弟结点指针，否则返回NULL函数参数： BinTree T 二叉树T BinTNode* n 二叉树结点n返回值： BinTNode* 左兄弟结点指针------------------------------------------------------------*/BinTNode* LeftSibling(BinTree T, BinTNode* n){ BinTree tmp; tmp = Parent(T,n); if (tmp->l) { return tmp->l; } return NULL;}
/*------------------------------------------------------------操作目的： 得到二叉树指定结点的右兄弟初始条件： 二叉树T已存在，n是二叉树T中的结点操作结果： 如果二叉树结点n有右兄弟则返回右兄弟结点指针，否则返回NULL函数参数： BinTree T 二叉树T BinTNode* n 二叉树结点n返回值： BinTNode* 右兄弟结点指针------------------------------------------------------------*/BinTNode* RightSibling(BinTree T, BinTNode* n){ BinTree tmp; tmp = Parent(T,n); if (tmp->r) { return tmp->r; } return NULL;}
/*------------------------------------------------------------操作目的： 在二叉树中插入结点初始条件： 二叉树T已存在，p是二叉树T中的结点，n为待插入的结点操作结果： 在二叉树的p结点之前插入结点n函数参数： BinTree T 二叉树T BinTNode* p 二叉树结点p LR d 二叉树结点p成为新结点n的左孩子或者右孩子 BinTNode* p 待插入结点n返回值： 无------------------------------------------------------------*/void InsertNode(BinTree T, BinTNode* p, LR d, BinTNode* n){ assert(n != NULL); //2.找p的位置，找p的父节点 BinTree tmp; tmp = Parent(T,p); if (tmp != NULL) { if (tmp->l == p) { tmp->l = n; n->l = p; n->r = NULL; } if (tmp->r == p) { tmp->r = n; n->r = p; n->l = NULL; } }
}
/*------------------------------------------------------------操作目的： 在二叉树中删除结点初始条件： 二叉树T已存在，p是二叉树T中的结点操作结果： 删除二叉树的p结点函数参数： BinTree T 二叉树T BinTNode* p 二叉树结点p LR d 结点p的左孩子或者右孩子来取代p返回值： 无------------------------------------------------------------*/void DeleteNode(BinTree T, BinTNode* p, LR d){ assert(NodeExist(T,p)); BinTree tmp; tmp = Parent(T,p); if (tmp != NULL) { if (tmp->l == p) { tmp->l = p->l; tmp->l = p->r; free(p); p = NULL; } if (tmp->r == p) { tmp->r = p->l; tmp->r = p->r; free(p); p = NULL; }
}}
/*------------------------------------------------------------操作目的： 先序遍历二叉树初始条件： 二叉树T已存在操作结果： 先序的方式，对二叉树的每个结点调用(*fp)一次且仅一次函数参数： BinTree T 二叉树T *fp 访问函数指针返回值： 无------------------------------------------------------------*/void PreOrderTraverse(BinTree T, void (*fp)(ElemType)){ assert(T != NULL); (*fp)(T->data); PreOrderTraverse(T->l,fp); PreOrderTraverse(T->r,fp);
}
/*------------------------------------------------------------操作目的： 中序遍历二叉树初始条件： 二叉树T已存在操作结果： 中序的方式，对二叉树的每个结点调用(*fp)一次且仅一次函数参数： BinTree T 二叉树T *fp 访问函数指针返回值： 无------------------------------------------------------------*/void InOrderTraverse(BinTree T, void (*fp)(ElemType)){ assert(T != NULL); InOrderTraverse(T->l,fp); (*fp)(T->data); InOrderTraverse(T->r,fp);}
/*------------------------------------------------------------操作目的： 后序遍历二叉树初始条件： 二叉树T已存在操作结果： 后序的方式，对二叉树的每个结点调用(*fp)一次且仅一次函数参数： BinTree T 二叉树T *fp 访问函数指针返回值： 无------------------------------------------------------------*/void PostOrderTraverse(BinTree T, void (*fp)(ElemType)){ assert(T != NULL); PostOrderTraverse(T->l,fp); PostOrderTraverse(T->r,fp); (*fp)(T->data);}
/*------------------------------------------------------------操作目的： 层序遍历二叉树初始条件： 二叉树T已存在操作结果： 层序的方式，对二叉树的每个结点调用(*fp)一次且仅一次函数参数： BinTree T 二叉树T *fp 访问函数指针返回值： 无------------------------------------------------------------*/void LevelOrderTraverse(BinTree T, void (*fp)(ElemType)){ BinTree q[100]; int front = 0; int rear =1; q[0]=T; while(front<rear) { if (q[front]) { fp(q[front]->data); q[rear++] = q[front]->l; q[rear++] = q[front]->r; front++; } else { front++; } }}
评论