北京大学：《数据结构与算法》课程教学资源（实验班讲义）第四章 二叉树

主要内容 数据结构与算法 41二叉树的概念 第四章二叉树 42二叉树的主要性质 4.3二叉树的抽象数据类 张铭 44周游二叉树 http:/db.pku.edu.cn/mzhang/ds/ 4.5二又树的实现 北京大学信息科学与技术学院 ■46二叉搜索树 数据结构与算法教学小组 47堆与优先队列 48 Huffman编码树 ⊙版权所有,转數或翻印必究 41二叉树的概念 二叉树的定义 4.1.1二叉树的定义及相关概念 树的特例 ■递归的定义:二叉树由结点的有限集合构成: ■412满二叉树 完全二叉树 或者由一个根结点及两棵不相交的分别称作这个根的左 扩充二叉树 子树和右子树的二叉树(它们也是结点的集合)组成 权有命 北大息带 机新有,成岛 二叉树的五种基本形态 二叉树的相关术语 二叉树可以是空集合,因此根可以有空的左子 纯点 根结点、子结点、父结点、左 树或右子树,或者左右子树皆为空 分支结点、叶结点 路径、路径长度 深度、高度、层数、宽度 叉树的高度定义为二叉树 层教最大的叶点的层数加1 度定义为二叉树中 日)空(b)独(O空右(d)空左()左右都不 大_息单脑

1 数据结构与算法 第四章 二叉树 张铭 http://db.pku.edu.cn/mzhang/DS/ 北京大学信息科学与技术学院 “数据结构与算法”教学小组 ©版权所有，转载或翻印必究 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 2 主要内容 „ 4.1 二叉树的概念 „ 4.2 二叉树的主要性质 „ 4.3 二叉树的抽象数据类型 „ 4.4 周游二叉树 „ 4.5 二叉树的实现 „ 4.6 二叉搜索树 „ 4.7 堆与优先队列 „ 4.8 Huffman编码树 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 3 4.1 二叉树的概念 „ 4.1.1 二叉树的定义及相关概念 „ 4.1.2 满二叉树 完全二叉树 扩充二叉树 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 4 二叉树的定义 „ 树的特例 „ 递归的定义：二叉树由结点的有限集合构成: „ 或者为空集 „ 或者由一个根结点及两棵不相交的分别称作这个根的左 子树和右子树的二叉树(它们也是结点的集合)组成 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 5 二叉树的五种基本形态 (a)空 (b)独根 (c)空右 (d)空左 (e)左右都不空 „ 二叉树可以是空集合，因此根可以有空的左子 树或右子树，或者左右子树皆为空 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 6 二叉树的相关术语 „ 结点 „ 根结点、子结点、父结点、左 子结点、右子结点 „ 分支结点、叶结点 „ 边 „ 路径、路径长度 „ 祖先、后代 „ 深度、高度、层数、宽度 „ 二叉树的高度定义为二叉树中 层数最大的叶结点的层数加1 „ 二叉树的深度定义为二叉树中 层数最大的叶结点的层数 H G E A B C D F I

满二叉树 完全二叉树 ■如果一橾二叉树的任何结点,或者是制叶 最多只有最下面的两层结点度数可以小于2 或者恰有两裸空子树,则此二叉树称作 最下一层的结点都集中最左边 叉树 F G 宜大_息啦张写 扩充二叉树 扩充二叉树 ■所有空子树,都增加空树叶 ■扩充二叉树是满二叉树 新增加的空树叶(外部结点)的个数等于原来二叉树 的结点(内部结点个数加1 路径长度 zom 外部路径长度E从扩充的二叉树的根到每个外部 结点的路径长度之和 内部路径长度I扩充的二叉树里从根到每个内部 结点的路径长度之和 四·E和两个量之间的关系为E=I+2n 42二叉树的主要性质 42二叉树的性质 满二叉树定理;非空满二叉树树叶数等于其分支结 2满二叉树定理推论:一个非空二叉树的空子树(指针) 点数加1 数目等于其结点数加1。 证明:设结点总数为n,叶结点数m,分支结点数b 有n(总结点数=m(叶)+b(分支)(公式4.1) 证明:设二叉树T,将其所有空子树换为树叶,记新的 每个分支,恰有两个子结点(满),故有2+b条边 〓叉树,除根结点外,每个结点都恰有一条边联摸父结 扩充满二叉树为T。所有原来T的结点现在是T的分支结 故共有n1条 点。根据满二叉树定理,新添加的树叶数目等于T结点 由(公式41),(公式42)得n1=m+b-1=2b,得出 个数加1。而每个新添加的树叶对应T的一个空子树。 Hb(分支)+1 区因此T中空子树数目等于T中结点数加1。 真大_血单

2 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 7 满二叉树 „ 如果一棵二叉树的任何结点，或者是树叶， 或者恰有两棵非空子树，则此二叉树称作 满二叉树 A B C D E F G H I 树叶 两棵非空子树 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 8 完全二叉树 A B G C A B C F G D E I J L D E F H K „ 最多只有最下面的两层结点度数可以小于2 „ 最下一层的结点都集中最左边 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 9 扩充二叉树 „ 所有空子树，都增加空树叶 wen wim xul yum wul xal wan zol wil yo zom xem yon zi 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 10 扩充二叉树 „ 扩充二叉树是满二叉树 „ 新增加的空树叶(外部结点)的个数等于原来二叉树 的结点(内部结点)个数加1 „ 路径长度 „ 外部路径长度E 从扩充的二叉树的根到每个外部 结点的路径长度之和 „ 内部路径长度I 扩充的二叉树里从根到每个内部 结点的路径长度之和 „ E和I两个量之间的关系为 E=I+2n 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 11 4.2 二叉树的主要性质 „ 1. 满二叉树定理：非空满二叉树树叶数等于其分支结 点数加1 „ 证明：设结点总数为n，叶结点数m，分支结点数b。 有n（总结点数= m（叶)+b（分支） (公式4.1) „ 每个分支，恰有两个子结点（满），故有2*b条边； „ 一颗二叉树，除根结点外，每个结点都恰有一条边联接父结 点，故共有n-1条边, 即n - 1 = 2b (公式4.2) „ 由(公式4.1)，(公式4.2)得 n-1=m+b-1 = 2b，得出 m(叶) = b（分支）+ 1 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 12 4.2 二叉树的性质 2.满二叉树定理推论：一个非空二叉树的空子树(指针) 数目等于其结点数加1。 证明：设二叉树T，将其所有空子树换为树叶，记新的 扩充满二叉树为T’。所有原来T的结点现在是T’的分支结 点。根据满二叉树定理，新添加的树叶数目等于T结点 个数加1。而每个新添加的树叶对应T的一个空子树。 因此T中空子树数目等于T中结点数加1

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) };

43二叉树的抽象数据类型 43二叉树的抽象数据类型 又树的抽象数据类型的C++定义 BinaryTree,没有 具体规定该抽象数据类型的存储方式 BinaryTree //构造函数 template <class t> bool isEmpty( const 判定二叉树是否为空树 class BinaryTree t /返回二叉树根结点 private eeNode<T>* Root; /返回 current结点的父结点 /二叉树根结点指针 BinaryTreeNode<T>* Parent(Binary TreeNode<T>* Binary TreeNode<T>* root; /返回 current结点的左兄弟 Binary TreeNode<T>*curre 张写 43二叉树的抽象数据类型 43二叉树的抽象数据类型 /返回 current结点的右兄弟 /后序周游二叉树或其子树 BinaryTreeNode<T>* current) void Postorder(BinaryTreeNode<T>* root); /以eem作为根结点, leftTree作为树的左子树 ∥/ rightTree作为树的右子树,构造一橾新的二叉树 /按层次周游二叉树或其子树 void CreateTree(const T& elem, void LevelOrder( BinaryTreeNode<T>k root); BinaryTree<T>& rightTree) /删除二叉树或其子树 //前序周游二叉树或其子树 void Delete BinaryTree(BinaryTreeNode<T>* /中序周游二叉树或其子树 id Inorder(Binary Treenode <t>* root): 张鲁写 前有,聊脂究 44周游二叉树 44周游二叉树 ■周游 ■二叉树周游 ■系统地访问数据结构中的结点 441深度优先周游二叉树 ■每个结点都正好被访问到一次 ■二叉树的结点的线性化 442非递归深度优先周游二叉树 44.3广度优先周游二叉树 真大_血单 大息

4 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 19 4.3 二叉树的抽象数据类型 „ 二叉树的抽象数据类型的C++定义BinaryTree，没有 具体规定该抽象数据类型的存储方式 template <class T> class BinaryTree { private: //二叉树根结点指针 BinaryTreeNode<T>* root; 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 20 4.3 二叉树的抽象数据类型 public: BinaryTree(); //构造函数 ~BinaryTree(); //析构函数 bool isEmpty() const; //判定二叉树是否为空树 //返回二叉树根结点 BinaryTreeNode<T>* Root(); //返回current结点的父结点 BinaryTreeNode<T>* Parent(BinaryTreeNode<T>* current); //返回current结点的左兄弟 BinaryTreeNode<T>* LeftSibling( BinaryTreeNode<T>* current); 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 21 4.3 二叉树的抽象数据类型 //返回current结点的右兄弟 BinaryTreeNode<T>* RightSibling( BinaryTreeNode<T>* current); // 以elem作为根结点，leftTree作为树的左子树, //rightTree作为树的右子树，构造一棵新的二叉树 void CreateTree(const T& elem, BinaryTree<T>& leftTree, BinaryTree<T>& rightTree); //前序周游二叉树或其子树 void PreOrder(BinaryTreeNode<T>* root)； //中序周游二叉树或其子树 void InOrder(BinaryTreeNode<T>* root)； 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 22 4.3 二叉树的抽象数据类型 //后序周游二叉树或其子树 void PostOrder(BinaryTreeNode<T>* root)； //按层次周游二叉树或其子树 void LevelOrder(BinaryTreeNode<T>* root)； //删除二叉树或其子树 void DeleteBinaryTree(BinaryTreeNode<T>* root); }; 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 23 4.4 周游二叉树 „ 周游 „ 系统地访问数据结构中的结点 „ 每个结点都正好被访问到一次 „ 二叉树的结点的线性化 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 24 4.4 周游二叉树 „ 二叉树周游 „ 4.4.1 深度优先周游二叉树 „ 4.4.2 非递归深度优先周游二叉树 „ 4.4.3 广度优先周游二叉树

深度优先周游二叉树 变换根结点的周游顺序,得到三种方案 ①前序周游(tLR次序):访问根结点;前 序周游左子树;前序周游右子树 n①前序周游: ABDCEGFHI 2中序周游(tR次序):中序周游左子 树;访问根结点;中序周游右子树。 n②中序周游: DBAEGCHFI ③后序周游(LR次序):后序周游左子 树;后序周游右子树;访问根结点 n⑧后序周游: DBGEHIFCA 张写 深度优先周游二叉树(递归) 44周游二叉树 lass t> void Binary Tree<T>: DepthOrder(Binary TreeNode<T>* root)( ■二叉树周游 Visit(root) //前序 DepthOrder(root- leftchildo);∥问左子树 44.1深度优先周游二叉树 visit(root); //中序 442非递归深度优先周游二叉树 DepthOrdert(root> rightchildo/访问右子树 Visit(root; //后序 443广度优先周游二叉树 叔有。轨印当究 张鲁写 前有,聊脂究 非递归深度优先周游二叉树 非递归前序周游二叉树—简洁 深度优先二叉树周游是递归定义的 遇到一个结点,就访问该结点,并把此结点的非空右结点 推入梭中,然后下降去周游它的左子树 栈是实现递归的最常用的结构 周游完左子树后,从栈顶托出一个结点,并按照它的右链 接指示的地址再去周游该结点的右子树结构 记下尚待周游的结点或子树 BinaryTree<T>:: PreOrderwithoutRecusion 以备以后访问 (Binary TreeNode<T>k root /非递归前序遍历二叉树或其子树 真大_血单 大息 5

5 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 25 深度优先周游二叉树 变换根结点的周游顺序，得到三种方案： ① 前序周游(tLR次序)：访问根结点；前 序周游左子树；前序周游右子树。 ② 中序周游(LtR次序)：中序周游左子 树；访问根结点；中序周游右子树。 ③ 后序周游(LRt次序)：后序周游左子 树；后序周游右子树；访问根结点。 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 26 „ ① 前序周游：ABDCEGFHI „ ② 中序周游：DBAEGCHFI „ ③ 后序周游：DBGEHIFCA G H E A B C D F I 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 27 深度优先周游二叉树（递归） template<class T> void BinaryTree<T>::DepthOrder (BinaryTreeNode<T>* root) ｛ if(root!=NULL){ DepthOrder(root->leftchild()); //访问左子树 DepthOrder(root->rightchild());//访问右子树 } ｝ Visit(root); //前序 Visit(root); //中序 Visit(root); //后序 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 28 4.4 周游二叉树 „ 二叉树周游 „ 4.4.1 深度优先周游二叉树 „ 4.4.2 非递归深度优先周游二叉树 „ 4.4.3 广度优先周游二叉树 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 29 非递归深度优先周游二叉树 „ 深度优先二叉树周游是递归定义的 „ 栈是实现递归的最常用的结构 „ 记下尚待周游的结点或子树 „ 以备以后访问 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 30 非递归前序周游二叉树——简洁 „ 思想： „ 遇到一个结点，就访问该结点，并把此结点的非空右结点 推入栈中，然后下降去周游它的左子树； „ 周游完左子树后，从栈顶托出一个结点，并按照它的右链 接指示的地址再去周游该结点的右子树结构。 template<class T> void BinaryTree<T>::PreOrderWithoutRecusion (BinaryTreeNode<T>* root) //非递归前序遍历二叉树或其子树