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

主要内容 数据结构与算法 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 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* leftchildo const; //返回当前结点指向右子树 (const BinaryTreeNode& Node) a Binary TreeNode * 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 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* leftchild() const; //返回当前结点指向右子树 BinaryTreeNode* rightchild() const; 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 18 4.3 二叉树的抽象数据类型 //设置当前结点的左子树 void setLeftchild(BinaryTreeNode*) ; //设置当前结点的右子树 void setRightchild(BinaryTreeNode*) ; //设置当前结点的数据域 void setValue(const T& val); //判定当前结点是否为叶结点,若是返回true bool isLeaf() const; //重载赋值操作符 BinaryTreeNode& operator= (const BinaryTreeNode& Node) };

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

4 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 19 4.3 二叉树的抽象数据类型 „ 二叉树的抽象数据类型的C++定义BinaryTree，没有 具体规定该抽象数据类型的存储方式 template class BinaryTree { private: //二叉树根结点指针 BinaryTreeNode* root; 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 20 4.3 二叉树的抽象数据类型 public: BinaryTree(); //构造函数 ~BinaryTree(); //析构函数 bool isEmpty() const; //判定二叉树是否为空树 //返回二叉树根结点 BinaryTreeNode* Root(); //返回current结点的父结点 BinaryTreeNode* Parent(BinaryTreeNode* current); //返回current结点的左兄弟 BinaryTreeNode* LeftSibling( BinaryTreeNode* current); 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 21 4.3 二叉树的抽象数据类型 //返回current结点的右兄弟 BinaryTreeNode* RightSibling( BinaryTreeNode* current); // 以elem作为根结点，leftTree作为树的左子树, //rightTree作为树的右子树，构造一棵新的二叉树 void CreateTree(const T& elem, BinaryTree& leftTree, BinaryTree& rightTree); //前序周游二叉树或其子树 void PreOrder(BinaryTreeNode* root)； //中序周游二叉树或其子树 void InOrder(BinaryTreeNode* root)； 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 22 4.3 二叉树的抽象数据类型 //后序周游二叉树或其子树 void PostOrder(BinaryTreeNode* root)； //按层次周游二叉树或其子树 void LevelOrder(BinaryTreeNode* root)； //删除二叉树或其子树 void DeleteBinaryTree(BinaryTreeNode* 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: DepthOrder(Binary TreeNode* root)( ■二叉树周游 Visit(root) //前序 DepthOrder(root- leftchildo);∥问左子树 44.1深度优先周游二叉树 visit(root); //中序 442非递归深度优先周游二叉树 DepthOrdert(root> rightchildo/访问右子树 Visit(root; //后序 443广度优先周游二叉树 叔有。轨印当究 张鲁写 前有,聊脂究 非递归深度优先周游二叉树 非递归前序周游二叉树—简洁 深度优先二叉树周游是递归定义的 遇到一个结点,就访问该结点,并把此结点的非空右结点 推入梭中,然后下降去周游它的左子树 栈是实现递归的最常用的结构 周游完左子树后,从栈顶托出一个结点,并按照它的右链 接指示的地址再去周游该结点的右子树结构 记下尚待周游的结点或子树 BinaryTree:: PreOrderwithoutRecusion 以备以后访问 (Binary TreeNodek 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 void BinaryTree::DepthOrder (BinaryTreeNode* 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 void BinaryTree::PreOrderWithoutRecusion (BinaryTreeNode* root) //非递归前序遍历二叉树或其子树

非递归前序周游二叉树 非递归中序周游二叉树 /使用STL中的 stack ■遇到一个结点 Binary TreeNode* pointer=root; a. push(NULL);//栈底监视哨 hile( pointer)//或者 laStack. empty 把它推入栈中 Visit( pointer> valued);∥/访问当前结点 f( pointer-> rightchildo!=NUL)/右孩子入栈 周游其左子树 a Stack.pu if (pointer->leftchildo I= NULl) 周游完左子树 d(H法左子同冲转向访问右子下 从栈顶托出该结点并访问之 aStack popo;/機顶元纛退栈} |國·按照其右链地址周游该结点的右子树 非递归中序周游二叉树 非递归中序周游二叉树 template void //end if Binary Tree: InOrderwithoutRecusion( Bina ese//左子树访问完毕,转向访问右子树 ryTreeNode* root)t ng std: stack 使用STL中的 stack aStackpopO: /栈顶元素退栈 stack*> aStack; vsit( pointer-> value();//访问当前结点 /当前链接结构指向右孩 Stack. emptyol lpo pointer=pointer->nightchildo: y/end else /vsit( pointer-> value()前序访问点 a Stack push( pointer);//当前结点地址入栈 //当前链接结构指向左孩子 pointer=pointer->leftchildo 张鲁写 前有,聊脂究 非递归后序周游二叉树 非递归后序周游二叉树 遇到一个结点 左子树返回vs右子树返回? 把它推入栈中 周游它的左子树 给栈中元素加上一个特征位 左子树周游结束后 Lef表示已进入该结点的左子树,将从左边回来 按照其右链地址周游该结点的右子树 周游遍右子树后 Right表示已进入该结点的右子树,将从右边回来 从栈顶托出该结点并访问之 真大_血单 大息

6 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 31 { 非递归前序周游二叉树 using std::stack; //使用STL中的stack stack* > aStack; BinaryTreeNode* pointer=root; aStack.push(NULL); // 栈底监视哨 while(pointer){ // 或者!aStack.empty() Visit(pointer->value()); //访问当前结点 if (pointer->rightchild() != NULL) //右孩子入栈 aStack.push(pointer->rightchild()); if (pointer->leftchild() != NULL) pointer = pointer->leftchild(); //左路下降 else { //左子树访问完毕，转向访问右子树 pointer=aStack.top(); aStack.pop(); //栈顶元素退栈 } } } 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 32 非递归中序周游二叉树 „ 遇到一个结点 „ 把它推入栈中 „ 周游其左子树 „ 周游完左子树 „ 从栈顶托出该结点并访问之 „ 按照其右链地址周游该结点的右子树 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 33 非递归中序周游二叉树 „ template void BinaryTree::InOrderWithoutRecusion(Bina ryTreeNode* root) { using std::stack; //使用STL中的stack stack* > aStack; BinaryTreeNode* pointer=root; while(!aStack.empty()||pointer) { if(pointer){ // Visit(pointer->value()); 前序访问点 aStack.push(pointer); //当前结点地址入栈 //当前链接结构指向左孩子 pointer=pointer->leftchild(); 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 34 非递归中序周游二叉树 }//end if else {//左子树访问完毕，转向访问右子树 pointer=aStack.top(); aStack.pop(); //栈顶元素退栈 Visit(pointer->value());//访问当前结点 //当前链接结构指向右孩子 pointer=pointer->rightchild(); }//end else } //end while } 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 35 非递归后序周游二叉树 „ 遇到一个结点 „ 把它推入栈中 „ 周游它的左子树 „ 左子树周游结束后 „ 按照其右链地址周游该结点的右子树 „ 周游遍右子树后 „ 从栈顶托出该结点并访问之 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 36 非递归后序周游二叉树 „ 左子树返回 vs 右子树返回 ? „ 给栈中元素加上一个特征位 „ Left表示已进入该结点的左子树，将从左边回来 „ Right表示已进入该结点的右子树，将从右边回来

非递归后序周游二叉树 非递归后序周游二叉树 栈中的元素类型定义 StackE| ement template enum Tags(Left, Right》//特征标识定义 void Binary Tree:: PostorderWithoutRecusion (BinaryTreeNode* root) class stackElement /栈元囊的定义 /非递归中序遗历二叉树或其子树 using std: stack;//使用STL找部分 叉树结点的链接 StackElement element; eeNode* pointer; stack> a stack;//栈申明 识申明 Tags tag: 四 return;/空树即返回 非递归后序周游二叉树 非递归后序周游二叉树 whle(true)//进入左子树 pointer=element pointer; while(pointer=NULL) lement pointer=pointer //从右子树回来 while(element tag==Right a stack push(element); vsit( pointer> value();//访问当前结点 /沿左子树方向向下周游 pointer=pointer->leftchildo: if(a Stack.empty) /托出栈顶元素 =astack topo element=aStack topO: 叔有。轨印当究 张鲁写 非递归后序周游二叉树 44周游二叉树 a Stackpop(;//弹栈 pointer=element pointer; ■二叉树周游 7/1/end else y/end while //从左子树回来 441深度优先周游二叉树 element tag=Right; 442非递归深度优先周游二叉树 /转向访问右子树 pointer=pointer->rightchildo: 44.3广度优先周游二叉树 y/end while 真大_血单 大息

7 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 37 非递归后序周游二叉树 „ 栈中的元素类型定义StackElement enum Tags{Left,Right}; //特征标识定义 template class StackElement //栈元素的定义 { public: //指向二叉树结点的链接 BinaryTreeNode* pointer; //特征标识申明 Tags tag; }; 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 38 非递归后序周游二叉树 template void BinaryTree::PostOrderWithoutRecusion (BinaryTreeNode* root) //非递归中序遍历二叉树或其子树 { using std::stack;//使用STL栈部分 StackElement element; stack > aStack;//栈申明 BinaryTreeNode* pointer; if(root==NULL) return;//空树即返回 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 39 非递归后序周游二叉树 //else pointer=root; while(true){//进入左子树 while(pointer!=NULL){ element.pointer=pointer; element.tag=Left; aStack.push(element); //沿左子树方向向下周游 pointer=pointer->leftchild(); } //托出栈顶元素 element=aStack.top(); 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 40 非递归后序周游二叉树 aStack.pop(); pointer=element.pointer; //从右子树回来 while(element.tag==Right){ Visit(pointer->value());//访问当前结点 if(aStack.empty()) return; //else{ element=aStack.top(); 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 41 非递归后序周游二叉树 aStack.pop();//弹栈 pointer=element.pointer; // }//end else }//end while //从左子树回来 element.tag=Right; aStack.push(element); //转向访问右子树 pointer=pointer->rightchild(); }//end while } 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 42 4.4 周游二叉树 „ 二叉树周游 „ 4.4.1 深度优先周游二叉树 „ 4.4.2 非递归深度优先周游二叉树 „ 4.4.3 广度优先周游二叉树

广度优先周游二叉树 广度优先周游二叉树 ■从二叉树的第一层(根结点)开始,自上至下逐 template 层遍历;在同一层中,按照从左到右的顺序对结 Void Binary Tree: LevelOrder 点逐一访问。 (Binary TreeNode* root) { /使用ATL的队列 ■例如 queue*> qUeue Binary TreeNode* pointer=root; ABCDEFGH if(pointer) Queue. push(pointer); 四whe( qUeue empty 广度优先周游二叉树 算法代价分析 /取队列首结点 时间 pointer=qUeue. front(; 在各种周游中,每个结点都被访问且只被访问 inter-> value();//访闻当前结点 qUeue popo /左子树进队列 如果计算非递归保存入出栈(或队列)时间 f(pointer->leftchildo) 广度优先,正好每个结点入/出队一次,o(m) Queue. push(pointer->leftchildo) /右子树进队列 前序、中序,某些结点入/出栈一次,不超过o(n) if(pointer->rightchildO) 后序周游,每个结点分别从左、右边各入/出一次, aQueue. push(pointer->rightchildo) 四 end while 驰血端张帖物写 有轨申 张鲁写 前有,聊脂究 回 45二叉树的实现 空间 451用指针实现二叉树 最好o(logn),最坏o(n) 深度优先 452空间开销分析 栈的深度与树的高度有关 453用数组实现完全二叉树 广度优先 ■与树的最大宽度有关 454穿线二叉树 真大_血单 ② 大息

8 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 43 广度优先周游二叉树 „ 从二叉树的第一层（根结点）开始，自上至下逐 层遍历；在同一层中，按照从左到右的顺序对结 点逐一访问。 „ 例如： A B C D E F G H I G H E A B C D F I 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 44 广度优先周游二叉树 template Void BinaryTree::LevelOrder (BinaryTreeNode* root) { using std::queue; //使用ATL的队列 queue*> aQueue; BinaryTreeNode* pointer=root; if(pointer) aQueue.push(pointer); while(!aQueue.empty()) 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 45 广度优先周游二叉树 { //取队列首结点 pointer=aQueue.front(); Visit(pointer->value());//访问当前结点 aQueue.pop(); //左子树进队列 if(pointer->leftchild()) aQueue.push(pointer->leftchild()); //右子树进队列 if(pointer->rightchild()) aQueue.push(pointer->rightchild()); }//end while } 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 46 算法代价分析 时间 „ 在各种周游中，每个结点都被访问且只被访问一 次，时间代价为O(n) „ 如果计算非递归保存入出栈（或队列）时间 „ 广度优先，正好每个结点入/出队一次，O(n) „ 前序、中序，某些结点入/出栈一次，不超过O(n) „ 后序周游，每个结点分别从左、右边各入/出一次， O(n) 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 47 空间 „ 最好O(log n)，最坏O(n) „ 深度优先 „ 栈的深度与树的高度有关 „ 广度优先 „ 与树的最大宽度有关 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 48 4.5 二叉树的实现 „ 4.5.1 用指针实现二叉树 „ 4.5.2 空间开销分析 „ 4.5.3 用数组实现完全二叉树 „ 4.5.4 穿线二叉树

45二叉树的实现 用指针实现二叉树 451用指针实现二叉树 ■非线性结构最自然的方法是链接的方法 452空间开销分析 指针left和 right,分别指向结点的左子女 453用数组实现完全二叉树 和右子女 454穿线二叉树 空指针 张写 用指针实现二叉树 用指针实现二叉树 其他的链接表示法 z区 例如“三叉链表 增加一个指向父母的指针 parent 具有“向上”访问的能力 h I 叔有。轨印当究 张鲁写 前有,聊脂究 用指针实现二叉树 用指针实现二叉树 扩展二叉树结点抽象数据类型 BinaryTreeNode,.为每 个元素结点添加left和rght左右子结点结构 //以后序周游的方式删除二叉树或其子树 if(root /二叉树结点指向左子树的指针 DeleteBinaryTree(root->left)}//递归删除左子树 Delete Binary Tree(root-> right);//递归删除右子树 /二叉树结点指向左子树的指针 Delete root/删除根结点 d inaryTreeNode <Tss right, 真大_血单 大息

9 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 49 4.5 二叉树的实现 „ 4.5.1 用指针实现二叉树 „ 4.5.2 空间开销分析 „ 4.5.3 用数组实现完全二叉树 „ 4.5.4 穿线二叉树 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 50 用指针实现二叉树 „ 非线性结构最自然的方法是链接的方法 „ 指针left和right，分别指向结点的左子女 和右子女 „ 空指针 left info right 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 51 用指针实现二叉树 A B C E F D G H I A B ∧ C ∧ D ∧ ∧ E F ∧ G ∧ ∧ H ∧ ∧ I ∧ t 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 52 用指针实现二叉树 „ 其他的链接表示法 „ 例如“三叉链表” „ 增加一个指向父母的指针parent „ 具有“向上”访问的能力 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 53 用指针实现二叉树 „ 扩展二叉树结点抽象数据类型BinaryTreeNode,为每 个元素结点添加left和right左右子结点结构 private: //二叉树结点指向左子树的指针 BinaryTreeNode* left; //二叉树结点指向左子树的指针 BinaryTreeNode* right; 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 54 用指针实现二叉树 templatevoid BinaryTree:: DeleteBinaryTree(BinaryTreeNode* root) {//以后序周游的方式删除二叉树或其子树 if(root){ DeleteBinaryTree(root->left);//递归删除左子树 DeleteBinaryTree(root->right);//递归删除右子树 Delete root;//删除根结点 } };

452空间开销分析 空间开销分析 结构性开销 存储密度a(≤1)表示数据结构存储的效率 a(存储密度) 数据本身存储量 辅助空间 整个结构占用的存储总量 保存数据结构的逻辑特性 显然a=1-y 方便运算 紧凑结构vs非紧凑结构 y(结构性开销) 辅助结构存储量 叉链表的存储是非紧凑结构 整个结构占用的存储总 张写 空间开销分析 空间开销分析入 根据满二叉树定理:一半的指针是空的 去掉满二叉树叶结点中的指针 ■每个结点存两个指针、一个数据域 (2p)n/2p ■总空间(2p+an 则结构性开销为12(假设p=d) 结构性开销:2pn 如果只在叶结点存数据,dn2 如果p=d,则 在分支结点存储指针,2pn/2=pn 2p(2p+a=2/3 注意:区分叶结点和分支结点又需要额外的算法时间 叔有。轨印当究 张鲁写 前有,聊脂究 回 空间开销分析 453用数组实现完全二叉树 d+可以用两种方法来实现不同的分支结点与叶结点 用 union联合类型定义 顺序方法存储二叉树 使用C+十的子类来分别实现分支结点与叶结点,并采用虚 把所有结点按照一定的次序顺方存储到一片连续的存储单 函数 isLe来区别分支结点与叶结点 早期节省内存资源 使结点在序列中的相互位量反映出二叉树结构的部分信息 利用结点指针的一个空阳位(一个bit)来存蜻点所属的类型 利用指向叶结点的指或者叶结点中的指针域来存储该叶结点的值 ■在存储结构上是线性的,但在逻辑结构上它仍然是 目前,计算机内存资源并不紧张的时候,一般不提倡这种单 纯追求效率,而丧失可读性的做法 二叉树型结构 真大_血单 大息 10

10 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 55 4.5.2 空间开销分析 „ 结构性开销γ „ 辅助空间 „ 保存数据结构的逻辑特性 „ 方便运算 γ = 辅助结构存储量 （结构性开销） 整个结构占用的存储总量 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 56 空间开销分析 „ 存储密度α (≤1)表示数据结构存储的效率 „ 显然α = 1 - γ „ 紧凑结构 vs 非紧凑结构 „ 二叉链表的存储是非紧凑结构 α = 数据本身存储量 （存储密度） 整个结构占用的存储总量 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 57 空间开销分析 根据满二叉树定理：一半的指针是空的 „ 每个结点存两个指针、一个数据域 „ 总空间 (2p + d)n „ 结构性开销：2pn „ 如果 p = d, 则 2p/(2p + d) = 2/3 G H E A B C D F I 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 58 空间开销分析 „ 去掉满二叉树叶结点中的指针 (2p) n/2 p (2p) n/2+ dn p + d 则结构性开销为 1/2 （假设p = d） „ 如果只在叶结点存数据, d n/2 在分支结点存储指针，2p n/2 = p n 则结构性开销为 „ pn / (pn + dn / 2) ⇒ 2/3 （假设p = d） „ 注意：区分叶结点和分支结点又需要额外的算法时间 = A B C D E F G H I 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 59 空间开销分析 „ C+可以用两种方法来实现不同的分支结点与叶结点： „ 用union联合类型定义 „ 使用C++的子类来分别实现分支结点与叶结点，并采用虚 函数isLeaf来区别分支结点与叶结点 „ 早期节省内存资源 „ 利用结点指针的一个空闲位（一个bit）来存储结点所属的类型 „ 利用指向叶结点的指针或者叶结点中的指针域来存储该叶结点的值 „ 目前，计算机内存资源并不紧张的时候，一般不提倡这种单 纯追求效率，而丧失可读性的做法 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 60 4.5.3 用数组实现完全二叉树 „ 顺序方法存储二叉树 „ 把所有结点按照一定的次序顺序存储到一片连续的存储单 元 „ 使结点在序列中的相互位置反映出二叉树结构的部分信息 „ 在存储结构上是线性的，但在逻辑结构上它仍然是 二叉树型结构