算法树结构,基于树的算法

　　Yyds干货库存

　　一.概述1。树的概念树(英文：tree)是一种抽象数据类型(ADT)或实现这种抽象数据类型的数据结构，用于模拟具有树状结构的数据集。它是由n(n=1)个有限节点组成的层次集合。它被称为“树”，因为它看起来像一棵颠倒的树，也就是说，它的根朝上，叶子朝下。它具有以下特点：

　　每个节点有零个或多个子节点；没有父节点的节点称为根节点；每个非根节点只有一个父节点；除了根节点，每个子节点可以被分成多个不相交的子树；例如：

　　2.树的术语：节点的度：一个节点所包含的子树的个数称为该节点的度；树的度：一棵树中最大节点的度称为树的度；叶节点或终端节点：零度的节点；父节点或父节点：如果一个节点包含子节点，则该节点称为其子节点的父节点；子节点或子节点：一个节点中包含的子树的根节点称为该节点的子节点；兄弟节点：具有相同父节点的节点称为兄弟节点；节点的层次结构：从根开始定义，根是第一级，其子节点是第二级，以此类推；树的高度或深度：树中节点的最高级别；堂兄弟节点：同一级父节点的节点是彼此的堂兄弟；节点的祖先：从根到节点的分支上的所有节点；后代：子树中以某个节点为根的任何节点都称为该节点的后代。森林：m(m=0)棵不相交的树的集合称为森林；3.树的类型无序树：树中任何节点的子节点之间都没有顺序关系。这种树叫无序树，也叫自由树；有序树：树中任何节点的子节点都具有有序关系。这种树叫做有序树。二叉树

　　:每个节点最多有两个子树的树称为二叉树；完全二叉树：对于二叉树，假设其深度为d(d 1)。除了D层，其他层的节点数都达到了最大，D层的所有节点都是从左到右连续紧密排列的。这样的二叉树称为完全二叉树，其中完全二叉树定义为所有叶子节点都在底部的完全二叉树；平衡二叉树(AVL树):二叉树当且仅当任意节点的两个子树的高度差不大于1；排序二叉树(二叉查找树(英文：二叉查找树)，又称二叉查找树和有序二叉树)；霍夫曼树(用于信息编码):加权路径最短的二叉树称为霍夫曼树或最优二叉树；B-tree:一种自平衡二叉查找树，可以优化读写操作。它可以保持数据有序，并且有两个以上的子树。4.树形存储和呈现顺序存储：数据结构存储在固定数组中，但在遍历速度上有一定优势，但由于空间较大，是非主流二叉树。二叉树通常以链的形式存储。

　　链式存储：

　　因为节点数无法掌握，所以常见树的存储表示都转换成二叉树进行处理，子节点数最多为2。

　　5.常见的树应用场景1)xml、html等。所以为这些东西写解析器的时候不可避免的要用到树。

　　2)路由协议是一种使用树的算法。

　　3)mysql数据库索引

　　4)文件系统的目录结构

　　5)那么多经典的AI算法其实都是树搜索，机器学习中的决策树也是树结构。

　　二、二叉树1、二叉树的基本概念二叉树是每个节点最多有两个子树的树结构。通常子树被称为“左子树”和“右子树”。

　　2.二叉树的性质(特征)性质1:二叉树的第I层最多有2 (I-1)个节点(i 0)。

　　性质：深度为k的二叉树最多有(k ^ 0)个2^k-1节点

　　3:对于任意二叉树，如果叶节点数为N0，度为2的节点总数为N2，则N0=N2 1；

　　属性：具有n个节点的完整二叉树的深度必须是log2(n-1)

　　5:对于一棵完整的二叉树，如果从上到下从左到右编号，编号为I的节点必有其左子编号2i和右子编号2i+1；父代的个数必须是I/2 (I=1是根，除外)

　　1)完全二叉树3354如果二叉树的高度为H，则除H层外，其他所有层(1 ~ h-1)的节点数达到最大。h层有叶子节点，叶子节点从左到右依次排列，是一棵完整的二叉树。

　　2)全二叉树3354除叶节点外，每个节点都有左右子叶，叶节点在底部。

　　3.二叉树的节点表示和树的创建。通过在Node类中定义三个属性，它们是elem本身的值，lchild的左子和rchild的右子。

　　类节点(对象):

　　节点类

　　def __init__(self，elem=-1，lchild=None，rchild=None):

　　self.elem=elem

　　self.lchild=lchild

　　self.rchild=rchild

　　创建一个树类，给一个根节点，一开始是空的，然后添加节点。

　　类别树(对象):

　　树类

　　def __init__(self，root=None):

　　self.root=root

　　定义添加(self，elem):

　　向树中添加节点

　　节点=节点(元素)

　　#如果树为空，则为根节点赋值

　　如果self.root==None:

　　self.root=node

　　否则：

　　队列=[]

　　queue.append(自我. root)

　　#分层遍历现有节点

　　排队时：

　　#弹出队列的第一个元素

　　cur=queue.pop(0)

　　如果cur.lchild==None:

　　cur.lchild=node

　　elif cur.rchild==None:

　　cur.rchild=node

　　否则：

　　#如果左右子树不为空，加入队列继续判断。

　　queue.append(cur.lchild)

　　queue.append(cur.rchild)

　　三、二叉树的遍历树的遍历是树的一个重要操作。遍历是指访问树中所有节点的信息，即树中每个节点依次访问一次，且只访问一次。我们称这种访问为所有节点的遍历。然后树的两种重要遍历模式是深度优先遍历和广度优先遍历。深度优先一般使用递归，广度优先一般使用队列。一般来说，大部分可以递归实现的算法也可以通过堆栈实现。

　　1.深度优先遍历对于一棵二叉树，深度优先搜索就是沿着树的深度遍历树的节点，尽可能深的搜索树的分支。那么深度遍历有三个重要的方法。这三种方法通常用于访问树的节点。两者的区别在于访问每个节点的顺序不同。这三种遍历称为前序遍历、中序遍历和后序遍历。我们先给它们一个详细的定义，然后用例子看看它们的应用。

　　1)一阶遍历

　　在前序遍历中，先访问根节点，然后递归使用前序遍历访问左子树，再递归使用前序遍历访问右子树。

　　节点-左侧子树-右侧子树

　　定义前序(自身，根):

　　一阶遍历的递归实现

　　如果root==None:

　　打印root.elem

　　self.preorder(root.lchild)

　　self.preorder(root.rchild)

　　2)中间顺序遍历

　　在中序遍历中，我们递归地使用中序遍历来访问左边的子树，然后是根节点，最后递归地使用中序遍历来访问右边的子树。

　　左子树-根节点-右子树

　　定义顺序(自身，根):

　　顺序遍历的递归实现

　　如果root==None:

　　self.inorder(root.lchild)

　　打印root.elem

　　self.inorder(root.rchild)

　　3)后序遍历

　　在后序遍历中，我们首先递归地使用后序遍历来访问左子树和右子树，最后访问根节点。

　　左子树-右子树-根节点

　　定义后序(自身，根):

　　递归实现后续遍历

　　如果root==None:

　　self.postorder(root.lchild)

　　self.postorder(root.rchild)

　　打印root.elem

　　2.广度优先遍历(层次遍历)从树的根开始，从左到右从上到下遍历整棵树的节点。

　　def width _ travel(自己，根):

　　使用队列实现树的层次遍历

　　如果root==None:

　　队列=[]

　　queue.append(根)

　　排队时：

　　node=queue.pop(0)

　　打印node.elem，

　　if node.lchild！=无：

　　queue.append(node.lchild)

　　if node.rchild！=无：

　　queue.append(node.rchild)

　　转载请联系作者取得转载授权，否则将追究法律责任。

郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。

相关文章阅读