数据结构

算法：

好的程序利用好的算法可以得到截然不同的效率。好的算法具有好的时间利用率与空间利用率。时间利用率包括函数的复杂度，其中不同的复杂度几乎差几个数量级，复杂度的排列顺序是N<NlogN<N2<N3。

其中FOR 函数的复杂度就是各个循环的乘积，IF-else的复杂度就是两个情况中复杂度最大的一种情况。两种复杂度相加取复杂度最大的那个，两种复杂度相乘取两种复杂度的乘积。

暂时学到比较有效的方法有二分法的分而治之，还有在线处理法的废而弃之（ps：各个完全是自己造的名字）；

线性结构：

线性链表，矩阵的多重链表

堆栈：先进后出

队列：先进先出

堆栈和队列都要注意单向链表的特殊性。

解决查找问题利用二分法最有效率；

判定树的概念：

1.结点的度：结点的子树个数

2.树的度；树的所有结点中最大的度数

3.叶结点，度为零的结点

二叉树

　　二叉树与普通树的区别在于二叉树有左右之分。

　　二叉树的分类：斜二叉树，完美二叉树（满二叉树），完全二叉树（有n个结点的二叉树，对树的结点按照从上到下，从左到右的顺序进行编号，编号为i的结点与满二叉树中编号为i的结点的位置相同）。

　　二叉树的几个重要的性质

　　　　1.一个二叉树第i层的最大节点的个数为：2**（i-1），i>1

　　　　2.深度为k的二叉树有最大的结点的总数为：2**k - 1，k>1;

　　　　3.对于任何非空的二叉树T，若n0表示叶结点的个数，n2是度为2 的非叶结点的个数，那么两者的关系是n0=n2+1.

　　二叉树的存储结构

　　　　1.顺序存储结构

　　　　　　完全二叉树：按从上到下从左到右的顺序存储

　　　　　　对于n个结点的完全二叉树的结点的父子关系（数组存储中的关系）：

　　　　　　　　a：非根结点的父节点是|i/2|：

　　　　　　　　b:结点的左孩子结点的序号为2i：

　　　　　　　　c：结点的右孩子的结点序号为2i+1；

　　　　　　　链表存储：

　　　　　　　　　　left data right

　　　　　　　　先序遍历：

　　　　　　　　　遍历的过程：

　　　　　　　　　　1》访问根结点：

　　　　　　　　　　2》先序遍历其左子树（将分支中的所有的左子树全部的遍历完了之后才开始遍历右子树）：

　　　　　　　　　　3》先序遍历其右子树

void post_order_traversal(BinTree BT)
{
if(BT)
printf("%d",BT->Data);
post_order_traversal(BT-> left);
post_order_traversal(BT-> Right);

}

中序遍历：

　　　　　　　　　　遍历的过程：

　　　　　　　　　　1》中序遍历左子树

　　　　　　　　　　2》访问根结点

　　　　　　　　　　3》中序遍历右子树

void post_order_traversal(BinTree BT)
{
if(BT)
post_order_traversal(BT-> left);
printf("%d",BT->Data);
post_order_traversal(BT-> Right);

}

　　　　　　　　后序遍历：

　　　　　　　　　1》后序遍历左子树

　　　　　　　　　2》后序遍历右子树

　　　　　　　　　3》访问根结点

void post_order_traversal(BinTree BT)
{
if(BT)
post_order_traversal(BT-> left);
post_order_traversal(BT-> Right);
printf("%d",BT->Data);
}

先序，后序和中序遍历的过程所经过的结点的路线是一样的，知识访问各节点的时间不同

中序遍历的非递归遍历算法

1》遇到一个结点，就把它压栈，并遍历它的左子树；

2》当左子树遍历结束后，从栈顶弹出这个结点并访问它

3》然后右指针再去中序遍历结点的右子树

void inorder_traversal(BinTree BT)
{
BinTree T=BT:
Stack S = CreatStack(MaxSize);
while(T || !IsEmpty(s))
{
while(T)
push(S,T);
T = T->Left;
}
if (!IsEmpty(s))
{
T = Pop(S);
printf("%5d",T->Data);
T = T->Right;
}
}

前序非递归遍历

void inorder_traversal(BinTree BT)
{
BinTree T=BT:
Stack S = CreatStack(MaxSize);
while(T || !IsEmpty(s))
{
while(T)

{

printf("%5d",T->Data);
push(S,T);
T = T->Left;
}
if (!IsEmpty(s))
{
T = Pop(S);

T = T->Right;
}
}

后序非递归遍历(太难了，待定)

层序遍历

　　层序遍历的基本过程

　　　　1:从队列中取出一个元素：

　　　　2：访问元素所指向的结点

　　　　3：若该元素所指向的结点的左右孩子结点非空则将器左右的孩子的指针顺序入队

void levelorderTraversal(BinTree BT)
{
　　Queue Q;BinTree T;
　　　　if(!BT)
　　　　return;
　　Q = CreatQueue(MaxSize);
　　AddQ(Q,BT);
　　while (!IsEmpty)(Q))
{
　　T = Delete(Q);
　　printf("%d ",T->Data);
　　if(T->Left) AddQ(Q,T->Left);
　　if(T->Right) AddQ(Q,T->Right);

}
}

二叉搜索树

　　1.非空左子树的所有的键值小于其根节点的键值。

　　 2.非空右子树的所有键值大于其根节点的键值

　　 3.左右子树都是二叉搜索树

　　•二叉树的查找操作（find）