网页界面设计分析案例,榆林百度seo,大学生简历制作网站,黔东南建设厅官方网站写在前面#xff1a;
二叉树是数据结构课程中非常重要的内容#xff0c;我们针对二叉树的概念、性质以及类型展开详细介绍。
一、概念
二叉树#xff08;Binary Tree#xff09;是n#xff08;n0#xff09;个结点的有限集合#xff0c;该集合或者空集#xff0…写在前面
二叉树是数据结构课程中非常重要的内容我们针对二叉树的概念、性质以及类型展开详细介绍。
一、概念
二叉树Binary Tree是nn0个结点的有限集合该集合或者空集称为空二叉树或者由一个根节点和两颗互不相交的分别称为根节点的左子树和右子树的二叉树组成。其中 二叉树的最大度为2。
特点 1每个结点最多有两棵子树 2左子树和右子树是有顺序的 3即使树中某结点只有一颗子树也要区分左右 图1 二叉树 例如图1中的E结点虽然只有一个子树但是还是要区分左右图中 I 为右子树。
二、性质 性质1在二叉树的第i层上至多有2^(i-1)个结点(i≥1)。 性质2深度为k的二叉树至多有2^(k)-1个结点(k≥1)。 性质3对任何一颗二叉树T如果其终端结点数为n_0度为2的结点数为n_2则n_0n_21。 性质4具有n个结点的完全二叉树深度为⌊log2n⌋1。 其中满二叉树深度为k且含有2^(k)-1个结点的二叉树。完全二叉树深度为k的有n个结点的二叉树当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。 性质5如果对有一颗n个结点的完全二叉树深度为⌊log2n⌋1的结点按层序编号从第1层到第⌊log2n⌋1层每层从左到右则对任一结点i(1≤i≤n)有 1如果i1则结点i是二叉树的根无双亲如果i1则其双亲PARENT(i)是结点 2如果2in则结点i无左孩子结点i为叶子结点否则其左孩子LCHILD(i)是结点2i 3如果2i1n则结点i无右孩子结点i为叶子结点否则其右孩子RCHILD(i)是结点2i1。 三、类型
1.满二叉树 除了最后一层的节点没有任何子节点外每层上的所有节点都有两个节点的二叉树 图2 满二叉树 2.完全二叉树 一颗二叉树的深度为h除了第h层外其他各层的节点都有两个子节点且第h层的所有节点都集中在最左边 满二叉树一定是完全二叉树但是完全二叉树不一定是满二叉树 图3 完全二叉树 3.二叉搜索树 左子树的所有节点的值均小于它的根节点的值 右子树的所有节点的值均大于它的根节点的值 它的左右子树也分别为二叉搜索树
4.平衡二叉树 平衡二叉树是一颗高度平衡的二叉搜索树左右两个子树的高度差绝对值不超过1且左右两个子树都是平衡二叉树 通过左旋右旋来实现平衡 图4 平衡二叉树 图5 非平衡二叉树 5.红黑树 一种弱平衡的二叉搜索树 1每个结点要么是红的要么是黑的 2根节点是黑的 3如果一个结点是红色的那么它的两个子节点都是黑的 4每个叶节点都是黑的 由于是弱平衡可以看到在相同的节点的情况下AVL树的高度低于红黑树相对于严格要求的AVL树来说它的旋转次数少所哟对于搜索插入和删除操作较多的情况下可以用红黑树。
6.堆 堆是完全二叉树所以一定是平衡二叉树。 分为大顶堆和小顶堆 在大顶堆中父节点的值比每一个子节点的值都要大 在小顶堆中父节点的值比每一个子节点的值都要小
注意堆的根节点中存放的是最大或者最小的元素但是其他节点的排序是未知。例如在一个大顶堆中最大的那一个元素总是位于index 0的位置但是最小的元素则未必是最后一个元素。唯一能保证的是最小的元素是一个叶节点但是不确定是哪一个。
插入、删除、查找的时间复杂度 二叉搜索树最好logn 最坏n 【参考】 平衡二叉搜索树logn 红黑树logn
引用
[1]https://blog.csdn.net/AiTTTTTT/article/details/122923963 [2]http://data.biancheng.net/view/192.html [3]https://blog.csdn.net/peachzy/article/details/116499139
