基本概念定义构造哈夫曼树哈夫曼编码树与二叉树的转换树转换为二叉树二叉树转换为树森林与二叉树的转换森林与二叉树的转换二叉树与森林的转换树的遍历森林的遍历遍历关系层序遍历#include stdio.h #include stdlib.h #define MAXSIZE 100 typedef char TreeType typedef struct TreeNode { TreeType data; struct TreeNode *lchild; struct TreeNode *rchild; }TreeNode; typedef TreeNode* ElemType; //队列中放树的节点 typedef struct { ElemType *data; int front; int rear; }Queue; typedef TreeNode* BiTree; char str[]ABDH#K###E##CFI###G#J##; int idx0; void createTree(BiTree *T) { TreeType ch; chstr[idx]; if(ch#) { *TNULL; } else { *T(BiTree)malloc(sizeof(TreeNode)); (*T)-datach; createTree((*T)-lchild); createTree((*T)-rchild); } } //初始化 Queue* iniQueue() { Queue *q(Queue*)malloc(sizeof(Queue)); q-data(ElemType*)malloc(sizeof((ElemType)* q-front 0; q-rear0; return q; } //判断队列是否为空 int isEmpty(Queue *Q) { if(Q-frontQ-rear) { printf(空的\n); return 1; } else { return 0; } } //入队 int equeue(Queue *Q,ElemTyoe e) { if((Q-rear1)%MAXSIZEQ-front) { printf(满了\n); return 0; } Q-data[Q-rear]e; Q-rear(Q-rear1)%MASIZE; return 1; } //出队 int dequeue(Queue *Q,ElemType *e) { if( Q-frontQ-rear) { printf(空的\n); return 0; } *eQ-data[Q-front]; Q-front(Q-front1)%MAXSIZE; return 1; } //获取队头元素 int getHead(Queue *Q,ElemType *e) { if(Q-frontQ-rear) { printf(空的\n); return 0; } *eQ-data[Q-front]; return 1; } //获取队列元素数量 int queueSize(Queue *Q) { if(!isEmpty(Q)) { return Q-rear-Q-front; } else { return 0; } } int maxDepth(TreeNode* root) { if(rootNULL) //判断是否为空树 { return 0; } int depth0; //记录深度 Queue *qinitQueue(); equeue(q,root); while(!isEmpty(q)) { int countqueueSize(q); while(count0) { TreeNode* curr; dequeue(q,curr); if(curr-lchild!NULL) { equeue(q,curr-lchild); } if(curr-rchild!NULL) { equeue(q,curr-rchild); } count--; } depth; } return depth; } int main() { BiTree T; createTree(T); printf(%d\n,maxdepth(T)); return 0; }