- 浏览: 279652 次
- 性别:
- 来自: 济南
文章分类
最新评论
08年9月入学,12年7月毕业,结束了我在软件学院愉快丰富的大学生活。此系列是对四年专业课程学习的回顾,索引参见:http://blog.csdn.net/xiaowei_cqu/article/details/7747205
二叉树
二叉树是每个结点最多有两个子树的有序树。通常子树的根被称作“左子树”(left subtree)和“右子树”(right subtree)。二叉树的每个结点至多只有二棵子树(不存在度大于2的结点),二叉树的子树有左右之分,次序不能颠倒。
二叉树有几点重要的性质:
- 性质1:在二叉树的第 i 层上至多有2i-1 个结点。 (i≥1)
- 性质2:深度为 k 的二叉树上至多含2k-1 个结点(k≥1)。
- 性质3:对任何一棵二叉树,若它含有n0 个叶子结点、n2 个度为 2 的结点,则必存在关系式:n0 = n2+1。
- 性质4:具有 n 个结点的完全二叉树的深度为log2n+1
- 性质5:若对含 n 个结点的完全二叉树从上到下且从左至右进行 1 至 n 的编号,则对完全二叉树中任意一个编号为 i 的结点:
(1) 若 i=1,则该结点是二叉树的根,无双亲,否则,编号为i/2 的结点为其双亲结点;
(2) 若 2i>n,则该结点无左孩子,否则,编号为 2i 的结点为其左孩子结点;
(3) 若 2i+1>n,则该结点无右孩子结点,否则,编号为2i+1 的结点为其右孩子结点。
采用链式存储结构实现二叉树
链式存储二叉树
1.首先我们要构造可以表示二叉树的节点的结构 Binary_node
2.构造类二叉树 Binary_tree,并编写其几个基本的成员函数:
Empty()- 检查树是否为空;clear()- 将树清空;size()- 得到树的大小;leaf_count()- 得到叶子数目;height()- 得到树高;
以及几个重要的成员函数:
Binary_tree(const Binary_tree<Entry>&original); 拷贝构造成员函数 Binary_tree &operator=(const Binary_tree<Entry>&original);重载赋值操作符 ~Binary_tree();析构函数
3.分别编写遍历算法的成员函数
void inorder(void(*visit)(Entry &)); 中序遍历(LVR) void preorder(void(*visit)(Entry &)); 前序遍历(VLR) void postorder(void(*visit)(Entry &)); 后续遍历(LRV)
因为二叉树的性质,三种遍历算法我们都用递归实现,所以分别编写其递归函数
void recursive_inorder(Binary_node<Entry>*sub_root,void (*visit)(Entry &)); void recursive_preorder(Binary_node<Entry>*sub_root,void(*visit)(Entry &)); void recursive_postorder(Binary_node<Entry>*sub_root,void(*visit)(Entry &));
4.作为辅助,我们再编写一个print_tree的函数,用以以括号表示法输出
同样使用递归,编写递归函数void recursive_print(Binary_node<Entry>*sub_root);
几个重要的函数代码如下:
template<class Entry> void Binary_tree<Entry>::inorder(void(*visit)(Entry &)) //Post: The tree has been traversed in inorder sequence //Uses: The function recursive_inorder { recursive_inorder(root,visit); } template<class Entry> void Binary_tree<Entry>::recursive_inorder(Binary_node<Entry>*sub_root,void(*visit)(Entry &)) //Pre: sub_root is either NULL or points to a subtree of the Binary_tree //Post: The subtree has been traversed in inorder sequence //Uses: The function recursive_inorder recursively { if(sub_root!=NULL){ recursive_inorder(sub_root->left,visit); (*visit)(sub_root->data); recursive_inorder(sub_root->right,visit); } } template<class Entry> void Binary_tree<Entry>::preorder(void(*visit)(Entry &)) //Post: The tree has been traversed in preorder sequence //Uses: The function recursive_preorder { recursive_preorder(root,visit); } template<class Entry> void Binary_tree<Entry>::recursive_preorder(Binary_node<Entry>*sub_root,void(*visit)(Entry &)) //Pre: sub_root is either NULL or points to a subtree of the Binary_tree //Post: The subtree has been traversed in preorder sequence //Uses: The function recursive_preorder recursively { if(sub_root!=NULL){ (*visit)(sub_root->data); recursive_preorder(sub_root->left,visit); recursive_preorder(sub_root->right,visit); } } template<class Entry> void Binary_tree<Entry>::postorder(void(*visit)(Entry &)) //Post: The tree has been traversed in postorder sequence //Uses: The function recursive_postorder { recursive_postorder(root,visit); } template<class Entry> void Binary_tree<Entry>::recursive_postorder(Binary_node<Entry>*sub_root,void(*visit)(Entry &)) //Pre: sub_root is either NULL or points to a subtree fo the Binary_tree //Post: The subtree has been traversed in postorder sequence //Uses: The function recursive_postorder recursively { if(sub_root!=NULL){ recursive_postorder(sub_root->left,visit); recursive_postorder(sub_root->right,visit); (*visit)(sub_root->data); } } template<class Entry> void Binary_tree<Entry>::print_tree() { recursive_print(root); cout<<endl; } template<class Entry> void Binary_tree<Entry>::recursive_print(Binary_node<Entry>*sub_root) { if(sub_root!=NULL){ cout<<sub_root->data; cout<<"("; recursive_print(sub_root->left); cout<<","; recursive_print(sub_root->right); cout<<")"; } } //其他函数见源码
程序结果
插入二叉树并实现中序、前序和后序遍历
AVL树
AVL树得名于其发明者G.M.Adelson-Velsky和E.M.Landis。AVL树是一个各结点具有平衡高度的扩展的二叉搜索树。在AVL树中,任一结点的两个子树的高度差最多为1,AVL树的高度不会超过1,AVL树既有二叉搜索树的搜索效率又可以避免二叉搜索树的最坏情况(退化树)出现。
AVL树的表示与二叉搜索树类似,其操作基本相同,但插入和删除方法除外,因为它们必须不断监控结点的左右子树的相对高度,这也正是AVL树的优势所在。
实现AVL树的相关运算
1、首先我们修改结构Binary_node,增加Balance_factor用以表示节点平衡情况
2、从二叉搜索树中派生出AVL树,编写其关键的插入和删除成员函数。
Error_code insert(const Record &new_data); Error_code remove(const Record &old_data);
3、入和删除函数我们都用递归实现
编写递归函数:
Error_code avl_insert(Binary_node<Record>* &sub_root, const Record &new_data,bool &taller); Error_code avl_remove(Binary_node<Record>* &sub_root, const Record &target,bool &shorter);
以及几个重要的调用函数:
左旋右旋函数:
void rotate_left(Binary_node<Record>* &sub_root); void rotate_right(Binary_node<Record>* &sub_root);
两次旋转的左右平衡函数
void right_balance(Binary_node<Record>* &sub_root); void left_balance(Binary_node<Record>* &sub_root);
删除函数还要分别编写删除左树和删除右树的递归函数
Error_code avl_remove_right(Binary_node<Record>&sub_root, const Record &target,bool &shorter); Error_code avl_remove_left(Binary_node<Record>*&sub_root, const Record &target,bool &shorter);
4、个重要的成员函数代码如下:
template<class Record> Error_code AVL_tree<Record>::insert(const Record &new_data) //Post: If the key of new_data is already in the AVL_tree, a code of duplicate_error // is returned. Otherwise, a code of success is returned and the Record // new_data is inserted into the tree in such a way that the properties of an // AVL tree are preserved. { bool taller; return avl_insert(root,new_data,taller); } template<class Record> Error_code AVL_tree<Record>::avl_insert(Binary_node<Record>* &sub_root, const Record &new_data,bool &taller) //Pre: sub_root is either NULL or points to a subtree of the AVL tree //Post: If the key of new_data is already in the subtree, a code of duplicate_error // is returned. Otherwise, a code of success is returned and the Record // new_data is inserted into the subtree in such a way that the properties of // an AVL tree have been preserved. If the subtree is increase in height, the // parameter taller is set to true; otherwise it is set to false //Uses: Methods of struct AVL_node; functions avl_insert recursively, left_balance, and right_balance { Error_code result=success; if(sub_root==NULL){ sub_root=new Binary_node<Record>(new_data); taller=true; } else if(new_data==sub_root->data){ result=duplicate_error; taller=false; } else if(new_data<sub_root->data){//Insert in left subtree result=avl_insert(sub_root->left,new_data,taller); if(taller==true) switch(sub_root->get_balance()){//Change balance factors case left_higher: left_balance(sub_root); taller=false; break; case equal_height: sub_root->set_balance(left_higher); break; case right_higher: sub_root->set_balance(equal_height); taller=false; break; } } else{ //Insert in right subtree result=avl_insert(sub_root->right,new_data,taller); if(taller==true) switch(sub_root->get_balance()){ case left_higher: sub_root->set_balance(equal_height); taller=false; break; case equal_height: sub_root->set_balance(right_higher); break; case right_higher: right_balance(sub_root); taller=false; //Rebalancing always shortens the tree break; } } return result; } template<class Record> void AVL_tree<Record>::right_balance(Binary_node<Record>* &sub_root) //Pre: sub_root points to a subtree of an AVL_tree that is doubly unbalanced // on the right //Post: The AVL properties have been restored to the subtree { Binary_node<Record>* &right_tree=sub_root->right; switch(right_tree->get_balance()){ case right_higher: sub_root->set_balance(equal_height); right_tree->set_balance(equal_height); rotate_left(sub_root); break; case equal_height: cout<<"WARNING: program error detected in right_balance "<<endl; case left_higher: Binary_node<Record>*sub_tree=right_tree->left; switch(sub_tree->get_balance()){ case equal_height: sub_root->set_balance(equal_height); right_tree->set_balance(equal_height); break; case left_higher: sub_root->set_balance(equal_height); right_tree->set_balance(right_higher); case right_higher: sub_root->set_balance(left_higher); right_tree->set_balance(equal_height); break; } sub_tree->set_balance(equal_height); rotate_right(right_tree); rotate_left(sub_root); break; } } template<class Record> void AVL_tree<Record>::left_balance(Binary_node<Record>* &sub_root) { Binary_node<Record>* &left_tree=sub_root->left; switch(left_tree->get_balance()){ case left_higher: sub_root->set_balance(equal_height); left_tree->set_balance(equal_height); rotate_right(sub_root); break; case equal_height: cout<<"WARNING: program error detected in left_balance"<<endl; case right_higher: Binary_node<Record>*sub_tree=left_tree->right; switch(sub_tree->get_balance()){ case equal_height: sub_root->set_balance(equal_height); left_tree->set_balance(equal_height); break; case right_higher: sub_root->set_balance(equal_height); left_tree->set_balance(left_higher); break; case left_higher: sub_root->set_balance(right_higher); left_tree->set_balance(equal_height); break; } sub_tree->set_balance(equal_height); rotate_left(left_tree); rotate_right(sub_root); break; } } template<class Record> void AVL_tree<Record>::rotate_left(Binary_node<Record>* &sub_root) //Pre: sub_root points to a subtree of the AVL_tree. This subtree has // a nonempty right subtree. //Post: sub_root is reset to point to its former right child, and the // former sub_root node is the left child of the new sub_root node { if(sub_root==NULL||sub_root->right==NULL)//impossible cases cout<<"WARNING: program error detected in rotate_left"<<endl; else{ Binary_node<Record>*right_tree=sub_root->right; sub_root->right=right_tree->left; right_tree->left=sub_root; sub_root=right_tree; } } template<class Record> void AVL_tree<Record>::rotate_right(Binary_node<Record>*&sub_root) { if(sub_root==NULL||sub_root->left==NULL) cout<<"WARNING:program error in detected in rotate_right"<<endl; else{ Binary_node<Record>*left_tree=sub_root->left; sub_root->left=left_tree->right; left_tree->right=sub_root; sub_root=left_tree; } } template<class Record> Error_code AVL_tree<Record>::remove(const Record &old_data) { bool shorter; return avl_remove(root,old_data,shorter); } template<class Record> Error_code AVL_tree<Record>::avl_remove(Binary_node<Record>* &sub_root, const Record &target,bool &shorter) { Binary_node<Record>*temp; if(sub_root==NULL)return fail; else if(target<sub_root->data) return avl_remove_left(sub_root,target,shorter); else if(target>sub_root->data) return avl_remove_right(sub_root,target,shorter); else if(sub_root->left==NULL){//Found target: delete current node temp=sub_root; //Move right subtree up to delete node sub_root=sub_root->right; delete temp; shorter=true; } else if(sub_root->right==NULL){ temp=sub_root; //Move left subtree up to delete node sub_root=sub_root->left; delete temp; shorter=true; } else if(sub_root->get_balance()==left_higher){ //Neither subtree is empty; delete from the taller temp=sub_root->left;//Find predecessor of target and delete if from left tree while(temp->right!=NULL)temp=temp->right; sub_root->data=temp->data; avl_remove_left(sub_root,temp->data,shorter); } else{ temp=sub_root->right; while(temp->left!=NULL)temp=temp->left; sub_root->data=temp->data; avl_remove_right(sub_root,temp->data,shorter); } return success; } template<class Record> Error_code AVL_tree<Record>::avl_remove_right(Binary_node<Record> *&sub_root,const Record &target,bool &shorter) { Error_code result=avl_remove(sub_root->right,target,shorter); if(shorter==true)switch(sub_root->get_balance()){ case equal_height: sub_root->set_balance(left_higher); shorter=false; break; case right_higher: sub_root->set_balance(equal_height); break; case left_higher: Binary_node<Record>*temp=sub_root->left; switch(temp->get_balance()){ case equal_height: temp->set_balance(right_higher); rotate_right(sub_root); shorter=false; break; case left_higher: sub_root->set_balance(equal_height); temp->set_balance(equal_height); rotate_right(sub_root); break; case right_higher: Binary_node<Record>*temp_right=temp->right; switch(temp_right->get_balance()){ case equal_height: sub_root->set_balance(equal_height); temp->set_balance(equal_height); break; case left_higher: sub_root->set_balance(right_higher); temp->set_balance(equal_height); break; case right_higher: sub_root->set_balance(equal_height); temp->set_balance(left_higher); break; } temp_right->set_balance(equal_height); rotate_left(sub_root->left); rotate_right(sub_root); break; } } return result; } template<class Record> Error_code AVL_tree<Record>::avl_remove_left(Binary_node<Record> *&sub_root,const Record &target,bool &shorter) { Error_code result=avl_remove(sub_root->left,target,shorter); if(shorter==true) switch(sub_root->get_balance()){ case equal_height: sub_root->set_balance(right_higher); shorter=false; break; case left_higher: sub_root->set_balance(equal_height); break; case right_higher: Binary_node<Record>*temp=sub_root->right; switch(temp->get_balance()){ case equal_height: temp->set_balance(left_higher); rotate_right(sub_root); shorter=false; break; case right_higher: sub_root->set_balance(equal_height); temp->set_balance(equal_height); rotate_left(sub_root); break; case left_higher: Binary_node<Record>*temp_left=temp->left; switch(temp_left->get_balance()){ case equal_height: sub_root->set_balance(equal_height); temp->set_balance(equal_height); break; case right_higher: sub_root->set_balance(left_higher); temp->set_balance(equal_height); break; case left_higher: sub_root->set_balance(equal_height); temp->set_balance(right_higher); break; } temp_left->set_balance(equal_height); rotate_right(sub_root->right); rotate_left(sub_root); break; } } return result; }
实验结果
实现如下功能:1)由{4,9,0,1,8,6,3,5,2,7}建AVL树B,并以括号表示法输出;2)删除B中关键字为8和2的结点,输出结果。
分析总结
采用链式存储结构实现二叉树
- 二叉树在插入的时候通过判断待插入数据与根节点数据的大小,若小于根数据,插入左树,反之插入右树(我们规定不许有重复元素);二叉树的存储结构常用于搜索等。但搜索的效率常依赖于树的结构。而树的结构与元素插入顺序有很大关系,用上述方法插入时若插入的元素是有序的,则得到的树与队列几乎没有区别,也起不到优化搜索的目的。
- 二叉树的遍历算法最为重要的一点是递归,递归使我们不必关心于具体的遍历每个节点的顺序,而只是将其看做三个部分,即左子树,根节点,右子树,具体子树的遍历仍是调用其递归函数。
3.在打印树的时候,我写的并不完美,因为对于叶子节点,理想应该不再打印括号,但我通过判断根节点不为空而调用递归函数,即只要节点有元素就会输出(,),还是表达出了树的意思,但并没有想到怎样达到简洁的效果。
实现AVL树的相关运算
- AVL树每插入,删除一个节点就会判断树的高度并改变相应节点的平衡因素,每当有节点不再满足AVL树的性质,立即通过旋转得到AVL树
- 旋转的函数及其巧妙。而插入和删除元素的函数要考虑的情况非常多,一种情况没有考虑到就可能达不到我们想要的效果,函数的编写需要极大的耐心和对编程语句的熟练掌握。很多地方我是参考书上的,别人的代码我可以理解,但我自己写可能还是会漏掉很多情况。
转载请注明出处:http://blog.csdn.net/xiaowei_cqu/article/details/7888562
发表评论
-
unity基础开发----物体位移和旋转实用代码
2013-11-21 22:46 1268using UnityEngine; using Syst ... -
android 动态时钟 附源码
2013-09-24 12:03 1279自定义View实践 例子代码 自定义动态时钟 ... -
android Dialog 背景问题
2013-08-14 11:22 1203我们在使用自定义的Dialog的时候,喜欢自己 ... -
ScrollView scrollTo 的使用 动画效果
2013-08-05 17:43 4595今天用到了ScrollView scrollTo方法 ... -
Android中View绘制优化之一---- 优化布局层次
2012-09-04 23:00 1065... -
Android中View绘制优化二一---- 使用<include />标签复用布局文件
2012-09-08 13:54 1049... -
Android中View绘制优化之三---- 优化View
2012-09-13 21:00 1081... -
兰林任务管理应用程序雏形版以及概要说明
2012-09-15 21:54 874... -
Android中measure过程、WRAP_CONTENT详解以及xml布局文件解析流程浅析(上)
2012-10-10 18:14 1160... -
Android中measure过程、WRAP_CONTENT详解以及xml布局文件解析流程浅析(下)
2012-10-17 20:05 858... -
Android中文件选择器的实现
2012-11-30 08:59 1164... -
【编译原理】使用Lex将C/C++文件输出为HTML文件
2012-07-20 09:37 106108年9月入学,12年7月毕业,结束了我在软件学院愉快丰富的大 ... -
【编译原理】正则表达式
2012-07-21 21:49 229308年9月入学,12年7月毕业,结束了我在软件学院愉快丰富的大 ... -
【OpenCV】访问Mat图像中每个像素的值
2012-07-22 07:10 1168今天百度搜资料还搜到了自己的。。。《访问图像中每个像素的值 ... -
【编译原理】用Yacc做语法分析
2012-07-23 05:47 176608年9月入学,12年7月毕 ... -
【UML】UML几种图的绘制
2012-07-24 09:49 98408年9月入学,12年7月毕业,结束了我在软件学院愉快丰富的大 ... -
【OpenCV】邻域滤波:方框、高斯、中值、双边滤波
2012-07-26 10:52 1452邻域滤波(卷积) 邻域算子值利用给定像素 ... -
【数据结构】排序算法:希尔、归并、快速、堆排序
2012-07-28 06:15 101908年9月入学,12年7月毕 ... -
【OpenCV】角点检测:Harris角点及Shi-Tomasi角点检测
2012-07-31 13:25 1542角点 特征检测与匹配 ... -
【UML】案例分析:机场运作系统
2012-08-01 17:22 310508年9月入学,12年7月毕 ...
相关推荐
在这个压缩包中,我们可以看到几个关键的主题,包括“有图”、“二叉树”、“AVL树”以及“最短路径”,这些都是数据结构和算法领域的重要概念。 首先,我们来深入理解一下“二叉树”。二叉树是一种特殊的数据结构...
在这个主题中,我们将探讨三种特殊的树类型:排序二叉树、AVL树和哈夫曼树,以及如何使用Java语言来实现它们的基本操作,如增、删、改、查。 首先,排序二叉树(Sorted Binary Tree)是一种特殊的二叉树,其中每个...
java数据结构与算法之平衡二叉树AVL树的设计与实现分析.doc
C语言数据结构之平衡二叉树(AVL树)实现方法示例 本文将详细介绍C语言数据结构之平衡二叉树(AVL树)实现方法,并结合实例形式分析了C语言平衡二叉树的相关定义与使用技巧。 知识点一:AVL树的定义 AVL树是一种...
学习和掌握AVL树的原理和实现,对于理解和应用数据结构有极大的帮助。通过阅读和分析提供的代码,可以加深对AVL树实际操作的理解,这对于软件开发,尤其是需要快速查找和更新数据的场景,是非常有价值的。
二叉树有多种类型,如完全二叉树、满二叉树和平衡二叉树(如AVL树和红黑树)。在C++中,二叉树可以通过结构体或类来实现,每个节点包含一个值、一个指向左子节点的指针和一个指向右子节点的指针。常见的操作包括插入...
本话题主要探讨了C++实现的二叉树、二叉搜索树以及AVL树,这些都是高级数据结构,对于优化算法和提高程序效率至关重要。 二叉树是一种特殊的树结构,每个节点最多只有两个子节点,通常分为左子节点和右子节点。在...
查找操作则是在有序的二叉树中进行线性搜索,AVL树的高度平衡使得查找效率高。 2. **AVL树的旋转操作**:分为四种类型——左旋、右旋、左右旋和右左旋,用于在插入和删除后恢复树的平衡。例如,当一个节点的左子树...
在本主题中,我们将深入探讨“树_数据结构二叉树和树的相关操作_”所涵盖的知识点。 首先,我们要了解什么是树。树是一种非线性的数据结构,它由一组节点(或称为顶点)和连接这些节点的边组成。每个节点可以有零个...
AVL树常用于数据库索引、文件系统、编译器符号表等场景,需要高效查找和保持数据结构平衡的场合。 **总结:** AVL树作为自平衡二叉搜索树的代表,通过平衡因子和旋转操作保证了高度平衡,提高了查找、插入和删除...
*avl树:一种自平衡二叉树,它可以在插入、删除和查找操作中保持平衡。 * 排序二叉树:一种二叉树,它的每个节点的值都小于或等于它的左子树中的所有节点的值。 二叉树的操作: * 插入操作:在二叉树中插入一个新...
平衡有序二叉树,也称为AVL树,是二叉搜索树的一种...总之,AVL树是一种高效的数据结构,适用于需要快速查找、插入和删除操作的场景。通过理解其平衡因子、旋转操作以及插入和删除的逻辑,可以更好地掌握和应用AVL树。
在计算机科学中,AVL树是最先发明的自平衡二叉查找树。在AVL树中任何节点的两个子树的高度最大差别为1,所以它也被称为高度平衡树。增加和删除可能需要通过一次或多次树旋转来重新平衡这个树。AVL树得名于它的发明者...
AVL 树是一种高效的数据结构,可以保持插入、删除和搜索操作的效率。通过了解 AVL 树的定义、结构、平衡因子、旋转操作和插入、删除操作等相关知识点,我们可以更好地应用 AVL 树解决实际问题。
在数据结构的学习中,理解并掌握AVL树的概念、特性以及操作是至关重要的。 平衡二叉树的概念: 平衡二叉树的主要目标是解决普通二叉搜索树可能产生的高度不平衡问题,以提高查找、插入和删除操作的效率。在AVL树中...
实验报告可能会详细解释这些操作的步骤,包括如何构建二叉查找树,如何实现AVL树的旋转算法,以及如何在实际应用中使用这些数据结构。此外,报告可能还会包含实验结果的分析,比如不同操作的运行时间比较,以及不...
本实验的主题是“二叉树”,这是数据结构中一个基础且重要的概念。二叉树是一种非线性的数据结构,由节点(或称为顶点)组成,每个节点最多有两个子节点,通常称为左子节点和右子节点。这个实验旨在帮助学生深入理解...
在实际应用中,二叉树的创建可能还包括插入新节点、平衡调整(如AVL树和红黑树)、遍历(前序、中序、后序)等操作。这些操作都需要对二叉树的性质有深入理解,并能灵活运用指针和引用。 总结起来,二叉树的创建...
6. **平衡二叉树**:如AVL树和红黑树,它们保持一定的平衡性,确保查找效率。在C++中实现这类树需要额外的旋转操作来维护平衡。 7. **树的深度优先搜索(DFS)和广度优先搜索(BFS)**:二叉树的遍历可以看作是DFS...
标题中的“c++数据结构二叉树所有功能的源码”表明这是一个用C++编程语言编写的二叉树实现,包含了二叉树的各种操作。C++是一种强类型、面向对象的编程语言,它的模板机制和STL(标准模板库)使得实现复杂的数据结构...