前端数据结构

栈(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. 顺序存储结构
  1. 链式存储结构

二叉树遍历

1.先序遍历(前序遍历)
若二叉树非空,则依次执行如下操作:
访问根结点;
遍历左子树;
遍历右子树。

2.中序遍历
若二叉树非空,则依次执行如下操作:
遍历左子树;
访问根结点;
遍历右子树。

3. 后序遍历
若二叉树非空,则依次执行如下操作:
遍历左子树;
遍历右子树;
访问根结点。

二叉查找树(二叉搜索树)

满足以下性质的二叉树
1. 若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值;
2. 若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值;
3. 它的左、右子树也分别为二叉查找树。

©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容