《数据结构C++树与二叉树》由会员分享，可在线阅读，更多相关《数据结构C++树与二叉树（12页珍藏版）》请在金锄头文库上搜索。
1、二叉树定义二叉树 二叉树( binary tree )t 是有限个元素的集合(可以为空)。当二叉树非空时， 其中有一个称为根的元素，余下的元素(如果有的话)被组成2个二叉树，分别称为t的左子树和 右子树。二叉树和树的根本区别是： 二叉树可以为空，但树不能为空。 二叉树中每个元素都恰好有两棵子树(其中一个或两个可能为空)。而树中每个元 素可有若干子树。 在二叉树中每个元素的子树都是有序的，也就是说，可以用左、右子树来区别。而 树的子树间是无序的。像树一样，二叉树也是根节点在顶部。二叉树左 (右)子树中的元素画在根的左(右)下方。在 每个元素和其子节点间有一条边。二叉树的特性特性1包含n (n 0
2、 )个元素的二叉树边数为n1。证明:二叉树中每个元素(除了根节点) 有且只有一个父节点。在子节点与父节点间有且 只有一条边，因此边数为n-1。二叉树的高度(h e i g h t)或深度(d e p t h)是指该二叉树的层数。特性2若二叉树的高度为h, h0,则该二叉树最少有h个元素，最多有2h - 1个元素。 证明:因为每一层最少要有1个元素，因此元素数最少为h。每元素最多有2个子节点，则 第i层节点元素最多为2i - 1个，i 0。h= 0时，元素的总数为0,也就是20 - 1。当h 0 时，元素的总数不会超过三一】.特性3包含n个元素的二叉树的高度最大为n,最小为lo g2 (n+ 1
3、 )。证明:因为每层至少有一个元素，因此高度不会超过n。由特性2,可以得知高度为h的二 叉树最多有2h-1个元素。因为nW2h-1,因此hlo (n+ 1 )。由于h是整数，所以h三 l o g2 (n+ 1 )。当高度为h的二叉树恰好有2h - 1个元素时，称其为满二叉树(full binary tree) 假设从满二叉树中删除k个元素，其编号为2h -i, 1WiWk，所得到的二叉树被称为完全 二叉树( complete binary tree)在完全二叉树中，一个元素与其孩子的编号有非常好的对应关系。其关系在特性4中给 出。特性4设完全二叉树中一元素的序号为i, 1 WiWn。则有以下关
4、系成立：1) 当i = 1时，该元素为二叉树的根。若i 1,则该元素父节点的编号为Li / 2。2) 当2i n时，该元素无左孩子。否则，其左孩子的编号为2i。3) 若2i + 1 n，该元素无右孩子。否则，其右孩子编号为2i + 1。 证明 :通过对 i 进行归纳即可得证。二叉树描述链表描述 二叉树最常用的描述方法是用链表或指针。每个元素都用一个有两个指针域的节点表示， 这两个域为L e f t C h i l d和R i g h t C h i d。除此两个指针域外，每个节点还有一个d a t a域。这种定义为二叉树节点提供了三种构造函数。第一种无参数，初始化时节点的左右孩子域被置为0 (
5、即NU L L )； 第二种有一个参数，可用此参数来初始化数据域，孩子域被置为 0； 第三种有3个参数，可用来初始化节点的 3个域。二叉树的边可用一个从父节点到子节点的指针来描述。指针放在父节点的指针域中。因为 包括n个元素的二叉树恰有n-1条边，因此将有2n-(n-1 ) =n+ 1个指针域没有值，这些域被置为0。/链表二叉树的节点类template class BinaryTreeNodefriend void Visit ( BinaryTreeNode *); friend void InOrder(BinaryTreeNode *);friend void PreOrder(Bina
6、ryTreeNode *); friend void PostOrder(BinaryTreeNode *);friend void LevelOrder(BinaryTreeNode *); / friend int main(void);public :BinaryTreeNode()LeftChild = RightChild = 0;BinaryTreeNode(const T& e)data = e;LeftChild = RightChild = 0;BinaryTreeNode(const T& e, BinaryTreeNode *l,BinaryTreeNode *r)dat
7、a = e;LeftChild = l;RightChild = r;private :T data;BinaryTreeNode *LeftChild, /左子树*RightChild; / 右子树说明：变量（在图中为t）来保存二叉树的根，用该变量的名称来指称根节点或整个二叉树，因 此可以说根节点t或二叉树t。从根节点开始，沿着LeftChild和RightChild指针域逐层进行 搜索，可以访问二叉树t中的所有节点。在二叉树中不设置指向父节点的指针一般不会有什 么问题，因为在二叉树的大部分函数中并不需要此指针。若某些应用需要此指针，可在每 个节点增加一个指针域。二叉树常用操作二叉树的常用操
8、作为： 确定其高度。 确定其元素数目。 复制。 在屏幕或纸上显示二叉树。 确定两棵二叉树是否一样。 删除整棵树。 若为数学表达式树，计算该数学表达式。 若为数学表达式树，给出对应的带括号的表达式。以上所有操作可以通过对二叉树进行遍历来完成。在二叉树的遍历中，每个元素仅被访问 一次。在访问时执行对该元素的所有操作。这些操作包括：把该元素显示在屏幕或纸上；计算以该元素为根的子树所表示的数学表达式的值； 对二叉树中元素的个数加 1； 删除表示该元素的节点等。二叉树遍历有四种遍历二叉树的方法： 前序遍历。 中序遍历。 后序遍历。 逐层遍历。前三种遍历方法在程序1- 2，1- 3，1- 4中给出。假设要
9、遍历的二叉树采用前前面所介绍的链 表的方法来描述，并且 B i n a n y Tr e e N o d e 被定义为类或模板结构。/1-2前序遍历 template void PreOrder(BinaryTreeNode *t)/ 对* t 进行前序遍历if (t) Visit ( t ) ; / 访问根节点PreOrder ( t - LeftChild ) ; / 前序遍历左子树 PreOrder( t - RightChild ) ; / 前序遍历右子树 /1-3中序遍历 template void InOrder(BinaryTreeNode *t) / 对* t 进行中序遍历if
10、 (t)InOrder(t - LeftChild ) ; / 中序遍历左子树Visit( t ) ; / 访问根节点InOrder ( t - RightChild ) ; / 中序遍历右子树 /1-4后序遍历template void PostOrder(BinaryTreeNode *t)/ 对* t 进行后序遍历if (t)PostOrder ( t - LeftChild ) ; / 后序遍历左子树PostOrder ( t - RightChild) ; / 后序遍历右子树 Visit( t ) ; / 访问根节点说明：在前三种方法中，每个节点的左子树在其右子树之前遍历。这三种遍历
11、的区别在于对同一 个节点在不同时刻进行访问。在进行前序遍历时，每个节点是在其左右子树被访问之前进行访 问的；在中序遍历时，首先访问左子树，然后访问子树的根节点，最后访问右子树。在后序遍 历时，当左右子树均访问完之后才访问子树的根节点。在逐层遍历过程中，按从顶层到底层的次序访问树中元素，在同一层中，从左到右进行访 问。由于遍历中所使用的数据结构是一个队列而不是栈，因此写一个按层遍历的递归程序很困 难。程序1 - 用6 来对二叉树进行逐层遍历，它采用了队列数据结构（ LinkedQueue 具体见前面队 列的定义）。队列中的元素指向二叉树节点。/1-6逐层遍历template void Level
12、Order(BinaryTreeNode *t)/ 对* t 逐层遍历LinkedQueue BinaryTreeNode* Q; while (t)Visit(t); / 访问 t/ 将 t 的右孩子放入队列if (t-LeftChild) Q.Add(t-LeftChild);if (t-RightChild) Q.Add(t-RightChild);/ 访问下一个节点tryQ.Delete(t);catch (OutOfBounds)return;说明：在程序中仅当树非空时，才进入w h ile循环。首先访问根节点，然后把其子节点加到队 列中。当队列添加操作失败时，由Ad d引发N o
13、M e m异常，由于没有捕获该异常，因此当异常 发生时L e v e l O r d e r函数将退出。在把t的子节点加入队列后，要从队列中删除t元素。若队列 为空，则由D e l e t e引发O u t O f B o u n d s异常，这由c a t c h语句来处理。因为一个空队列意 味着遍历的结束，所以执行r e t u r n语句。若队列非空，则D e l e t e把所删除的元素返回至变量t。 被删除的元素指向下一个欲访问的节点。抽象数据类型 B i n a r y Tr e e (类)二叉树的抽象数据类型描述抽象数据类型B in a ry Tre e实例元素集合；如果不空，则
14、被划分为根节点、左子树和右子树； 每个子树仍是一个二叉树操作C reate( )：创建一个空的二叉树；I s E m p t y：如果二叉树为空，则返回true，否则返回f a l s eRoot (x):取x为根节点；如果操作失败，则返回f a l s e,否则返回t r u eM a k e Tre e (ro o t， l eft，r i g h t)：创建一个二叉树，ro o t作为根节点，l eft作为左子树，r i g h t作 为右子树B re a k Tree (ro o t， l e f t， r i g h t)：拆分二叉树P re O rd e r：前序遍历In O rd e r:中序遍历P o s t O rd e r：后序遍历L e v e l O rd e r :逐层遍历类 B i n a r y Tr e e二叉树抽象数据类型的C + +定义。此定义中采用了链接描述的二叉树，对应的C + +类为B i n a r y Tr e e。函数Vi s it作为遍历函数的参数，以利于不同操作的实现。/二叉树类定义 template class BinaryTreepublic :BinaryTree( )root = 0;BinaryTree( ) ;bool IsEmpty( ) constreurn (root) ?
