网上有关“二叉检索树的构造”话题很是火热，小编也是针对二叉检索树的构造寻找了一些与之相关的一些信息进行分析，如果能碰巧解决你现在面临的问题，希望能够帮助到您。
1、23为根结点
2、15<23,所以15为23左孩子
3、9<23,9<15,9为15的左孩子
4、17<23,17>15，17为15的右孩子
5、26>23,26为23的右孩子
6、18<23,18>15,18>17,18为17的右孩子
7、24>23,24<26,24为26的左孩子
二叉排序树如下图
23
/ \
15 26
/ \ /
9 17 24
\
18
最优二叉树算法的构造算法
基本概念用五个标志域来存储结点的结构 ?以这种结点结构构成的二叉链表作为二叉树的存储结构叫做线索链表（Threaded Linked Lists） 线索 指向结点前驱和后继的指针 线索二叉树（Threaded Binary Tree） 加上线索的二叉树 线索化 对二叉树以某种次序遍历使其变为线索二叉树的过程 在结构示意图中 指针用实线表示 线索通常用虚线表示 线索二叉树的存储结构 二叉树按中序线索化的算法?线索二叉树上常用运算
查找某结点*p在指定次序下的前趋和后继结点 在中序线索二叉树中 查找指定结点*p的中序后继结点和中序前趋结点 1 若结点*p的左子树（或右子树）非空 则*p的中序前趋（或中序后继）是从*p的左孩子（或右孩子）开始往下查找 由于二叉链表中结点的链域是向下链接的 所以在非线索二叉树中亦同样容易找到*p的中序前趋（或中序后继） 2 若结点*p的左子树（或右子树）为空 则在中序线索二叉树中是通过*p的左线索（或右线索）直接找到*p的中序前趋（或中序后继） 但中序线索一般都是 向上 指向其祖先结点 而二叉链表中没有向上的链接 因此在这种情况下 对于非线索二叉树 仅从*p出发无法找到其中序前趋（或中序后继） 而必须从根结点开始中序遍历 才能找到*p的中序前趋（或中序后继）
在后序线索二叉树中 查找指定结点*p的后序前趋结点 1 若*p的左子树为空 同p >lchild是前趋线索 指示其后序前趋结点 2 若*p的左子树非空 则p >lchild不是前趋线索 当*p的右子树非空时 *p的右孩子必是其后序前趋
在后序线索二叉树中 查找指定结点*p的后序后继结点 1 若*p是根 则*p是该二叉树后序遍历过程中最后一个访问到的结点 2 若*p是其双亲的右孩子 则*p的后序后继结点就是其双亲结点 3 若*p是其双亲的左孩子 但*p无右兄弟时 *p的后序后继结点是其双亲结点 4 若*p是其双亲的左孩子 但*p有右兄弟 则*p的后序后继是其双亲的右子树中第一个后序遍历到的结点 它是该子树中 最左下的叶结点
遍历线索二叉树
lishixinzhi/Article/program/sjjg/201311/23149
从上述算法中可以看出，F实际上是森林，该算法的思想是不断地进行森林F中的二叉树的“合并”，最终得到哈夫曼树。
在构造哈夫曼树时，可以设置一个结构数组HuffNode保存哈夫曼树中各结点的信息，根据二叉树的性质可知，具有n个叶子结点的哈夫曼树共有2n－1个结点，所以数组HuffNode的大小设置为2n－1，数组元素的结构形式如下： weight lchild rchild parent 其中，weight域保存结点的权值，lchild和rchild域分别保存该结点的左、右孩子结点在数组HuffNode中的序号，从而建立起结点之间的关系。为了判定一个结点是否已加入到要建立的哈夫曼树中，可通过parent域的值来确定。初始时parent的值为－1，当结点加入到树中时，该结点parent的值为其双亲结点在数组HuffNode中的序号，就不会是－1了。
构造哈夫曼树时，首先将由n个字符形成的n个叶结点存放到数组HuffNode的前n个分量中，然后根据前面介绍的哈夫曼方法的基本思想，不断将两个小子树合并为一个较大的子树，每次构成的新子树的根结点顺序放到HuffNode数组中的前n个分量的后面。
下面给出哈夫曼树的构造算法。
const maxvalue= 10000; {定义最大权值}
maxleat=30; {定义哈夫曼树中叶子结点个数}
maxnode=maxleaf*2-1;
type HnodeType=record
weight: integer;
parent: integer;
lchild: integer;
rchild: integer;
end;
HuffArr:array[0..maxnode] of HnodeType;
var ……
procedure CreatHaffmanTree(var HuffNode: HuffArr); {哈夫曼树的构造算法}
var i,j,m1,m2,x1,x2,n: integer;
begin
readln(n); {输入叶子结点个数}
for i:=0 to 2*n-1 do {数组HuffNode[ ]初始化}
begin
HuffNode[i].weight=0;
HuffNode[i].parent=-1;
HuffNode[i].lchild=-1;
HuffNode[i].rchild=-1;
end;
for i:=0 to n-1 do read(HuffNode[i].weight); {输入n个叶子结点的权值}
for i:=0 to n-1 do {构造哈夫曼树}
begin
m1:=MAXVALUE; m2:=MAXVALUE;
x1:=0; x2:=0;
for j:=0 to n i-1 do
if (HuffNode[j].weight
begin m2:=m1; x2:=x1;
m1:=HuffNode[j].weight; x1:=j;
end
else if (HuffNode[j].weight
begin m2:=HuffNode[j].weight; x2:=j; end;
{将找出的两棵子树合并为一棵子树}
HuffNode[x1].parent:=n i; HuffNode[x2].parent:=n i;
HuffNode[n i].weight:= HuffNode[x1].weight HuffNode[x2].weight;
HuffNode[n i].lchild:=x1; HuffNode[n i].rchild:=x2;
end;
end;
关于“二叉检索树的构造”这个话题的介绍，今天小编就给大家分享完了，如果对你有所帮助请保持对本站的关注！
本文来自作者[努力啊大安蕾]投稿，不代表九五号立场，如若转载，请注明出处：http://www.9www.net/zlan/202601-1067.html
评论列表（3条）
我是九五号的签约作者“努力啊大安蕾”
本文概览：网上有关“二叉检索树的构造”话题很是火热，小编也是针对二叉检索树的构造寻找了一些与之相关的一些信息进行分析，如果能碰巧解决你现在面临的问题，希望能够帮助到您。1、23为根结点2...
文章不错《二叉检索树的构造》内容很有帮助