栈(stack)
限定仅在表尾进行插入和删除操作的线性表(一个线性表是
n个具有相同特性的数据元素的有限序列,线性表中数据元素之间的关系是一对一的关系)，表尾为栈顶，表头称为栈底。
栈基本操作（以数组为例）
1. 一个空栈
var Stack = [ ]; //字面量方式
var Stack = new Array() //构造函数模式
2.清空栈
// 1. length
StackA.length = 0;
// 2. 赋值[ ]
StackA = [ ];
//3.删除元素，并向数组添加新元素
splice()
//arr.splice( index, howmany , itemq, .... ,itemx)
//index : 必需，整数，规定添加/删除项目的位置，使用负数可从数组结尾处规定位置
//howmany : 必需，要删除的项目的数量，如果设置为0，则不会删除项目
//item, ...., itemX : 可选，向数组中添加新的项目
StackA.splice( -1 , StackA.length) //从尾部(索引为-1)删除元素
3.判断是否为空栈，返回true/false
function isEmpty( stack ){
if(stack.length == 0){
return false
} else {
return true
}
}
4.返回栈的元素个数
function stackLength ( stack ) {
return stack.length
}
5. 删除栈顶元素
//删除数组最后一个元素，把数组长度减1，并且返回它删除的元素的值
// 如果数组已为空，则pop()不改变数组，并返回undefined 值
pop ( )
function popTop ( stack) {
return stack.pop()
}
6. 插入新的栈顶元素
push ( ) //向数组的末尾添加一个或多个元素，并返回新的长度
//items为要添加的新元素构成的数组
function pushItem ( stack , items) {
stack.push (...items)
}
队列
和 栈 相反，队列 是一种先进先出（
FIFO）的线性表，只允许在表的一端进行插入，而在另一端进行删除元素，最早进入队列的元素最早离开。允许插入的一端称为队尾，允许删除的一端称为队头
队列操作
1.构造一个空队列 （以数组为例）
var Queue = [ ] ;
var Queue = new Array();
2.清空队列
// 1. length
QueueA.length = 0;
// 2. 赋值
QueueA = [ ];
// 3. splice（）
Queue.splice( 0 , QueueA.length) //从头部删除元素
// 4.判断是否为空
function isEmpty( queue ){
if(queue.length == 0){
return false
} else {
return true
}
}
// 5.返回元素个数
return queue.length
// 6. 删除队头元素
//将数组第一个元素从其中删除，并返回第一个元素的值，如果数组为空，将不进行任何操作，并返回undefined
shift ( )
queue.shift( )
// 7. 插入新的队尾元素
push ( ) //向数组的末尾添加一个或多个元素，并返回新的长度
//items为要添加的新元素构成的数组
function pushItem ( queue , items) {
queue.push (...items)
}
3.树和二叉树
以分支关系定义的层次结构。树 是
n (n>=0)个结点的有限集
在任意一棵非空树中：
（1） 有且仅有一个特定的称为 **根（root） **的结点 ；
（2） 当 n>1 时，其余结点可分为m (m>0) 个互不相交的有限集T1,T2,...,Tm, 其中每一个集合本身又是一棵树，并且称为根的 子树 。
如图 是有6个结点的树，其中A 是根，其余结点分为2个互不相交的子集，T1= {B, D, E} , T2 = { C, F} ,T1 , T2 都是根A 的子树，且本身也是一棵树，如T1的根为B，而T11 = {D } , T12 = {E}，则T11,T22都是B的子树，是只有一个根结点的树
二叉树
二叉树的特点是每个结点至多只有两课子树（即二叉树中不存在深度大于2的结点）。并且，二叉树的子树有左右之分，其次序不能任意颠倒
1. 二叉树的第i层上至多有2^(i-1)个结点 （i>=1）
2. 深度为K的二叉树至多有(2^k)-1个结点
二叉树分类
1. 满二叉树：一棵深度为k且有2^k - 1个节点的二叉树称为满二叉树
2. 完全二叉树：完全二叉树是指最后一层左边是满的，右边可能满也可能不满，然后其余层都是满的二叉树称为完全二叉树(满二叉树也是一种完全二叉树)
二叉树的存储结构
- 顺序存储结构
- 链式存储结构
二叉树遍历
1.先序遍历（前序遍历）
若二叉树非空，则依次执行如下操作：
⑴ 访问根结点；
⑵ 遍历左子树；
⑶ 遍历右子树。
2.中序遍历
若二叉树非空，则依次执行如下操作：
⑴ 遍历左子树；
⑵ 访问根结点；
⑶ 遍历右子树。
3. 后序遍历
若二叉树非空，则依次执行如下操作：
⑴ 遍历左子树；
⑵ 遍历右子树；
⑶ 访问根结点。
二叉查找树(二叉搜索树)
满足以下性质的二叉树
1. 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
2. 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
3. 它的左、右子树也分别为二叉查找树。
网友评论