ADT Tree Data 树是由一个根结点和若干棵子树构成， 树中结点具有相同数据类型及层次关系 Operation InitTree 前置条件：树不存在 输入：无 功能：初始化一棵树 输出：无 后置条件：构造一个空树 DestroyTree 前置条件：树已存在 输入：无 功能：销毁一棵树 输出：无 后置条件：释放该树占用的存储空间 Root 前置条件：树已存在 输入：无 功能：求树的根结点 输出：树的根结点的信息 后置条件：树保持不变 Parent 前置条件：树已存在 输入：结点x 功能：求结点x的双亲 输出：结点x的双亲的信息 后置条件：树保持不变 Depth 前置条件：树已存在 输入：无 功能：求树的深度 输出：树的深度 后置条件：树保持不变 PreOrder 前置条件：树已存在 输入：无 功能：前序遍历树 输出：树的前序遍历序列 后置条件：树保持不变 PostOrder 前置条件：树已存在 输入：无 功能：后序遍历树 输出：树的后序遍历序列 后置条件：树保持不变 endADT
树的前序遍历操作定义为： 若树为空，不进行遍历；否则 ⑴ 访问根结点； ⑵ 按照从左到右的顺序前序遍历根结点的每一棵子树。
树的后序遍历操作定义为： 若树为空，则遍历结束；否则 ⑴ 按照从左到右的顺序后序遍历根结点的每一棵子树； ⑵ 访问根结点。
树的层序遍历操作定义为： 从树的第一层（即根结点）开始，自上而下逐层遍历，在同一层中，按从左到右的顺序对结点逐个访问。
PostOrder 前置条件：二叉树已存在 输入：无 功能：后序遍历二叉树 输出：二叉树中结点的一个线性排列 后置条件：二叉树不变 LeverOrder 前置条件：二叉树已存在 输入：无 功能：层序遍历二叉树 输出：二叉树中结点的一个线性排列 后置条件：二叉树不变 endADT
template class BiTree { public: BiTree(); ~BiTree( ); void PreOrder(){PreOrder(root);} void InOrder() {InOrder(root);} void PostOrder() {PostOrder(root);} void LevelOrder(){LeverOrder(root)}; private: BiNode *root; BiNode * Creat( ); void Release(BiNode *root); void PreOrder(BiNode *root); void InOrder(BiNode *root); void PostOrder(BiNode *root); void LevelOrder(BiNode *root); };
template void BiTree::PreOrder(BiNode *root) { if (root ==NULL) return; else { cout<data; PreOrder( ); PreOrder( ); } }
template void BiTree::PreOrder(BiNode *root) { SeqStack<BiNode *> s; while (root!=NULL | | !s.empty()) { while (root!= NULL) { cout<data; s.push（root）; root=root->lchild; } if (!s.empty()) { root=s.pop(); root=root->rchild; } } }
template class BiTree{ public: BiTree(); ~BiTree( ); void PreOrder(){PreOrder(root);} void InOrder() {InOrder(root);} void PostOrder() {PostOrder(root);} void LevelOrder(); private: BiNode *root; void Creat(BiNode *& root); void Release(BiNode *root); void PreOrder(BiNode *root); void InOrder(BiNode *root); void PostOrder(BiNode *root); void LevelOrder(BiNode *root); };
template void BiTree::Creat(BiNode * &root ) { T ch; cout<<“请输入创建一棵二叉树的结点数据”<<endl; cin>>ch; if (ch=="#") root = NULL; else{ root = new BiNode; //生成一个结点 root->data=ch; Creat(root->lchild ); //递归建立左子树 Creat(root->rchild); //递归建立右子树 } }
template void BiTree::PostOrder(BiNode *root) { if (root==NULL) return; else { PostOrder(root->lchild); PostOrder(root->rchild); cout<data; } }
