数据结构和算法的知识点
常见算法的时间复杂度
常数阶: O(1)
线性阶: O(N)
平方阶: O(n^2)
对数阶: O(logn)
nlog阶: O(nlogn)
立方阶: O(n^3)
指数阶: O(2^n)
阶乘阶: O(n!)
次方阶: O(n^n)
二叉树基本概念
森林:树的集合称为森林, 一个森林包含0至多棵树;
度:树中节点所拥有的子树的个数称为该节点的度;树中各节点度的最大值称为该树的度, 称度为M的树为M叉树;
叶子:度为0的节点称为叶子节点(也称为终端节点);
非叶:度不为0的节点称为分枝点(内节点);
元素:节点度数允许的最大值称为树的元数, 若树的元数为M则树中所有节点的度都不能超过M;
满二叉树:除了最后一层没有任何子节点外, 每一层的所有节点上都有两个子节点;
完全二叉树:完全二叉树是有满二叉树演变而来; 对于一个高度为h的二叉树, 如果其从0到第h-1层的节点都是满的, 最下层节点不满, 则所有的节点在左边连续排列, 空位都在右边, 这样二叉树称为完全二叉树;
完全二叉树
二叉检索(搜索)树:它或者是一棵空树，或者是具有下列性质的 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为二叉检索树;
平衡树:是一类树的统称, 如果树的高度限制在节点O(logn)范围内, 这样树结构称为平衡树;
平衡因子:表示节点的左右子树的高度之差(取值:-1, 0, 1);
二叉平衡检索树:这棵树既是AVL树又是二叉检索树;
例:AVL树, 它有以下特点
- h<= 1.45logn;
- 二叉树的左右子树的高度差不超过1;
- AVL是一棵二叉平衡树;
二叉树和森林(树)的转换规则:
二叉树到森林或者树:如果二叉树最顶端节点有右侧子节点,先将顶端节点补一个虚根, 具体规则为二叉树左侧的节点为子节点, 右侧的子节点为此节点的兄弟节点;
树转化为二叉树
森林转化为二叉树
二叉树的三种遍历方法:
先序(根)遍历 <DLR>
后序(根)遍历 <LRD>
中序(根)遍历 <LDR>
image.png
先序遍历（根左右）：A B D H E I C F J K G
中序遍历（左根右） : D H B E I A J F K C G
后序遍历（左右根） : H D I E B J K F G C A
任何n个不同节点的二叉树, 都可以由它的先序序列和中序序列唯一的确定; 同样根据后序序列和中序序列也能唯一的确定;
扩展先序序列或者扩展后序序列也能唯一确定一颗二叉树, 但是扩展中序序列不能唯一确定;
