二叉树与哈夫曼码

您所在的位置：网站首页 › 二叉树的建立 › 二叉树与哈夫曼码

二叉树与哈夫曼码

#二叉树与哈夫曼码| 来源: 网络整理| 查看: 265

*T是指向根节点的指针，T是指向指针的指针

1，二叉树1.1 建立二叉树

其中lchild，rchild代表左右子节点的地址

（分别为BiTNode和BiTree。BiTNode是指向这个结构体的指针类型，而BiTree则是对BiTNode的另一种指针类型取的别名）

typedef struct BiTNode { TElemType data; struct BiTNode* lchild, * rchild; }BiTNode, * BiTree;

可以理解为两步：创建结构体，起别名。

// 定义 BiTNode 结构体类型 struct BiTNode { int data; struct BiTNode* left; struct BiTNode* right; }; // 为 BiTNode 结构体类型定义别名 BiTree typedef struct BiTNode BiTNode; typedef BiTNode* BiTree;

初始化

Status InitBiTree(BiTree* T) { /* 操作结果: 构造空二叉树T */ *T = NULL;//T是指向根节点指针的指针，根节点指针设置为空 return OK; }1.2递归删除

传入根节点地址，free函数释放内存

void DestroyBiTree(BiTree* T) { /* 初始条件: 二叉树T存在。操作结果: 销毁二叉树T */ if (*T) /* 非空树 */ { if ((*T)->lchild) DestroyBiTree(&(*T)->lchild); if ((*T)->rchild) DestroyBiTree(&(*T)->rchild); free(*T); *T = NULL; } }1.3按先序遍历输入二叉树void CreateBiTree(BiTree* T) { /* 按先序次序输入二叉树中结点的值（可为字符型或整型，在主程中定义）。变量Nil表示空（子）树。 */ TElemType ch; scanf("%c", &ch); if (ch == Nil) /* 空 */ *T = NULL; else { *T = (BiTree)malloc(sizeof(BiTNode));//创建一个节点 if (!*T) exit(OVERFLOW); (*T)->data = ch; /* 根节点赋值 */ CreateBiTree(&(*T)->lchild); /* 构造左子树 */ CreateBiTree(&(*T)->rchild); /* 构造右子树 */ } }1.4查看二叉树的性质

查看是否存在

Status BiTreeEmpty(BiTree T) { /* 初始条件: 二叉树T存在 */ /* 操作结果: 若T为空二叉树,则返回TRUE,否则FALSE */ if (T) return FALSE; else return TRUE; }

查看深度

int BiTreeDepth(BiTree T) { /* 初始条件: 二叉树T存在。操作结果: 返回T的深度 */ int i, j; if (!T) return 0; if (T->lchild) i = BiTreeDepth(T->lchild); else i = 0; if (T->rchild) j = BiTreeDepth(T->rchild); else j = 0; return i > j ? i + 1 : j + 1; }

根节点查询

TElemType Root(BiTree T) { /* 初始条件: 二叉树T存在。操作结果: 返回T的根 */ if (BiTreeEmpty(T)) return Nil; else return T->data; }

节点查询，赋值

TElemType Value(BiTree p) { /* 初始条件: 二叉树T存在，p指向T中某个结点 */ /* 操作结果: 返回p所指结点的值 */ return p->data; } void Assign(BiTree p, TElemType value) { /* 给p所指结点赋值为value */ p->data = value; }1.5遍历

Status(*Visit)(TElemType)：表示在遍历二叉树过程中需要调用的函数，是一个指向函数的指针；该函数的参数为 TElemType 类型（即二叉树节点数据的类型），返回值为 Status 类型（即函数执行的状态）。

先序遍历

void PreOrderTraverse(BiTree T, Status(*Visit)(TElemType)) { /* 初始条件: 二叉树T存在,Visit是对结点操作的应用函数。算法6.1，有改动 */ /* 操作结果: 先序递归遍历T,对每个结点调用函数Visit一次且仅一次 */ if (T) { Visit(T->data); PreOrderTraverse(T->lchild, Visit); // 递归遍历左子树 PreOrderTraverse(T->rchild, Visit); // 递归遍历右子树 } }

中序遍历

void InOrderTraverse(BiTree T, Status(*Visit)(TElemType)) { /* 初始条件: 二叉树T存在,Visit是对结点操作的应用函数 */ /* 操作结果: 中序递归遍历T,对每个结点调用函数Visit一次且仅一次 */ if (T) { InOrderTraverse(T->lchild, Visit); // 递归遍历左子树 Visit(T->data); InOrderTraverse(T->rchild, Visit); // 递归遍历右子树 } }

后序遍历

void PostOrderTraverse(BiTree T, Status(*Visit)(TElemType)) { /* 初始条件: 二叉树T存在,Visit是对结点操作的应用函数 */ /* 操作结果: 后序递归遍历T,对每个结点调用函数Visit一次且仅一次 */ if (T) { PostOrderTraverse(T->lchild, Visit); // 递归遍历左子树 PostOrderTraverse(T->rchild, Visit); // 递归遍历右子树 Visit(T->data); } }visit函数

普通的打印而言

Status visitT(TElemType e) { printf("%c ", e); return OK; }主程序调用

注意，必须按照先序输入的规则输入，空结点必须用" "表示，否则会进入无限循环中即结尾必须包含两个空格

//健壮性有待提高

输入例子：

”ABD E C “ //输入的树： A / \ B C / \ D E

//请输入时将“”删去

int main() { BiTree T; TElemType e1; InitBiTree(&T); e1 = Root(T); printf("请先序输入二叉树:\n"); CreateBiTree(&T); e1 = Root(T); if (e1 != Nil) printf("二叉树的根为: %c\n", e1); else printf("树空，无根\n"); printf("中序递归遍历二叉树:\n"); InOrderTraverse(T, visitT); printf("\n"); printf("后序递归遍历二叉树:\n"); PostOrderTraverse(T, visitT); printf("\n"); return 0; }2，伟大滴哈夫曼编码2.1储存表示

其中HTNode表示一颗哈夫曼树上每个结点的信息，weight表示结点的权值，parent、lchild和rchild分别表示父节点、左子节点和右子节点在数组中的下标；HuffmanTree表示一个指向哈夫曼树的指针；HuffmanCode表示一个指向指针数组的指针，用于存储每个字符对应的Huffman编码。

/* 赫夫曼树和赫夫曼编码的存储表示 */ typedef struct { unsigned int weight; unsigned int parent, lchild, rchild; }HTNode, * HuffmanTree; typedef char** HuffmanCode;

未完待续

//太困了，呼呼喵，

【本文地址】

二叉树与哈夫曼码

二叉树与哈夫曼码

今日新闻

推荐新闻