精华内容
下载资源
问答
  • 当每个非终端节点均含有m个孩子节点时间,此时整棵树在所有含有n个节点的m叉中是最矮胖的,此时这棵树的高度也是含有n个节点m叉中高度最低。在极限的状态下可以称之为满m叉,因此可以推导不等式,得出最低高度...

    一、最大高度

    试想一下,若有n个节点的度为m的树,当只有最后一层有m个节点,其余层均只有一个节点,在所有含有nn个节点的度为m的树中一定是最高的。
    在这里插入图片描述

    二、最低高度

    当每个非终端节点均含有m个孩子节点时间,此时整棵树在所有含有n个节点的度为m的树中是最矮胖的,此时这棵树的高度也是含有n个节点度为m的树中高度最低。在极限的状态下可以称之为满m叉树,因此可以推导不等式,得出最低高度。
    在这里插入图片描述

    结论:综上分析,对于一个含有n个节点的度为m的树的高度范围为:ceil(logm((m-1)*n + 1) <= h <= n-m+1

    展开全文
  • 二叉树的基本概念    二叉树是每个节点最多有两个子树的树结构。通常子树被称作“左子树”(left subtree)和“右子树”(right subtree)。...   性质4:具有 n 个节点的完全二叉树的深度必为 log2(n+1)  

    二叉树的基本概念

       二叉树是每个节点最多有两个子树的树结构。通常子树被称作“左子树”(left subtree)和“右子树”(right subtree)。

    二叉树的性质(特性)

       性质1:在二叉树的第i层上至多有 2(i-1)个节点(i>0);
       性质2:深度为 k 的二叉树至多有 2k-1 个节点;
       性质3:对于任意一棵二叉树,如果其叶节点数为 N0,而度数为 2 的结点总数为N2,则N0=N2+1
       性质4:具有 n 个节点的完全二叉树的深度必为 log2(n+1)
       性质5:对完全二叉树,若从上至下,从左至右编号,则编号为 i 的结点,其左孩子编号必为 2i, 其右孩子编号必为 2i+1;其双亲的编号必为 i/2i=1 时为根,除外)

    (1)完全二叉树——若设二叉树的高度为 h,除第 h 层外,其他各层(1~h-1)的节点数都达到最大个数,第 h 层有叶子节点,并且叶子节点都是从左到右依次排布,这就是完全二叉树。
    在这里插入图片描述在这里插入图片描述(2)满二叉树——除了叶节点外每一个节点都有左右子叶且叶子节点都处在最底层的二叉树。
    在这里插入图片描述

    二叉树的节点及树的创建

    【示例】通过使用Node类中定义三个属性,分别为elem本身的值,还有lchild左孩子和rchild右孩子

    #定义节点类
    class Node(object):
    	#初始化方法
    	def __init__(self, elem=-1, lchild=None, rchild=None):
    	self.elem = elem
    	self.lchild = lchild
    	self.rchild = rchild
    

    【示例】树的创建,创建一个树的类,并给一个root根节点,一开始为空,随后添加节点

    #创建树的类
    class Tree(object):
    	#初始化方法
    	def __init__(self, root=None):
    		self.root = root
    	#为树添加节点
    	def add(self, elem):
    		node = Node(elem)
    		#如果树是空的,则对根节点赋值
    		if self.root == None:
    			self.root = node
    		else:
    			queue = []
    			queue.append(self.root)
    			#对已有节点进行层次遍历
    			while queue:
    				#弹出队列的第一个元素
    				cur = queue.pop(0)
    				if cur.lchild == None:
    					cur.lchild = node
    					return
    				elif cur.rchild == None:
    					cur.rchild = node
    					return
    				else:
    					#如果左右子树都不为空,加入队列继续判断
    					queue.append(cur.lchild)
    					queue.append(cur.rchild)
    
    展开全文
  • 首先我们可以知道对于一个完全二叉树来说,具有n个节点的完全二叉树的深度是(log以2为底n)+1,所有我们可以先得到这二叉树的深度,即一共有多少层。然后判断这二叉树的右子是否也到达了这个深度,如果到了,...

    要求:时间复杂度低于O(N),N为这棵树的节点个数
    思想:如果采用遍历的话,那么复杂度就刚好是O(n)。不符合要求;
    首先我们可以知道对于一个完全二叉树来说,具有n个节点的完全二叉树的深度是(log以2为底n)+1,所有我们可以先得到这棵二叉树的深度,即一共有多少层。然后判断这棵二叉树的右子树是否也到达了这个深度,如果到了,那么这棵二叉树的左子树一定是一棵满二叉树。再依次使用递归判断右子树。如果右子树没有到达那个深度,那么右子树一定是一棵满二叉树,便可以得到右子树的节点数是多少,再通过递归依次判断右子树。一棵满二叉树的结点个数是2的K次方-1。

    代码:

    public class Count{
    
    	public static class Node {
    		public int value;
    		public Node left;
    		public Node right;
    
    		public Node(int data) {
    			this.value = data;
    		}
    	}
    
    	public static int nodeNum(Node head) {
    		if (head == null) {
    			return 0;
    		}
    		return bs(head, 1, mostLeftLevel(head, 1));
    	}
    
    	public static int bs(Node node, int level, int h) {
    		if (level == h) {
    			return 1;
    		}
    		if (mostLeftLevel(node.right, level + 1) == h) { //如果右子树到达了二叉树的底部,那么左子树的节点数就可以算出来
    			return (1 << (h - l)) + bs(node.right, level + 1, h); //1 << (h - l))的意思是2的h-1次方
    		} else { //如果右子树没有到,那么右子树一定是一个满二叉树,可以算出来右子树的节点数*
    			return (1 << (h - l - 1)) + bs(node.left, level + 1, h);
    		}
    	}
    
    	public static int mostLeftLevel(Node node, int level) { //得到这棵数的深度
    		while (node != null) {
    			level++;
    			node = node.left;
    		}
    		return level - 1;
    	}
    
    	public static void main(String[] args) {
    		Node head = new Node(1);
    		head.left = new Node(2);
    		head.right = new Node(3);
    		head.left.left = new Node(4);
    		head.left.right = new Node(5);
    		head.right.left = new Node(6);
    		System.out.println(nodeNum(head));
    
    	}
    
    }
    

    这个算法的复杂度是O(log以2为底n)的平方。

    展开全文
  • 什么是二叉树:每个节点最多有两个子树的树结构,通常子树被称作“左子树”(left subtree)和“右子树”(right subtree)。二叉树具备以下数学性质:在二叉树的第i层上至多有2^(i-1)个结点(i>0)深度为k的...

    什么是二叉树:每个节点最多有两个子树的树结构,通常子树被称作“左子树”(left subtree)和“右子树”(right subtree)。

    二叉树具备以下数学性质:

    • 在二叉树的第i层上至多有2^(i-1)个结点(i>0)
    • 深度为k的二叉树至多有2^k - 1个结点(k>0)
    • 对于任意一棵二叉树,如果其叶结点数为N0,而度数为2的结点总数为N2,则N0=N2+1;
    • 具有n个结点的完全二叉树的深度必为 log2(n+1)
    • 对完全二叉树,若从上至下、从左至右编号,则编号为i 的结点,其左孩子编号必为2i,其右孩子编号必为2i+1;其双亲的编号必为i/2(i=1 时为根,除外)

    两个子概念:

    满二叉树:除最后一层无任何子节点外,每一层上的所有结点都有两个子结点二叉树

    a6ca7dc474b0d4ca1a03f2b67893eb39.png

    完全二叉树:设二叉树的深度为h,除第 h 层外,其它各层 (1~h-1) 的结点数都达到最大个数,第 h 层所有的结点都连续集中在最左边,这就是完全二叉树。

    a6ca7dc474b0d4ca1a03f2b67893eb39.png

    二叉树的实现

    二叉树由两个对象组成,一个是节点对象,一个是树对象

    class Node:
        """节点类"""
        def __init__(self, elem, lchild=None, rchild=None):
            self.elem = elem
            self.lchild = lchild
            self.rchild = rchild
    
    
    class Tree:
        """树类"""
        def __init__(self, root=None):
            self.root = root
    

    接下来给这树添加基本方法:增加节点

    class Node:
        """节点类"""
        def __init__(self, elem, lchild=None, rchild=None):
            self.elem = elem
            self.lchild = lchild
            self.rchild = rchild
    
    
    class Tree:
        """树类"""
        def __init__(self, root=None):
            self._root = root
    
        def add(self, item):
            node = Node(item)
            if not self._root:
                self._root = node
                return
            queue = [self._root]
            while queue:
                cur = queue.pop(0)
                if not cur.lchild:
                    cur.lchild = node
                    return
                elif not cur.rchild:
                    cur.rchild = node
                    return
                else:
                    queue.append(cur.rchild)
                    queue.append(cur.lchild)
    

    对二叉树节点的操作是通过列表存储节点的形式来操作,但是二叉树数据本身是通过链表的形式来存储,节点的操作一般使用递归函数。

    二叉树的遍历又分为深度遍历和广度遍历,深度遍历还要分中序遍历/先序遍历/后序遍历,将在下一篇来给二叉树增加遍历方法。

    63bb10667f74b7a61c022f51437679d2.png
    展开全文
  • #1694 : 删除树节点

    2018-03-18 17:23:13
    时间限制:10000ms单点时限:1000ms内存限制:256MB描述给定一棵包含N个节点的有根树,编号1~N,其中第i号节点具有权值Wi。 现在小Hi要删除中除了根以外的所有权值小于K的节点。 对于一个节点U,如果它被删除,则它的...
  • 树的重心也叫树的质心,对于一棵具有 n 结点的无根树,找到一点,使得将树变为以该点为根的有根树时,最大子树的结点数最小。 简单来说,就是给定一棵 n 的树,当删除某点 x 后,使得最大连通块最小,此时...
  • 二叉查找 简介 二叉查找也称为有序二叉查找,满足二叉查找的一般性质,是指一棵树具有如下性质: ...一个二叉查找是由n个节点随机构成,所以,对于某些情况,二叉查找会退化成一个有n个节点的线性链.如...
  • 树的基本概念

    2018-03-22 10:34:34
    从递归定义中,我们发现,一棵树是由N个节点和N-1条边集合。 树叶 没有儿子节点成为树叶。 兄弟 具有相同父亲节点成为兄弟,类似方法可以定义祖父和孙子。 路径 从节点n1n1n_1到nknkn_k路径...
  • 一、二叉查找 1、简介 二叉查找也称为有序二叉查找,满足二叉查找树的一般性质,是指一棵树具有如下性质: ...一个二叉查找是由n个节点随机构成,所以,对于某些情况,二叉查找会退化成一个有n个...
  • 给定一棵包含N个节点的无根,节点编号1~N。其中每个节点都具有一个权值,第i个节点的权值是Ai。 小Hi希望你能找到上的一条最长路径,满足沿着路径经过的节点的权值序列恰好构成等差数列。 Input 第一行包含...
  • 前言当我们发现SQL执行很慢时候,自然而然想到就是加索引。对于范围查询,索引底层结构就是B+。今天我们一起来学习一下B+...它由有限个节点,组成具有层次关系集合。因为它看起来像一棵树,所以得其名。...
  • 二叉查找树对于大多数情况下的查找和插入在效率上来说是没有问题的,但是他在最差的情况下效率...在一棵具有N 个节点的树中,我们希望该树的高度能够维持在lgN左右,这样我们就能保证只需要lgN次比较操作就可以查找到想
  • 二叉排序题目

    千次阅读 2017-09-16 00:28:47
    解题思路:因为题目给出的参数是有序数组,可以把该数组朝着构建完全二叉树的角度去思考,根据二叉树的性质:具有n个节点的完全二叉树的深度为log2n(“log2n”代表着以2为底,指数为n的对数值),so,句代码搞定,...
  • 关于或二叉树一些定理和结论

    千次阅读 2015-10-19 12:05:47
    1.对于一棵具有n个结点的树,该树中所有结点的度数之和为多少?怎么算? n-1 每个节点都有且只有一个入度。除去根节点没有入度 所以一共是N-1。(这里所说的入度借鉴的是图论中对于入度的定义)。 2. 二叉树叶子...
  • 二叉查找简介二叉查找也称为有序二叉查找,满足二叉查找的一般...局限性及应用个二叉查找是由n个节点随机构成,所以,对于某些情况,二叉查找会退化成个有n个节点的线性链.如下图: b图为个普通的二...
  • 1.二叉树定义及性质 二叉树是一种树状结构,它特点是每个节点至多只能有两棵子树,并且二叉树子树有左右之分,...性质 3 对于任何一棵二叉树T,如果其终端节点数为n0,度为2节点数n2,则n0=n2+1。 2.二
  • 二叉查找 简介 二叉查找也称为有序二叉查找,满足二叉查找的一般性质,是指一棵树具有如下性质: ...一个二叉查找是由n个节点随机构成,所以,对于某些情况,二叉查找会退化成一个有n个节点的线性链...
  • 二叉查找 简介 二叉查找也称为有序二叉查找,满足二叉查找的一般性质,是指一棵树具有如下性质: ...一个二叉查找是由n个节点随机构成,所以,对于某些情况,二叉查找会退化成一个有n个节点的线性链...
  • 二叉排序 1.基本应用 二叉排序也称为也叫二叉查找,二叉搜索, BST。 满足二叉查找树的一般性质,是指一棵树具有如下性质: ...一个二叉排序是由n个节点随机构成,所以,对于某些情况,二...
  • 二叉查找 简介 二叉查找也称为有序二叉查找,满足二叉查找的一般性质,是指一棵树具有如下性质: ...一个二叉查找是由n个节点随机构成,所以,对于某些情况,二叉查找会退化成一个有n个节点的线性链.如...
  • 平衡查找之2-3

    2016-11-14 11:34:35
    前面介绍了二叉查找树(Binary Search Tree),他对于大多数情况下的查找和插入在效率上来说是没有问题的,但是他在最差的情况下效率比较低。本文及后面文章介绍的平衡查找树的...在一棵具有N 个节点的树中,我们希望该树
  • [STL]

    2020-06-05 14:39:32
    GITHUB:红黑 红黑简介 红黑本质上就是一棵二叉查找,但它在二叉查找的基础上增加了着色和相关的性质使得红黑相对平衡,从而...上面的5个性质使得一棵n个节点的红黑始终保持log n 的高度,从而使得红
  • 前面介绍了二叉查找树(Binary Search Tree),他对于大多数情况下的查找和插入在效率上来说是没有问题的,但是他在最差的情况下效率比较低。本文及后面文章介绍的平衡查找树的...在一棵具有N 个节点的树中,我们希望该树
  • 伸展(Splay Tree)

    2019-10-05 03:16:30
    理想情况下,一棵n个节点的二叉排序应该具有的深度,这样我们在二叉树中任意搜索一个节点的时间复杂度不会超过。最差情况下,一棵n个节点的二叉排序将会退化成一条naive的链,在这种情况下任意搜索一个节点的...
  • 2-3

    2017-05-23 21:31:48
    前面介绍了二叉查找树(Binary Search Tree),他对于大多数情况下的查找和插入在效率上来说是没有问题的,但是他在最差的情况下效率比较低。本文及后面文章介绍的平衡查找树的...在一棵具有N 个节点的树中,我们希望该树
  • 前面介绍了二叉查找树(Binary Search Tree),他对于大多数情况下的查找和插入在效率上来说是没有问题的,但是他在最差的情况下效率比较低。本文及后面文章介绍的平衡...在一棵具有N 个节点的树中,我们希望该树的高...

空空如也

空空如也

1 2 3 4 5 ... 7
收藏数 127
精华内容 50
关键字:

对于一棵具有n个节点的树