第六章树和二叉树2数据结构.ppt

二叉树遍历中序遍历二叉树算法的定义：若二叉树为空，则空操作；否则中序遍历左子树(L)；访问根结点(V)；中序遍历右子树(R)。遍历结果a+b*c-d-e/fvoidInOrder(BinTreeNode*T){if(T!=NULL){InOrder(T->leftChild);cout<<T->data;InOrder(T->rightChild);}}前序遍历二叉树算法的定义：若二叉树为空，则空操作；否则访问根结点(V)；前序遍历左子树(L)；前序遍历右子树(R)。遍历结果-+a*b-cd/ef前序遍历二叉树的递归算法voidPreOrder(BinTreeNode*T){if(T!=NULL){cout<<T->data;PreOrder(T->leftChild);PreOrder(T->rightChild);}}后序遍历二叉树算法的定义：若二叉树为空，则空操作；否则后序遍历左子树(L)；后序遍历右子树(R)；访问根结点(V)。遍历结果abcd-*+ef/-后序遍历二叉树的递归算法：voidPostOrder(BinTreeNode*T){if(T!=NULL){PostOrder(T->leftChild);PostOrder(T->rightChild);cout<<T->data;}}二叉树遍历应用intCount(BinTreeNode*T){if(T==NULL)return0;elsereturn1+Count(T->leftChild)+Count(T->rightChild);}intLeaf_Count(BitreeT){//求二叉树中叶子结点的数目if(!T)return0;//空树没有叶子elseif(!T->lchild&&!T->rchild)return1;//叶子结点elsereturnLeaf_Count(T-lchild)+Leaf_Count(T-rchild);//左子树的叶子数加上右子树的叶子数}intHeight(BinTreeNode*T){if(T==NULL)return0;else{intm=Height(T->leftChild);intn=Height(T->rightChild));return(m>n)?m+1:n+1;}}复制二叉树(递归算法)判断二叉树等价(递归算法)线索二叉树(ThreadedBinaryTree)0Lchild域指示结点的左孩子Ltag=1Lchild域指示结点的遍历前驱二叉树以及它的中序线索二叉树在中根遍历的线索树中查找前驱结点在中根遍历的线索树中查找后继结点树的存储结构双亲表示以一组连续空间存储树的结点，同时在结点中附设一个指针，存放双亲结点在链表中的位置。用双亲表示实现的树定义A结点结构typedefcharTreeData;typedefstructnode{TreeDatadata;structnode*firstChild,*nextSibling;}TreeNode;typedefTreeNode*Tree;T1T2T3树的二叉树表示:树的遍历树的后根次序遍历:霍夫曼树(HuffmanTree)1带权路径长度(WeightedPathLength,WPL)二叉树的带权(外部)路径长度是树的各叶结点所带的权值wi与该结点到根的路径长度li的乘积的和。WPL=2*2+WPL=2*1+WPL=7*1+4*2+5*2+4*2+5*3+5*2+2*3+7*2=367*3=464*3=35霍夫曼树(2)重复以下步骤,直到F中仅剩下一棵树为止：①在F中选取两棵根结点的权值最小的扩充二叉树,做为左、右子树构造一棵新的二叉树。置新的二叉树的根结点的权值为其左、右子树上根结点的权值之和。②在F中删去这两棵二叉树。③把新的二叉树加入F。5555constintn=20;//叶结点数constintm=2*n-1;//结点数typedefstruct{floatweight;intparent,leftChild,rightChild;}HTNode;typedefHTNodeHuffmanTree[m];哈夫曼树的应用最佳判定树学生成绩的分布呈正态分布即：中等成绩的学生较多，而较好或较差学生均比较少。设其分布规律如下表：若采用图（a）来进行判断，则80%以上的数据要进行三次或三次以上的比较才能得到结果。而如果我们以各分数段人数的占总人数的比例5、15、40、30、10为权值构造哈夫曼树，可得到如图（b）所示的判定树来进行判断,就可以使大部分数据经过比较少次数的比较得到结果。霍夫曼编码若按各个字符出现的概率不同而给予不等长编码，可望减少总编码长度。各字符出现概率为{2/18,7/18,4/18,5/18},化整为{2,7,4,5}。以它们为各叶结点