数组和二叉树

数组的存储地址矩阵的压缩存储稀疏矩阵——三元组顺序表树定义树是n个节点的有限集。n0时称为空树。在任意一颗非空树中有且仅有一个特定的称为根root的结点。当n1时其余结点可分为mm0个互不相交的有限集t1、t2……其中每一个集合本身优势一颗树并称为根的子树SubTree。树的结点包含一个数据元素及若干指向其子树的分支。结点拥有的子树数称为结点的度。度为0的结点称为叶子Leaf或终端结点度不为0的结点称为非终端结点或分支结点。除根结点之外分支结点也称为内部结点。树的度是树内各结点的度的最大值。结点的子树的根称为该结点的孩子相应的该结点称为孩子的双亲。同一个双亲的孩子之间互称兄弟。结点的祖先是从根到该结点所经分支上的所有结点。以某结点为根的子树中的任一结点都成为该结点的子孙。结点的层次从根开始根为第一层根的孩子为第二层。双亲在同一层的结点互为堂兄弟树中结点的最大层次称为树的深度或者高度。有序树——从逻辑上看树中结点的各子树从左至右是有次序的不能互换。无序树——从逻辑上看树中结点的各子树从左至右是无序的可以互换。森林森林是m(m0棵互不相交的树的结合。对树中的每个结点而言其子树的集合即为森林。树的应用场景文件系统数据库索引决策树网络路由表达式树堆哈夫曼编码树二叉搜索树二叉树二叉树的定义二叉树是一种每个结点最多有两个子结点的树结构。二叉树的子树有左右之分其次序不能任意颠倒。深度为k的有n个结点的二叉树当且仅当其每一个结点都与深度为k的满二叉树的编号从1至n的结点一一对应时称之为完全二叉树。完全二叉树是一种特殊的二叉树其定义是除了最后一层外所有层的结点都达到了最大结点数并且最后一层的结点是从左到右依次排序的。二叉树的性质二叉树的遍历1.先序遍历步骤访问当前根节点。递归遍历左子树。递归遍历右子树。2.中序遍历步骤递归遍历左子树。访问当前根结点。递归遍历右子树。3.后续遍历步骤递归遍历左子树。递归遍历右子树。访问当前根结点。最优二叉树赫夫曼树给定N个权值作为N个叶子结点构造一棵二叉树若该树的带权路径长度路径长度达到最小称这样的二叉树为最优二叉树也称为哈夫曼树。哈夫曼树是带权路径长度最短的树权值较大的结点离根较近。