数据结构二叉树

数据结构第二次讨论课内容一二叉树的存储与基本运算二叉树的存储表示完全二叉树的顺序表示

012345678901234567891

可以按层次顺序，存储在一片连续的存储单元中。2已知一个结点的位置，可以计算出它左右孩子及双亲的位置。3从下表为0的位置开始存放。1371531极端情形:只有右单支的二叉树1371531一般二叉树不宜采用顺序结构，若采用此结构，将无法确定一颗普通二叉树的树形结构。二叉树的链接表示二叉链表每个结点有三个数据成员Lchild和rchild分为别指向左右孩子的指针，element为元素域leftChilddatarightChilddataleftChildrightChild一个n结点的二叉树中，有n-1个指针域非空，n+1个空指针域二叉树的类定义template<classT>structBinTreeNode{ //二叉树结点类定义

Tdata; //数据域

BinTreeNode<T>*leftChild,*rightChild;

//左子女、右子女链域

BinTreeNode()//构造函数

{leftChild=NULL;rightChild=NULL;}

BinTreeNode(Tx,BinTreeNode<T>*l=NULL,

BinTreeNode<T>*r=NULL){data=x;leftChild=l;rightChild=r;}};二叉树的基本运算函数maketree

建立一个新结点，有三个参数元素e二叉树对象left和rightvoidmaketree(constT&x,BinaryTree<T>&left,BinaryTree<T>&right);函数breaktree

拆分一颗二叉树成三部分后，执行语句”deleteroot;root=NULL;”原二叉树成为空二叉树，并将二叉树的根结点收回。

voidbreaktree(T&x,BinaryTree<T>&left,BinaryTree<T>&right);函数clear

释放二叉表中的所有结点。

voidClear();遍历算法1先序遍历(VLR)voidPreorder(void(*Visit)(T&x));2中序遍历(LVR)voidInorder(void(*Visit)(T&x));3后序遍历(LRV)voidPostorder(void(*Visit)(T&x));V:访问跟结点

L：遍历左子树

R：遍历右子树Visit函数访问元素函数Template<ClassT>VoidVisit(T&x){Cout<<x<<““;}9二叉树递归的中序遍历算法template<classT>voidBinaryTree<T>::InOrder(BinTreeNode<T>*subTree,void(*visit)(BinTreeNode<T>*t)){if(subTree!=NULL){

InOrder(subTree->leftChild,visit);

//遍历左子树

visit(subTree); //访问根结点

InOrder(subTree->rightChild,visit);

//遍历右子树

}};

public：

void

inOrder(void(*visit)(BinTreeNode<T>*t))

{inOrder(root,visit);

}//中序遍历

霍夫曼树：1.基本概念霍夫曼树又称最优二叉树，是一种带权路径长度最短的二叉树。所谓树的带权路径长度，就是树中所有的叶结点的权值乘上其到根结点的路径长度（若根结点为0层，叶结点到根结点的路径长度为叶结点的数）。树的带权路径长度：设一棵二叉树有

n

个叶子结点，每个叶子结点拥有一个权值Ｗ

1

，Ｗ

2

，

......

Ｗ

n

，从根结点到每个叶子结点的路径长度分别为

L1

，

L2......Ln

，那么树的带权路径长度为从树根到每一结点的路径长度之和，记为WPL=(W1*L1+W2*L2+W3*L3+...+Wn*Ln)。1.初始化：根据给定的n个权值{w1,w2,…wn}构成n棵二叉树的集合F={T1,T2,..,Tn}，其中每棵二叉树Ti中只有一个带权wi的根结点，左右子树均空。2.找最小树：在F中选择两棵根结点权值最小的树作为左右子树构造一棵新的二叉树，且至新的二叉树的根结点的权值为其左右子树上根结点的权值之和。3.删除与加入：在F中删除这两棵树，并将新的二叉树加入F中。4.判断：重复前两步（2和3），直到F中只含有一棵树为止。该树即为霍夫曼树。霍夫曼树的基本算法霍夫曼树实现无损压缩编码无损数据压缩是指使用压缩后的数据进行重构，重构后的数据与原来的数据完全相同；无损压缩用于要求重构的信号与原始信号完全一致的场合。也就是说数据经过压缩后信息不受损失，还能完全恢复到压缩前的原样。霍夫曼编码实现数据压缩过程思路：出现概率高的字符使用较短的编码，反之出现概率低的则使用较长的编码，这便使编码之后的字符串的平均期望长度降低，从而达到无损压缩数据的目的。

其实现过程如下：1）字母A,B,C,D,E已被编码，相应的出现概率如下：p（A）=0.16，p（B）=0.51，p（C）=0.09，p（D）=0.13,p（E）=0.112）C和E概率最小，被排在第一棵二叉树中作为树叶。他们的根节点CE的组合概率为0.20。从CE到C的一边被标记为1，从CE到E的一边被标记为0。这种标记是强制性的，所以，不同的霍夫曼编码可能由相同的数据产生。3）各节点相应的概率如下：p（A）=0.16，p（B）=0.51，p（CE）=0.20，p（D）=0.13D和A两个节点的概率最小，这两个节点作为叶子组合成一颗新的二叉树，根节点AD的组合概率为0.29。由AD到A的一边标记为0，由AD到D的一边标记为1。如果不同的二叉树的根节点有相同的概率，那么具有从根到节点最短的最大路径的二叉树应先生成，这样能保持编码的长度基本稳定。

4).剩下节点的概率如下：

P（AD）=0.29，P（B）=0.51，P（CE）=0.20

AD和ＣＥ两节点的概率最小。它们生成一棵二叉树。其根节点ＡＤＣＥ的组合概率为０.４９.由ＡＤＣＥ到AD一边标记为0，由ADCE到ＣＥ的一边标记为１。

5).剩下两个节点的相应概率如下：

P（ＡＤＣＥ）＝０