树的深度: 树中结点的最大层次。
有序树: 树中结点的各子树从左至右有次序(最左边的为第一个孩子)。
无序树: 树中结点的各子树无次序。
//二叉树顺序存储表示#define MAXTSIZE 100
Typedef TElemType SqBiTree[MAXSTIZE]
SqBiTree bt;
typedef struct BiNode{
TElemType data;
struct BiNode *lchild, *rchild; //左右孩纸
}BiNode,*BiTree;
typedef struct TriTNode{
TelemType data;
struct TriTNode *lchild,*parent,*rchild;
}TriTNode,*TriTree;
Status PreOrderTraverse(BiTree T){
if(T==NULL) return OK; //空二叉树
else{
visit(T); //访问根结点
PreOrderTraverse(T->lchild);//递归遍历左子树
PreOrderTraverse(T->rchild);//递归遍历右子树
}
}
void Pre(BiTree *T) {
if (T!=NULL) {
printf("%d\t",T->data);
pre(T->lchild);
pre(T->rchild);
}
}
Status InOrderTraverse(BiTree T){
if(T==NULL) return OK;//空二叉树
else{
InOrderTraverse(T->lchild);//递归遍历左子树
visit(T);//访问根结点;
InOrderTraverse(T->rchild);//递归遍历右子树}
}
}
Status PostOrderTraverse(BiTree T){
if(T==NULL) return OK;//空二叉树
else{
PostOrderTraverse(T->lchild);//递归遍历左子树
PostOrderTraverse(T->rchild);//递归遍历右子树
visit(T);//访问根结点
}
}
Status InOrderTraverse (BiTree T) {
BiTree p; InitStack(S); p=T;
while(p || !StackEmpty(S)) {
if(p) {
Push(S,p);
p = p->lchild;
}
else {
Pop(S,q);
printf(“%c”，q->data);
p= q->rchild;
}
}
return OK;
}
typedef struct{
BTNode data[MaxSize]; //存放队中元素
int front，rear; //队头和队尾指针
} SqQueue; //顺序循环队列类型
void LevelOrder(BTNode *b) {
BTNode *p; SqQueue *qu;
InitQueue(qu); //初始化队列
enQueue(qu,b); //根结点指针进入队列
while (!QueueEmpty(qu) ) { //队不为空，则循环
deQueue(qu,p); //出队结点p
printf("%c ", p->data); //访问结点p
if (p->lchild!=NULL) enQueue(qu，p->lchild); //有左孩子时将其进队
if (p->rchild!=NULL) enQueue(qu，p->rchild); //有右孩子时将其进队
}
}
建立
Status CreateBiTree(BiTree &T) {
scanf(&ch); //cin> >ch;
if (ch== “#”) T = NULL;
else {
if (!(T =(BiTNode *)malloc(sizeof(BiTNode))))
exit(OVERFLOW); //T=new BiTNode;
T->data = ch; //生成根结点
CreateBiTree(T->lchild);//构造左子树
CreateBiTree(T->rchild);//构造右子树
}
return OK;
}// CreateBiTree
复制二叉树
int Copy(BiTree T，BiTree &NewT){
if(T==NULL){//如果是空树返回0
NewT=NULL;return 0;
}
else {
NewT=new BiTNode;
NewT->data=T->data;
Copy(T->lChild，NewT->lchild);
Copy(T->rChild，NewT->rchild);
}
}
深度
int Depth( BiTree T){
if(T==NULL) return O;//如果是空树返回0
else {
m=Depth(T->lChild);
n =Depth(T->rChild);
if(m>n) return (m+1);
else return(n+1);
}
}
结点总数
int NodeCount(BiTree T){
if(T == NULL)
return O;
else
return NodeCount(T->lchild)+NodeCount(T->rchild)+1;
}
叶子结点总数
int LeadCount(BiTree T){
if(T==NULL) //如果是空树返回0
return O;
if (T->lchild == NULL && T->rchild == NULL)
return 1; //如果是叶子结点返回1
else
return LeafCount(T- >lchild) +LeafCount(T->rchild);
}
typedef struct BiThrNode{
int data;
int Itag, rtag;
struct BiThrNode *Ichild,rchild;
}BiThrNode，*BiThrTree ;
typedef struct PTNode {
TElemType data;
int parent; //双亲位置域
}PTNode;
#define MAX_TREE_SIZE 100
typedef struct {
PTNode nodes[MAX_TREE_SIZE];
int r, n; //根结点的位置和结点个数
}PTree;
typedef struct CTNode {
int child;
struct CTNode *next;
}*ChildPtr;
typedef struct {
TElemType data;
ChildPtr firstchild;//孩子链表头指针
}CTBox;
typedef struct {
CTBox nodes[MAX_TREE_SIZE];
int n, r;//结点数和根结点的位置
}CTree;
typedef struct CSNode{
ElemType data;
struct CSNode *firstchild, *nextsibling;
}CSNode,*CSTree;
typedef struct {
int weight;
int parent, lch, rch;
}HTNode,*HuffmanTree;
void CreatHuffmanTree (HuffmanTree HT, int n){//构造哈夫曼树——哈夫曼算法
if(n<=1) return;
m=2*n-1; //数组共2n-1个元素
HT=new HTNode[m+1]; //0号单元未用，HT[m]表示根结点
for(i=1;i<=m;++i){ //将2n-1个元素的lch、rch、parent置为0
HT[i].Ich=O; HT[i].rch=O; HT[i].parent=O;
}
for(i=1;i<=n;++i) cin>>HT[i].weight;//输入前n个元素的weight值
//初始化结束，下面开始建立哈夫曼树
for( i=n+1;i<=m; i++){ //合并产生n-1个结点-构造Huffman树
Select(HT, i-1,s1, s2); //在HT[k](1≤k≤i-1)中选择两个其双亲域为0,
//且权值最小的结点,并返回它们在HT中的序号s1和s2
HT[s1].parent=i; HT[s2].parent=i; //表示从F中删除s1,s2
HT[i].lch=s1; HT[i].rch=s2 ;
//s1,s2分别作为i的左右孩子
HT[i].weight=HT[s1].weight + HT[s2].weight;//i的权值为左右孩子权值之和
}
}
void CreatHuffmanCode(HuffmanTree HT, HuffmanCode &HC, int n){
//从叶子到根逆向求每个字符的哈夫曼编码，存储在编码表HC中
HC=new char *[n+1]; //分配n个字符编码的头指针矢量
cd=new char [n]; //分配临时存放编码的动态数组空间
cd[n-1]= ‘1O’; //编码结束符
for(i=1; i<=n; ++i){ //逐个字符求哈夫曼编码
start=n-1; c=i; f=HT[i].parent;
while(f!=O){ //从叶子结点开始向上回溯，直到根结点
--start; //回溯一次start向前指一个位置
if (HT[f].Ilchild= =c) cd[start]= '0’ ; //结点c是f的左孩子，则生成代码0
else cd[start]= ‘1’ ; //结点c是f的右孩子，则生成代码1
c=f; f=HT[f].parent; //继续向上回溯
} //求出第i个字符的编码
HC[i]= new char [n-start]; //为第i个字符串编码分配空间
strcpy(HC[i],&cd[start]); //将求得的编码从临时空间cd复制到HC的当前行中
}
delete cd; //释放临时空间
}// CreatHuffanCode
1; i<=n; ++i){ //逐个字符求哈夫曼编码
start=n-1; c=i; f=HT[i].parent;
while(f!=O){ //从叶子结点开始向上回溯，直到根结点
–start; //回溯一次start向前指一个位置
if (HT[f].Ilchild= =c) cd[start]= '0’ ; //结点c是f的左孩子，则生成代码0
else cd[start]= ‘1’ ; //结点c是f的右孩子，则生成代码1
c=f; f=HT[f].parent; //继续向上回溯
} //求出第i个字符的编码
HC[i]= new char [n-start]; //为第i个字符串编码分配空间
strcpy(HC[i],&cd[start]); //将求得的编码从临时空间cd复制到HC的当前行中
}
delete cd; //释放临时空间
}// CreatHuffanCode
## 5.9.5文件的编码和解码
[外链图片转存中...(img-Eb60AhkD-1642168867104)]
[外链图片转存中...(img-ATRnHMgF-1642168867104)]
[外链图片转存中...(img-eWwpUqqr-1642168867105)]
[外链图片转存中...(img-JBLQcu4n-1642168867105)]
[外链图片转存中...(img-Uj4RLzFp-1642168867105)]