c 数据结构,二叉树ds5-binary tree(new)

《c 数据结构,二叉树ds5-binary tree(new)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第五章二叉树主要内容5.1定义与主要特性5.2二叉树的实现5.3遍历二叉树及线索化5.4二叉搜索树5.5AVL树5.6堆5.7霍夫曼编码树25.1定义与特性5.1.1定义和术语5.1.2二叉树的性质35.1.1定义和术语一、树的定义5定义：树(Tree)是n(n>=0)个结点的有限集T，T为空时称为空树，否则它满足如下两个条件：（1）有且仅有一个特定的称为根(Root)的结点；（2）其余的结点可分为m(m>=0)个互不相交的子集T1,T2,T3…Tm，其中每个子集又是一棵树，并称其为子树(Subtree)这是一个递归定义。二、二叉树的

2、定义6定义：二叉树是由n(n>=0)个结点的有限集合构成，此集合或者为空集，或者由一个根结点及两棵互不相交的左右子树组成，并且左右子树都是二叉树。这也是一个递归定义。二叉树可以是空集合，根可以有空的左子树或空的右子树三、相关术语7结点的度树的度叶结点分支结点左孩子、右孩子、双亲路径、路径长度祖先、子孙结点的深度树的高度5.1.2二叉树的性质99一、二叉树的定义和特点1、定义：二叉树是有限个结点的集合，它或者是空，或者是由一个根结点加上两棵分别称为左子树和右子树、互不相交的二叉树组成。2、特点◆每个结点最多只有两个孩子结点，即结点的度不

3、大于2。◆子树有左右之别，子树的次序（位置）不能颠倒。3、基本形态空只有根结点根的右子树为空根的左子树为空根的左右子树都不空1010二、二叉树的性质1、若层次从0开始，则第i层最多有2个结点i2、高度为h的二叉树最多有2-1个结点h第0层（根）第1层第2层第3层11如果二叉树中每一个结点，或者是叶节点，或者是分支节点且恰有两个非空子结点。2453671图满二叉树三、满二叉树1212345612345712367(a)完全二叉树(b)非完全二叉树(c)非完全二叉树图完全二叉树四、完全二叉树一棵高度为d的二叉树除了d-1层以外每一层都是满

4、的，并且每一层都是从左到右填充13定理1：非空满二叉树的叶结点数等于其分支结点数加1四、满二叉树定理定理2：一棵非空二叉树空子树的数目等于其结点数目加114如图5.11所示为完全二叉树上结点及其左右孩子结点之间的关系。[i/2]ii+12i2i+12(i+1)2i+3[i+1/2]i+12(i+1)2i+3i2i2i+1图5.11完全二叉树中结点I和i+1(a)I和i+1结点在同一层(b)I和i+1结点不在同一层5.2二叉树的实现5.2.1二叉树抽象数据类型5.2.2使用指针实现5.2.3使用数组实现15165.2.1二叉树的抽象数据

5、类型二叉树结点的ADTtemplateclassBinNode{public:virtualElem&val()=0;//返回元素的值virtualvoidsetVal(constElem&)=0;;//设置元素的值virtualBinNode*left()=0;;//返回左结点的指针virtualBinNode*right()=0;//返回右结点的指针virtualvoidsetLeft(BinNode*)=0;//设置左结点virtualvoidsetRight(BinNode*)=0;//设置右结点virt

6、ualboolisLeaf()=0;//判断是否为叶结点}16175.2.2使用指针实现结点结构和示例leftChilddatarightChildABCDEFrootA∧B∧C∧D∧E∧∧F∧root18二叉树的二叉链表存储表示templateclassBinaryTree;templateclassBinTreeNode{firendclassBinaryTree;private:Elemdata;//数据域BinTreeNode*lchild;//左子结点指针域BinTre

7、eNode*rchild;//右子结点指针域public:BinTreeNode(){lchild=rchild=NULL;}BinTreeNode(Eleme,BinNodePtr*l=NULL,BinNodePtr*r=NULL){data=e;lchild=l;rchild=r;}~BinTreeNode(){}链式存储的特点动态建立，灵活性高结构性开销大19205.2.3使用数组实现abcdefghijklABCDEFGHIJKL12345678910111221一般二叉树ABCDEFGØØØØØ表示该处没有元素存在仅仅为了好

8、理解ABCDEØØØØFG数组存储的特点对于完全二叉树空间利用率很高从树根起，自上层至下层，每层自左至右的给所有结点编号缺点是有可能对存储空间造成极大的浪费在最坏的情况下，一个深度为H且只有H个结点的右单支树确需要2h-