//BiTNode.h 二叉链表结点类型结构体
#ifndef _yhhBITNODE_H_
#define _yhhBITNODE_H_
template<typename T>struct BiTNode
{
T data;
BiTNode<T> *lchild, *rchild;
};
#endif
//BiTree.h 二叉链表结构的二叉树类（BiTree类）
#ifndef _yhhBITREE_H_
#define _yhhBITREE_H_
enum Tags {Left, Right};
enum style {Pre, In, Post};//枚举类型遍历方式
template<typename T>
struct StackElem
{
BiTNode<T> *p;
Tags flag;
};
template<typename D>class SOSTree;
template<typename T>class BiTree
{
friend SOSTree<struct S>;
protected:
BiTNode<T> *root;
private:
void DestroyBiTree(BiTNode<T>* &t) //指针的引用
{//销毁t所指的二叉树
if(t!=NULL)
{
DestroyBiTree(t->lchild);
DestroyBiTree(t->rchild);
delete t;
t=NULL;
}
}
public:
BiTree()
{
root=NULL;
}
~BiTree()
{
DestroyBiTree(root);
}
void CreateBiTreeFromFile(ifstream &f)
{
T e;
InputFromFile(f, e);
if(e==Nil)
return;
root=new BiTNode<T>;
assert(root!=NULL);
root->data=e;
BiTree<T> left, right;
left.CreateBiTreeFromFile(f); //递归创建左子树
right.CreateBiTreeFromFile(f); //递归创建右子树
root->lchild=left.root; //根节点的左孩子接左子树的根节点
left.root=NULL;
root->rchild=right.root;
right.root=NULL;
}
bool BiTreeEmpty()const
{
return root==NULL;
}
int BiTreeDepth(BiTNode<T>* t)const
{//返回t所指树的深度
int i, j;
if(t==NULL)
return 0;
else
{
i=BiTreeDepth(t->lchild);//i为左子树的深度，t的左子树为空，i=0;
j=BiTreeDepth(t->rchild);
return i>j?i+1:j+1;
}
}
void PreOrderTraverse(void(*visit)(BiTNode<T>*))const
{//前序(利用栈)遍历二叉树
stack<BiTNode<T>*> s;
BiTNode<T> *t=root;
s.push(NULL);
while(t!=NULL)
{
visit(t);
if(t->rchild!=NULL)
s.push(t->rchild);
if(t->lchild!=NULL)
t=t->lchild;
else
{
t=s.top();//获得栈顶元素
s.pop();//清除栈顶元素
}
}
}
void InOrderTraverse(void(*visit)(BiTNode<T>*))const
{//中序(利用栈)遍历二叉树
stack<BiTNode<T>*> s;
BiTNode<T> *t=root;//根节点
while(t!=NULL || !s.empty())
{
if(t)
{//遍历左子树
s.push(t);
t=t->lchild;
}
else
{
t=s.top();
s.pop();//弹出栈顶元素
visit(t);
t=t->rchild;
}
}
cout<<endl;
}
void PostOrderTraverse(void(*visit)(BiTNode<T>*))const
{
StackElem<T> se;
stack<StackElem<T> > s;
BiTNode<T> *t=root;
if(t==NULL)
return;
while(!s.empty() || t!=NULL)
{
while(t!=NULL)
{
se.p=t;
se.flag=Left;
s.push(se);
t=t->lchild;
}
se=s.top();
s.pop();
t=se.p;
if(se.flag==Left)
{
se.flag=Right;
s.push(se);
t=t->rchild;
}
else
{
visit(t);
t=NULL;
}
}
}
void LevelOrderTraverse(void(*visit)(BiTNode<T>*))const
{
queue<BiTNode<T>*> q;
BiTNode<T> *a, *t=root;
if(t!=NULL)
{
q.push(t);
while(!q.empty())
{
a=q.front();
q.pop();
visit(a);
if(a->lchild!=NULL)
q.push(a->lchild);
if(a->rchild!=NULL)
q.push(a->rchild);
}
}
cout<<endl;
}
void OrderTraverse(BiTNode<T>* t,style mode,void(*visit)(BiTNode<T>*))const
{
if(t!=NULL)
{
if(mode==Pre)
visit(t);
OrderTraverse(t->lchild, mode, visit);
if(mode==In)
visit(t);
OrderTraverse(t->rchild, mode, visit);
if(mode==Post)
visit(t);
}
}
BiTNode<T>* Root()
{
return root;
}
bool InsertChild(BiTNode<T>* &p, bool LR, BiTree<T> &c)
{
BiTNode<T> *q=c.Root();
c.root=NULL;
if(p!=NULL)
{
if(!LR)
{
q->rchild=p->lchild;
p->lchild=q;
}
else
{
q->rchild=p->rchild;
p->rchild=q;
}
return true;
}
return false;
}
bool DeleteChild(BiTNode<T>* &p, bool LR)
{
if(p!=NULL)
{
if(!LR)
DestroyBiTree(p->lchild);
else
DestroyBiTree(p->rchild);
return true;
}
else
return false;
}
T Value(BiTNode<T>* p)const
{
return p->data;
}
void Assign(BiTNode<T>* p, T value)const
{
p->data=value;
}
BiTNode<T>* Parent(BiTNode<T>* p)const
{
queue<BiTNode<T>*> q;
BiTNode<T> *a;
if(root!=NULL)
{
q.push(root);
while(!q.empty())
{
a=q.front();
q.pop();
if(a->lchild && a->lchild==p || a->rchild && a->rchild==p)
return a;
else
{
if(a->lchild!=NULL)
q.push(a->lchild);
if(a->rchild!=NULL)
q.push(a->rchild);
}
}
}
return NULL;
}
void Child(BiTNode<T>* p, BiTNode<T>* &left, BiTNode<T>* &right)const
{
left=p->lchild;
right=p->rchild;
}
bool Sibling(BiTNode<T>* p, BiTNode<T>* &sib, bool &LR)const
{
BiTNode<T> *q=Parent(p);
if(q==NULL)
return false;
if(q->lchild==p)
{
sib=q->rchild;
LR=true;
}
else
{
sib=q->lchild;
LR=false;
}
if(sib!=NULL)
return true;
else
return false;
}
};
#endif
#include "stdafx.h"
#ifndef _C_H_
#define _C_H_
#include <iostream>
#include <fstream>//fin
#include <iomanip>//setw()
#include <cmath>
#include <string>
#include <vector>
#include <list>
#include <stack>
#include <queue>
#include <bitset>//STL位集合
#include <algorithm>//STL中的算法
#include <ctime>
#include <cstdarg>//提供宏va_start,va_arg,va_end,用于存取变长参数表
#include <assert.h>//assert宏
using namespace std;//使用命名空间
#endif
#include <iostream>
using namespace std;
//Main4-1.cpp 验证二叉链表结构的二叉树BiTree<T>类的成员函数
#include "C.h"
#include "yhhBiTNode.h"
#include "yhhBiTree.h"
typedef char T;
T Nil='#';
//Func4-1.cpp 数据元素类型为基本类型的I/O操作
void Visit(BiTNode<T> *c)
{
cout<<c->data<<' ';
}
void InputFromFile(ifstream &f, T &c)
{
f>>c;
}
void Input(T &c)
{
cin>>c;
}
void main()
{
BiTree<T> t, c;
BiTNode<T> *p, *q, *r, *s;
T e;
bool f, k;
string LR;
cout<<"树t空否？"<<boolalpha<<t.BiTreeEmpty()<<"。树t的深度=";
cout<<t.BiTreeDepth(t.Root())<<endl;
ifstream fin("F4-1.txt");
t.CreateBiTreeFromFile(fin);
fin.close();
cout<<"由文件F4-1.txt创建二叉树t后，树t空否？"<<boolalpha<<t.BiTreeEmpty();
cout<<"。树t的深度="<<t.BiTreeDepth(t.Root())<<endl;
cout<<"先序递归遍历二叉树t：";
t.OrderTraverse(t.Root(), Pre, Visit);
cout<<endl<<"中序递归遍历二叉树t：";
t.OrderTraverse(t.Root(), In, Visit);
p=t.Root();
cout<<endl<<"t的根结点="<<t.Value(p)<<"。给根结点赋新值，请输入新值：";
Input(e);
t.Assign(p, e);
t.Child(p, q, r);
s=t.Parent(r);
cout<<"树t根结点的右孩子是"<<t.Value(r)<<"，它的双亲是"<<t.Value(s);
f=t.Sibling(r, s, k);
if(f)
{
if(!k)
LR="左";
else
LR="右";
cout<<"，它的"<<LR<<"兄弟是"<<t.Value(s)<<endl;
}
fin.open("F4-2.txt");
c.CreateBiTreeFromFile(fin);
fin.close();
cout<<"创建右子树为空的二叉树c后，中序非递归遍历二叉树c：";
c.InOrderTraverse(Visit);
cout<<"后序递归遍历二叉树c：";
c.OrderTraverse(c.Root(), Post, Visit);
f=t.InsertChild(q, true, c);
if(f)
{
cout<<endl<<"先序非递归遍历插入后的二叉树t：";
t.PreOrderTraverse(Visit);
cout<<endl;
cout<<"中序非递归遍历插入后的二叉树t：";
t.InOrderTraverse(Visit);
cout<<"先序递归遍历插入后的二叉树c：";
c.OrderTraverse(c.Root(), Pre, Visit);
}
f=t.DeleteChild(q, true);
if(f)
{
cout<<endl<<"后序非递归遍历删除后的二叉树t：";
t.PostOrderTraverse(Visit);
cout<<endl<<"中序递归遍历删除后的二叉树t：";
t.OrderTraverse(t.Root(), In, Visit);
cout<<endl<<"层序遍历删除后的二叉树t：";
t.LevelOrderTraverse(Visit);
}
}
F4-1.txt内容：
ABDG###E##C#F##
F4-2.txt内容：
FIJL###K###