可以做长页海报的网站,网站文案技巧,沙发网站建设,网站开发和网页开发有什么区别基础知识#xff1a; 树是一种非线性结构#xff0c;其严格的数学定义是#xff1a;如果一组数据中除了第一个节点#xff08;第一个节点称为根节点#xff0c;没有直接前驱节点#xff09;之外#xff0c;其余任意节点有且仅有一个直接前驱#xff0c;有零个或多个直接… 基础知识 树是一种非线性结构其严格的数学定义是如果一组数据中除了第一个节点第一个节点称为根节点没有直接前驱节点之外其余任意节点有且仅有一个直接前驱有零个或多个直接后继这样的一组数据形成一棵树。这种特性简称为一对多的逻辑关系。 树的基本术语 树是由若干个节点组成的分支每个节点都可能组成一棵树 1.根(root) 树的第一个节点没有直接前驱如上图的A 2.双亲节点(parent): 某节点的直接前驱称为该节点的双亲节点或称为父节点例如上图A 是B的父节点。 3.孩子节点(child): 某节点的直接后继称为该节点的孩子节点例如上图中的B、C、D均为 A的孩子节点。 4.节点的层次(level): 从树根开始根为第一层根的孩子为第二层树中节点的最大层次 称为树的深度或者高度。比如上图中节点E的层次是3. 5.节点的度(degree): 节点拥有的子树的数量称为该节点的度度为0的节点称为叶子节点或者终端节点度不为0的节点称为非终端节点或者分支节点比如上图节点B的度为2。 6.叶子(leaf): 一棵树中度等于0的节点称为叶子节点如上图K,L,G,M,I为叶子 二叉树
二叉树是一种属性结构他的特性是每个节点最多只有两棵子树即二叉树中不存在度大于2的节点并且二叉树的子树有左右之分其次序不能任意颠倒。 二叉树的形态可以多种多样但通常有以下几种基本形态 满二叉树Full Binary Tree 完全二叉树Complete Binary Tree 平衡二叉树Balanced Binary Tree 二叉搜索树Binary Search Tree, BST 哈夫曼树Huffman Tree 遍历
深度优先遍历
前中后序遍历都是递归算法。前序遍历为例当访问完根节点进而要访问左子树时由于左子树本身一棵二叉树因此也需要进行前序遍历也就是先访问左子树的根节点然后再依次访问左子树的左孩子和左子树的右孩子。
前序遍历 : 根节点 - 左子树 - 右子树F-BADCE-GIH中序遍历 : 左子树 - 根节点 -右子树ABCDE-F-GHI后序遍历 : 左子树 - 右子树 - 根节点ACEDB-HIG-F
广度优先遍历
按层遍历从上到下从左到右 特点
在二叉树的第i层上最多有2^(i-1)个节点(i0)深度为K的二叉树最多有2^k-1个节点对任意一颗二叉树T如果其叶子节点数为n0,度为2的节点为n2则有n2 n0-1
存储结构
存储结构即保存了元素又保存了关系(根据二叉树的信息可以把二叉树还原)
顺序存储结构
由于在顺序存储数据之间的逻辑关系是用物理位置来表达而二叉树中每一个节点都有一个对应的标号因此可以使用标号来作为数组的下标但除非是完全二叉树否则会浪费存储空间 链式存储结构
链式存储思路与链表类似使用指针来直接将节点的逻辑关系串联起来 满二叉树
一棵深度为k且具备有2^k-1个节点的二叉树称为满二叉树在不改变深度的情况下无法再往这棵树上加节点。
完全二叉树
除去最后一层后为满二叉树最后一层的节点必须一次从左往右边排(左边不排满就不要排右边)完全二叉树的特性是不浪费空间
二叉搜索树BST
按照小-中-大(或大-中-小)的规律来存储数据即对于任意一个节点都可以明确找到其值大于或等于其左孩子节点且小于或等于其有孩子节点。 平衡二叉树AVL
它或者是一棵空树或者是具有以下特性的二叉搜索树BST
它的左子树或者右子树都是平衡二叉树左子树和右子树的深度之差的绝对值不超过1(1,-0,-1)
将二叉树上的节点的平衡因子定义为该节点的左子树的深度减去它右子树的深度当平衡因子的绝对值大于1则该二叉树不平衡。
不平衡二叉树转变为平衡二叉树
单向右旋平衡处理 单向左旋平衡处理 双向旋转(先左后右)平衡处理 双向旋转(先右后左)平衡处理 哈夫曼树
又称最优二叉树是一种特殊的二叉树。
构造 带权路径长度
每层叶子结点*对应层权值之和6811*225*371
