二叉树

发表于 2017-02-11

二叉树

定义

定义：是n(n>=0)个结点的有限集合，该集合或者为空集(空二叉树)，或者由一个
根节点和两颗不互相交的、分别称为根的左子树和右子树的二叉树
特点：
-每个结点最多有两颗子树，不存在度大于2的结点
-左右子树有顺序，次序不能颠倒，即使只有一颗子树也要区分它是左子树还是右子树

五种基本形态：

空二叉树
只有一个根节点
根结点只有左子树
根结点只有右子树
根结点既有左子树又有右子树

特殊二叉树

1.斜树：只有左子树或只有右子树
2.满二叉树：该二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子都在同一层上
–特点：
1.叶子只能出现在最下一层
2.非叶子结点的度一定是2
3.在同样深度的二叉树中，满二叉树的节点个数一定最多，同时叶子也最多
3.完全二叉树：对一颗具有N个结点的二叉树按层序编号，如果编号为i(i<=i<=n)的结点与同样深度的满二叉树中编号为i的
结点位置完全相同，则这棵树称为完全二叉树
–特点：
1.叶子结点只能出现在最下两层
2.最下层的叶子一定集中在左部连续位置
3、倒数第二层，若有叶子结点，一定都在右部连续位置
4.如果结点度为1，则该结点只有左孩子
5.同样结点数的二叉树，完全二叉树的深度最小
满二叉树一定是完全二叉树，但完全二叉树不一定是满二叉树

二叉树存储结构

顺序结构

用数组存储，按层序遍历对比满二叉树顺序，没有结点的位置数组在该位置填空

二叉链表

每个结点包含一个数据域和两个指针域，两个指针分别指向该结点左右孩子结点

typedef struct BiTNode
{
ElemType data;
struct BiTNode *lchild,*rchild;
}BiTNode,8BiTree;

二叉树的遍历

从根结点出发，按照某种次序访问二叉树中所有结点，使每个结点被访问一次且仅被访问一次
1.前序遍历：根左右
若二叉树为空，则空操作返回;否则先访问根结点，然后前序遍历左子树，再前序遍历右子树
a.先访问根结点，然后访问根结点的左孩子
b.将根结点的左孩子视作子树根结点,继续访问其左孩子，再以这个左孩子结点为根再访问其左孩子直到叶结点
c.访问完该叶结点后，再访问该叶结点双亲的右孩子，
d.如果没有右孩子，则该子树访问完毕，继续访问该结点双亲的双亲的右孩子，再以该右孩子为根继续从步骤a开始访问
核心：从整棵树的根结点开始，每次将左孩子看成子树根结点,从上到下，从左到右
ABDHIEJCFKG
2.中序遍历：左根右
若二叉树为空，则空操作返回;否则从根节点根结点开始(并不是先访问根结点)，然后中序遍历左子树，然后访问根结点，再中序遍历右子树
核心：无论什么级别的子树树都从最左端叶结点开始，按左孩子，双亲，右孩子顺序遍历，从下到上，从左到右
HDIBEJAFKCG
3.后序遍历：左右根
若二叉树为空，则空操作返回;否则从左到右先叶子结点的方式遍历左右子树，最后访问根结点
核心：从最左端叶结点开始，按左孩子，右孩子，双亲顺序遍历，从左到右，从下到上
HIDJEBKFGCA
4.层序遍历
若二叉树为空，则空操作返回;否则从根节点开始，按层依次往下，每层从左到右依次遍历

二叉树的性质

性质一：在二叉树的第i层上至多有2^(i-1)个结点(i>=1)
性质二：深度为K的二叉树至多有2^K-1个结点(K>=1)
性质三：对于任何一颗二叉树T，如果其终端结点数为n0,度为2的结点数为n2,则n0=n2+1
性质四：具有n个结点的完全二叉树的深度为log2n取下限加1
性质五：如果对一颗有n个结点的完全二叉树(其深度为log2n取下限加1)的结点按层序编号对任一结点i(1<=i<=n)有以下性质
如果i=1,则结点i是二叉树的根，无双亲;如果i>1，则其双亲是结点i/2取下限
如果2i>n,则结点i无左孩子(结点i为叶子结点);否则其左孩子是结点2i
如果2i+1>n,则结点i无右孩子(结点i为叶子结点);否则其右孩子是结点2i+1

计算：
输出指定结点在该树中所在的层数

[未完成]

var str="AB DEC #";//约定前序遍历输入
var btree = {
  data:'',
  lchild:{},
  rchild:{}
};
console.log(btree);
function creatbtree(num,item){
  console.log(str[num])
  if(str[num]=="#");
  {
  return
  }
  if(str[num] == " "){
    item = null;
  }else{
    item.data = str[num];
    num+=1;
    item.lchild ={
      data:'',
      lchild:{},
      rchild:{}
    }  
    creatbtree(num,item.lchild);
    num+=1;
    item.rchild ={
      data:'',
      lchild:{},
      rchild:{}
    }
    creatbtree(num,item.rchild);
  }
}
creatbtree(0,btree);
console.log(btree.rchild)

关于树的一些定义

发表于 2017-02-08

树

定义：n(n>=0)个结点的有限集。当n=0时称为空树，在任意一颗非空树中：
——有且仅有一个特定的结点称为根
——当n>1时，其余结点可分为m(m>0)个互不相交]的有限集T1、T2…Tm,其中每一个集合本身又是一颗树，并且称为根的子树
结点：图中每一个圆圈称为树的一个结点
结点的度：结点拥有的子树数称为该结点的度
树的度：树内各结点度的最大值
叶结点/终端结点：度为0的结点
分支结点/非终端结点：度不为0的结点
内部结点：分支结点中除根节点以外的结点
结点的孩子：D是B的孩子
孩子的双亲：B是D的双亲
兄弟：D和E互称为兄弟
结点的祖先：从根到该结点所经过分支上的所有结点
结点的层次：从根开始定在一起,根为第一层，根的孩子为第二层
树的深度/高度：树中结点的最大层次,图中树的深度为3
有序树:如果将树中结点的各子树看成从左至右是有次序的不能互换的，则称该树为有序树，否则称为无序树
森林:m(m>=0)棵互不相交的树的集合。对树中每个结点而言，其子树的集合即为森林

以下遍历采用层序遍历

双亲表示法

每个结点由该结点数据和该结点双亲的下标组成,根结点双亲下标赋值为-1

下标	data	parent
0	A	-1
1	B	0
2	C	0
3	D	0
4	E	1
5	F	3
6	G	3
7	K	6
8	H	4
9	I	4
10	J	4

孩子表示法

每个结点由该结点数据和该结点双亲的下标、该结点孩子的下标组成,根结点双亲下标赋值为-1
无孩子则孩子属性赋值-1

下标	data	parent	children
0	A	-1	1,2,3
1	B	0	4
2	C	0	-1
3	D	0	5,6
4	E	1	8,9,10
5	F	3	-1
6	G	3	-1
7	K	6	-1
8	H	4	-1
9	I	4	-1
10	J	4	-1

兄弟表示法

每个结点由该结点数据和该结点双亲的下标、该结点兄弟的下标组成,根结点双亲下标赋值为-1
无兄弟则兄弟属性赋值-1

下标	data	parent	rightsib
0	A	-1	-1
1	B	0	2
2	C	0	3
3	D	0	-1
4	E	1	5
5	F	3	6
6	G	3	-1
7	K	6	-1
8	H	4	9
9	I	4	10
10	J	4	-1

双亲孩子表示法

所有结点组成一个数组，每个结点包含该结点数据属性,该结点双亲属性(由双亲结点下标表示)以及第一个孩子结点的下标
每一个孩子结点包含下一个孩子结点的下标,用js数组实现相当于兄弟表示法

下标	data	parent	nextchildren
0	A	-1	-1
1	B	0	2
2	C	0	3
3	D	0	-1
4	E	1	5
5	F	3	6
6	G	3	-1
7	K	6	-1
8	H	4	9
9	I	4	10
10	J	4	-1

# define MAX_TREE_SIZE 100
typedef char ElemType;
//孩子结点
typedef struct
{
	int child;						//孩子结点的下标
	struct CTNode *next;	//指向下一个孩子结点的指针
}*ChildPtr;

//表头结构
typedef struct
{
	ElemType data;				//存放在树中的结点数据
	int parent;						//存放双亲的下标
	ChildPtr firstchild;	//指向第一个孩子的指针
}
//树结构
typedef struct
{
CTBox nodes[MAX_TREE_SIZE];//结点数组
int r,n;
}

js实现：

var tree=[];
for(var i =0;i<11;i++){
  var prior = -1;
  var next = [];
  if(i==0){
    prior =-1;
  }else if(i>0&&i<4){
    prior = 0;
  }else if(i==4){
    prior = 1;
  }else if(i==5 || i==6){
    prior = 3;
  }else if(i>6 && i<10){
    prior = 4;
  }else{
    prior = 6;
  }
  tree.push({
    data:i,
    parent:prior,
  });
}
for(var i =0;i<11;i++){
 var children=[];
  for(var j =0;j<11;j++){
   if(tree[j].parent == i){
     children.push(j);
   }
  }
  tree[i].children = children.slice();
}
console.log(tree);

字符串(串结构)

发表于 2017-02-07

字符串

定义：串是由0个或多个字符组成的有限序列，又名字符串
1.空串：没有字符，直接由””表示
2.主串与子串：”hello”是”helloworld”的子串,”helloworld”是”hello”主串
3.字符串比较：比较字符串里每个字符的ASCII码大小,没有意义，一般看是否相等
4.存储结构
顺序存储：用一组地址连续的存储单元来存储串中的字符序列，
按照预定义大小，为每个定义的字符串变量分配一个固定长度的存储区，一般用定长数组来定义
链式存储：不常用
5.BF算法：
有两个字符串S和T，长度为N和M，首先S[1]和T[1]比较，若相等，则再比较S[2]和T[2],一直到T[M-1]为止;
若S[1]和T[1]不等，则T向右移动一个字符的位置，再依次进行比较
6.字符串模式匹配：依据BF算法,S是主串,T是子串这种定位操作即字符串模式匹配

BF算法

var string1="hellohannahworld";
var string2="hannah";
function BF(str1,str2){
  var i = 0;
  var j = 0;
  while(i<str2.length){
    while(j<str1.length){
      if(str2[i]==str1[j]){
        if(i==str2.length-1){
          var temp=j-str2.length+1;
          console.log("字符串匹配的起始位置为"+temp);
          return
        }
        j++;
        i++;
      }else{
        if(i>0){
          i=0;
        }
        if(i==0){
          j++
        }
      }
    }
  }
  console.log("两字符串一点也不匹配!")
  return
}
BF(string1,string2);

使用Git Bash建立本地仓库并同步github仓库

发表于 2017-02-03

建立本地仓库

1.选择仓库存放位置,新建文件夹,用作本地仓库
2.打开Git bash,cd 切换路径到该文件夹
3.执行以下命令

echo "该项目简短说明" >> README.md     ##输入“该项目简短说明”内容到README.md文件
git init
git add README.md                      ##将提交的文件(README.md)的信息添加到索引库
git commit -m "第一次提交"             ##依据索引库中的内容来进行文件的提交
																			 ##同时提交更改描述“第一次提交”

以上步骤完成本地仓库建立和将文件提交到本地仓库的工作

建立远成仓库

1.登录github账号,点击右上角“+”,选择“New repository”
2.填写仓库名称,简单描述
3.为避免与本地仓库READMD.md冲突，初始化时不勾选“Initialize this repository with a README”
4.点击“Create repository”,生成远程仓库

同步仓库

1.点击“Clone or download”, 复制远程仓库地址
2.执行以下代码

1 2	git remote add origin 远程仓库地址 ##将本地仓库推送到远成仓库 git push -u origin master ##将本地仓库推送到远程分支

以上步骤即完成本地仓库同步到远程仓库

执行git remote时，
若出现提示出错信息：fatal: remote origin already exists.
则先输入

1	git remote rm origin ##删除远程仓库

再执行推送语句 “git remote add origin 远程仓库地址”

更新远成仓库

若对本地仓库进行了修改
git add <文件名> 只是添加一个文件
git add . 可添加全部仓库文件
若执行“git add .”时，总出现警告：warning: LF will be replaced by CRLF in XXXXXXXXXXXXXX.
可执行语句 “git config core.autocrlf false”
添加完文件后执行提交操作
git commit -m “”
最后推送到远程仓库
git push -u origin master

[资源共享]（http://www.cnblogs.com/len0031/p/5831571.html)

循环队列

发表于 2017-02-02

假溢出

循环队列的容量是固定的，并且它的对头和队尾指针都可以随着元素出入队列而发生改变，
这样循环队列逻辑上就好像是一个环形存储空间,但在实际内存中，是不可能有真正的环形存储区的，
我们只是用顺序表模拟逻辑上的循环
因此,为防止发生假溢出,当我们采用循环队列时,front和rear不断加1,即使超出了地址范围，
也会自动从头开始,判断溢出，可采用取模处理
(rear+1)%QueueSize
(front+1)%QueueSize
取模即取余数，取得的值永远不会大于除数

定义一个循环队列

# define MAXSIZE 100
typedef struct{
	ElemType *base;	##存放内存分配基地址，也可以用数组存放
	int front;
	int rear;
}

初始化一个循环队列

initQueue(cyclQueue *q){
	q->base = (ElemType *)malloc(MAXSIZE sizeof(ElemType));
	if(!q->base){
	exit(0);
	}
	q->front = q->rear = 0;
}

入队列操作

insertQueue(cyclQueue *q,ElemType e){
	if((q->rear+1)%MAXSIZE == q->front){
	return;	##队列已满
	}
	q->base[q->rear] = e;
	q->rear = (q->rear+1)%MAXSIZE;
}

出队列操作

DeleteQueue(cyclQueue *q,ElemType e){
	if(q->rear == q->front){
	return;	##队列为空
	}
	*e = q->base[q->front];
	q->front = (q->front+1)%MAXSIZE;
}

递归

发表于 2017-02-02

递归

1.把有一个直接调用自己或通过一系列的调用语句间接的调用用自己的函数，称作递归函数
2.每个递归函数必须有一个终止调用的条件语句，否则陷入永不结束的无穷递归

斐波那契数列

迭代实现

var a=[];
a[0] = 1;
a[1] = 1;
for(var i =2;i<40;i++){
  a[i]=a[i-1]+a[i-2];
}
for(var j=0;j<40;j++){
  console.log(j,a[j]);
}

递归实现

function fib(n){
  if(n<2){
    return 1;
  }
  if(n>1 && n<40){
    return fib(n-1)+fib(n-2);
  }
}
console.log(fib(4));

n!阶乘递归算法

function fib(n){
    if(n>0){
      return n*fib(n-1);
    }else{
      return 1;
    }
    
}
console.log(fib(4));

汉诺塔问题

function hanoita(n,x,y,z){
  if(n==1){
    console.log(x+"->"+z);
  }else{
    hanoita(n-1,x,z,y);
    console.log(x+"->"+z);
    hanoita(n-1,y,x,z);
  }
}

hanoita(3,"x","y",'z');

递归字符串翻转

var string = "hello#";
var count = 0;
function print(){
  if(string[count]!="#"){
    count++;
    print();
  }
  count--;
  if(count>-1 && string[count]!="#"){
    console.log(string[count]);
  }
}
print();

折中查找法递归

代码链接

小结

1.迭代使用循环结构，递归使用选择结构
2.递归能使程序结构更清晰、简洁、容易让人理解，从而减少读懂代码的时间
3.大量的递归会建立函数的副本，会消耗大量时间和内存，而迭代不需要
4.递归函数分为调用和回退阶段，递归的回退顺序是它调用顺序的逆序

KMP算法

发表于 2017-02-02

next数组

经推导发现,进行模式匹配时,子串的移位规律与主串内容无关，与子串的内容有关,
因此根据子串的内容,生成基于子串的next数组，用来存放在对应位置如果发生失配,
应该将子串的哪个位置移动到失配位置
1.失配位置的前缀：永远是子串第一位
2.失配位置的后缀：失配位置的前一位
3.失配位置的前后缀相同位数：
从第一位开始的n位和从后缀开始倒数的n位相同,但前缀连续长度最长不能包含后缀那一位,
后缀也不能包含前缀,重叠也没关系,就说失配位置的前缀和后缀有n位相同
例：
ababc
若在倒数第二位的b位置(位置4)失配，则位置4的前缀是位置1的a,后缀是位置3的a,
从位置1和位置3开始,二者只有一位相同，则前后缀有1为相同,
若在最后一位位置5失配,前缀a虽然和后缀b不相同，但前缀连续两位ab和后缀连续两位ab相同
则c的前后缀有两位相同
ssssb
若在b位置失配,前缀连续sss,后缀连续sss,虽然重叠位置2和位置3的s,但前后缀相同位数为3
4.next数组值
失配位置的next数组值 = 失配位置的前后缀相同位数 + 1
特殊情况:子串位置1的next数组值为0,位置2的next数组值为1
例：

T:	a	b	a	b	a	a	a	b	a
下标:	1	2	3	4	5	6	7	8	9
next:	0	1	1	2	3	4	2	2	3

next数组获取代码实现

i后缀	1	2	。	3	4	5	6	7	。	8	9
j前缀	0	1	0	1	2	3	4	2	1	2	3

var string = "9ababaaaba"; //第一位存放字符串长度
function getnext(T){
  var next=[];
  next[0]=T.length-1;
  var i = 1;## 前缀
  var j = 0;## 后缀
  next[1] = 0;
  while(i<T[0]){
    if(j==0 || T[i] == T[j]){// 子串自己匹配自己
      i++;
      j++;
      next[i]=j;
    }else{
      j = next[j]; // 自己匹配发生失配,则视前缀为子串,后缀为主串,将前缀回溯
    }
  }
  console.log(next);
}
getnext(string);

KMP算法

代码链接

队列

发表于 2017-02-02

队列

1.先进先出的线性表，有顺序表和链表
2.只允许在一段插入，另一端删除

队列的链式存储结构

和栈相反，队列常用链表实现

typedef sruct QNode{
	ElemType data;
	struct QNode *next;
}QNode,*QueuePrt;
typedef struct {
	QueuePrt front;	##队头指针指向链队列的头结点(头结点不是必要的)
	QueuePrt rear;	##队尾指针指向终端结点，空队列时，front，rear都指向头结点
}LinkQueue;

入队列

InsertQueue(LinkQueue *q,ElemType e){
	QueuePrt p;
	p = (QueuePtr)malloc(sizeof(QNode));
	if(p==NULL){
		exit(0);
	}
	p->data = e;
	p->next = NULL;
	q->rear->next = p;
	q->rear = p;
}

出队列

DeleteQueue(LinkQueue *q,ElemType e){
	QueuePrt p;
	if(q->front ==q->rear)
	{
		retrun;
	}
	p=q->front->next;
	*e=p->data;
	q->front->next = p->next;
	if(q->rear ==p){
		q->rear = q->front;
	}
	free(p);
}

销毁一个队列

由于链队列建立在内存的动态区，因此当一个队列
不在有用时，应当及时销毁掉，以免过多占用内存空间

DestroyQueue(LinkQueue *q){
	while(q->front){
	q->rear = q->front->next;
	free(q->front):
	q->front = q->rear;
	}
}

简单实现

var list = [];
for(var i=0;i<5;i++){
  list.push({
    next:i+1
  })
}
list[4].next = null;
console.log(list);
//入队列
var length = list.length;
list.push({
  next:null
})
list[length-1].next=length;
console.log(list);
//出队列
list.splice(0,1);
console.log(list);
//清空
list=[];

栈

发表于 2017-02-02

栈

1.特殊线性表,所以也分为顺序存储和链式存储结构
2.表尾称为栈尾，表头称为栈底
3.元素必须后进先出;所有操作只能在表尾进行
4.插入操作叫做进栈/入栈/压栈，删除操作叫出栈/弹栈
5.最开始栈中不含有任何数据，叫空栈，此时栈顶就是栈底，
然后数据从栈顶进入，栈顶栈底分离，整个栈的当前容量变大，
数据出栈时从栈顶弹出，栈顶下移，整个栈的当前容量变小

栈的顺序存储结构
typedef struct
{
  ElemType *base; ##指向栈底的指针变量
  ElemType *top;  ##指向栈顶的指针变量
  int stackSize;  ##栈当前可使用的最大容量
}sqStack;

入栈操作

每次向栈中压入一个数据，top指针+1，直到栈满为止

出栈操作

在栈顶取数，栈顶指针随之下移，当前容量-1，

JS数组push和pop方法对数组处理

二进制转10进制
主要思想，每次pop数组最后一项，即二进制的位数依次增长，顺序i正好为指数

var list = [1,1,0,1,0,1,0,1];
var sum = 0;
var length = list.length;
for(var i = 0;i<length;i++){
  var pop = list.pop();
  sum+= pop*Math.pow(2,i);
}
console.log(sum);

二进制转8进制
主要思想，三位一组生成10进制，最后十进制按位数相加

var list = [1,1,0,1,0,1,0,1];
var hex = 0;
var length = list.length;
for(var i=0;i<length/3+1;i++){
  var sum = 0;
   for(var j = 0;j<3;j++){
    if(list.length>0){
      sum+=list.pop()*Math.pow(2,j);
    }
   }
   hex +=sum*Math.pow(10,i);
}
console.log(hex);

二进制转16进制
注意 >9时，转换成字母，pop，进行反序链接

var list = [1,1,0,1,0,1,0,1];
var hex = [];
var length = list.length;
for(var i=0;i<length/4+1;i++){
  var sum = 0;
   if(list.length>0){
   for(var j = 0;j<4;j++){
    if(list.length>0){
      sum+=list.pop()*Math.pow(2,j);
    }
   }
   if (sum >-1&&sum<10) {
    hex.push(String.fromCharCode(sum+48));
   }
   if(sum >9 && sum <16){
     hex.push(String.fromCharCode(sum+55));
   }
}
}
var str = "";
for(var l = hex.length-1;l>-1;l--){
  str+=hex[l];
}
console.log(str);

逆波兰表达式/后缀表达式

发表于 2017-02-02

栈的链式存储结构

typedef struct StackNode{
  ElemType data;          ##存放栈的数据
  struct StackNode *next;
}StackNode,*LinkStackPtr;
typedef struct LinkStack{
  LinkStackPrt top;        ##top指针
  int count;               ##栈元素计数器
}

栈链的入栈操作

假设元素值e的新结点是s,top为栈顶指针

Status Push(LinkStack *s,ElemType e){
  LinkStackPtr p=(LinkStackPtr)malloc(sizeof(StackNode));
  p->data = e;
  p->next = s->top;
  s->top = p;
  s->count++;
  return OK;
}

栈的出栈操作

假设变量p用来存储要删除的栈顶结点，将栈顶指针下移一位，最后释放p

Status Pop(LinkStack *s,ElemType e){
  LinkStackPtr p;
  if(StackEmpty(*s)){
  return ERROR;
  }
  *e=s->top->data;
  p=s->top;
  s->top = s->top->next;
  free(p);
  s->count--;
  return OK;
}

逆波兰表达式/后缀表达式

正常表达式–>后缀表达式
（1-2)x(4+5）–> 1 2 - 4 5 + x
1.计算后缀表达式
主要思想是判断字符是否为运算符，若为数字，则入栈，为运算符则连续出栈两次进行运算，再将运算结果入栈

var list =[1,2,3,4,'-','*','+']
var stack = [];
for(var i = 0;i<list.length;i++){
  if(!isNaN(list[i])){
      stack.push(list[i]);
    }else{
       var a = stack.pop();
       var b = stack.pop();
       if(list[i] =="+"){
        stack.push(b+a);
       }else if(list[i] =="-"){
        stack.push(b-a);
       }else if(list[i] =="*"){
        stack.push(b*a);
       }else if(list[i] =="/"){
        stack.push(b/a);
       }
  }
}
console.log(stack);

2.计算表达式转后缀表达式
主要思路
1，表达式中参与运算的数字、运算符以及小括号分割，形成待处理数组
2，循环判断
A.若字符为数字，入栈2，
B.若字符为“+”、“-”，分情况讨论
（1）此时栈1为空，入栈；
（2）栈1不为空，将“（”左括号以上的符号从栈1 pop到栈2，“（”留在栈1，处理完后，将“+”、“-”入栈1；
C若字符为“）”，将“（”以上符号从栈1 pop到栈2，“（”也pop出来
但不入栈2
D若字符为“/”“*”“（”直接入栈2
E其他情况，非法字符，抛出异常
3.将栈1元素pop到栈2；
栈2即后缀表达式
代码链接