42二叉树的性质 42二叉树的性质 3.任何一颗二叉树,皮为0的结点比度为2的结点多一个 4.二又树的第l层(根为第0层,1≥1)最多有2 明:设有n个结点的二叉树的度为0、1、2的结点数 分别为=,m1,n?则 个结点 n;+ 边数为e。因为除根以外,每个结点都有 5.高度为k(深度为k-1。只有一个根结点的二叉 e+1。由于这些边是有度为1和2的的结点射出的 树的高度为1,深度为0)的二叉树至多有2k-1个 因此e=n1+2 结点 2·n2+1 公式44) 因此由公式(1)(2)得 6.有n个结点(n>0)的完全二叉树的高度为 n+n+n=n+2·n 团即吗=n+1 og2(n+1)1(深度为og2(n+1)1-1) 张写 43二叉树的抽象数据类型 43二叉树的抽象数据类型 ■逻辑结构十运算 template <class T> class Binary TreeNode 针对整棵树 /申明二叉树为结点类的友元类,便于访问私有 初始化二叉树 //数据成员 合并两棵二叉树 friend class BinaryTree 围绕结点 T element//二叉树结点数据域 访问某个结点的左子结点、右子结点、父结点 /实现时,可以补充 private的左右 访问结点存储的数据 /子结点定义 叔有。轨印当究 张鲁写 前有,聊脂究 43二叉树的抽象数据类型 43二叉树的抽象数据类型 //设置当前结点的左子树 BinaryTreeNodeo oid setLeftchild BinaryTreeNode*): BinaryTreeNode( const T&ele)//拷贝构造函数 //设置当前结点的右子树 /给定了结点值和左右子树的构造函 Binary TreeNode(const T& el //设量当前结点的数据域 void setvalue(const T& val) //判定当前结点是否为叶结点着是返回true T value( const;//返回当前结点的 /返回当前结点指向左子树 //载赋值操作符 BinaryTreeNode<T>* leftchildo const; //返回当前结点指向右子树 (const BinaryTreeNode<T>& Node) a Binary TreeNode <T>* rightchildo const; 真大_血单 大息3 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 13 4.2 二叉树的性质 3.任何一颗二叉树，度为0的结点比度为2的结点多一个 证明：设有n个结点的二叉树的度为0、1、2的结点数 分别为=n0，n1，n2，则 n = n0 + n1 + n2 (公式4.3) 设边数为e。因为除根以外，每个结点都有一条边进入，故 n = e + 1。由于这些边是有度为1和2的的结点射出的， 因此e = n1+ 2·n2，于是 n = e + 1= n1 + 2·n2 + 1 （公式4.4） 因此由公式（1）（2）得 n0 + n1 + n2 = n1 + 2·n2 + 1 即 n0 = n2 + 1 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 14 4.2 二叉树的性质 „ 4. 二叉树的第i层（根为第0层，i≥1）最多有2i 个结点 „ 5. 高度为k(深度为k-1。只有一个根结点的二叉 树的高度为1，深度为0)的二叉树至多有2k-1个 结点 „ 6. 有n个结点（n>0）的完全二叉树的高度为 ⎡log2 (n+1)⎤ (深度为⎡log2 (n+1)⎤ - 1) 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 15 4.3 二叉树的抽象数据类型 „ 逻辑结构 + 运算： „ 针对整棵树 „ 初始化二叉树 „ 合并两棵二叉树 „ 围绕结点 „ 访问某个结点的左子结点、右子结点、父结点 „ 访问结点存储的数据 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 16 4.3 二叉树的抽象数据类型 template <class T> class BinaryTreeNode { //申明二叉树为结点类的友元类，便于访问私有 //数据成员 friend class BinaryTree; private: T element; //二叉树结点数据域 // 实现时，可以补充private的左右 //子结点定义 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 17 4.3 二叉树的抽象数据类型 public: BinaryTreeNode(); //缺省构造函数 BinaryTreeNode(const T& ele);//拷贝构造函数 //给定了结点值和左右子树的构造函数 BinaryTreeNode(const T& ele, BinaryTreeNode* l, BinaryTreeNode* r); T value() const;//返回当前结点的数据 //返回当前结点指向左子树 BinaryTreeNode<T>* leftchild() const; //返回当前结点指向右子树 BinaryTreeNode<T>* rightchild() const; 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 18 4.3 二叉树的抽象数据类型 //设置当前结点的左子树 void setLeftchild(BinaryTreeNode*) ; //设置当前结点的右子树 void setRightchild(BinaryTreeNode*) ; //设置当前结点的数据域 void setValue(const T& val); //判定当前结点是否为叶结点,若是返回true bool isLeaf() const; //重载赋值操作符 BinaryTreeNode<T>& operator= (const BinaryTreeNode<T>& Node) };