编程开发中二叉树和霍夫曼树的示例分析-创新互联

小编给大家分享一下编程开发中二叉树和霍夫曼树的示例分析，相信大部分人都还不怎么了解，因此分享这篇文章给大家参考一下，希望大家阅读完这篇文章后大有收获，下面让我们一起去了解一下吧！

创新互联公司主要从事网站建设、成都网站建设、网页设计、企业做网站、公司建网站等业务。立足成都服务贡山,十年网站建设经验,价格优惠、服务专业,欢迎来电咨询建站服务:18980820575

一、二叉树的深层性质

性质1
在二叉树的第 i层最多有 2^(i-1)个结点。 (i≥1)
第一层最多有 2-1=1个结点
第二层最多有 2^(2-1)=2个结点
第三层最多有 2^(3-1)=4个结点
性质2
深度为 k 的二叉树最多有 2^k -1个结点。 (k ≥ 0)
如果有一层，最多有 1=2- 1=1 个结点
如果有两层，最多有 1+2=2^2- 1=3 个结点
如果有三层，最多有 1+2+4=2^3 -1=7个结点
性质3
对任何一棵二叉树，如果其叶结点有 n0个，度为2的非叶结点有n2个，有则有
n0＝n2＋1
性质4
具有n个结点的完全二叉树的高度为[log2 n]+ 1 。（[X]表示不大于 X 的大整数)
性质5
一棵有 n个结点的二叉树（高度为[log2 n]+ 1），按层次对结点进行编号（从上到下，从左到右），对任意结点 i 有：
如果 i = 1 ，则结点 i 是二叉树的根
如果 i > 1 ，则其双亲结点为 [ i/2]
如果 2i <= n ，则结点 i 的左孩子为 2i
如果 2i > n ，则结点 i 无左孩子
如果 2i+1 <= n ，则结点 i 为的右孩子为 2i+1
如果 2i+1 > n , 则结点 i无右孩子
编程开发中二叉树和霍夫曼树的示例分析

二、创建二叉树的方法

指路法定位结点
编程开发中二叉树和霍夫曼树的示例分析

指路法通过根结点与目标结点的相对位置进行定位
指路法可以避开二叉树递归的性质“线性”定位

二叉树存储结构

用结构体来定义二叉树中的指针域
二叉树的头结点也可以用结构体实现

 //结点指针域定义
typedef struct _tag_BTreeNode BTreeNode;
struct _tag_BTreeNode
{
    BTreeNode* left;
    BTreeNode* right;   
};                             

//头结点定义
typedef struct _tag_BTree TBTree;
struct  _tag_BTree
{
    int count;
    BTreeNode* root;
};

定位：利用二进制中的0和1分别表示left和right，位运算是实现指路法的基础
编程开发中二叉树和霍夫曼树的示例分析

三、遍历二叉树

单链表的遍历是指从第一个结点开始（下标为0的结点），按照某种次序依次访问每一个结点。
二叉树的遍历是指从根结点开始，按照某种次序依次访问二叉树中的所有结点。
前序遍历
编程开发中二叉树和霍夫曼树的示例分析
中序遍历

后序遍历

层次遍历

四、线索化二叉树

线索化二叉树指的是将二叉树中的结点进行逻辑意义上的“重排列”，使其可以线性的方式访问每一个结点
二叉树线索化之后每个结点都有一个线性下标，通过这个下标可以快速访问结点，而不需要遍历二叉树
线索化方法1
利用结点中的空指针域，使其指向后继结点
编程开发中二叉树和霍夫曼树的示例分析
算法思想：

线索化方法2
利用线性表保存二叉树的遍历顺序

算法思想：

利用结点空指针线索化的方法会破坏树的结构，线索化二叉树之后不能够再恢复
这两个问题可以在树结点中加入一个线索化指针而得以解决
然而线索化指针的加入又会浪费内存空间，不够灵活
链表线索化方法不会破化树的结构，不需要时线索化时销毁链表即可
链表线索化方法可以很容易的以任何一种遍历顺序对二叉树进行线索化

五、霍夫曼树

编程开发中二叉树和霍夫曼树的示例分析

以上是“编程开发中二叉树和霍夫曼树的示例分析”这篇文章的所有内容，感谢各位的阅读！相信大家都有了一定的了解，希望分享的内容对大家有所帮助，如果还想学习更多知识，欢迎关注创新互联行业资讯频道！

另外有需要云服务器可以了解下创新互联scvps.cn，海内外云服务器15元起步，三天无理由+7*72小时售后在线，公司持有idc许可证，提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案，具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势，专为企业上云打造定制，能够满足用户丰富、多元化的应用场景需求。