新建 文本文档 (2).txt

这是一个用java做的二叉树的遍历的实例！

　　栈定义：
　　struct {
　　　datatype data[max_num];
　　　int top;
　　};

　　●队列定义
　　特点:先进先出
　　/入队列 in_queue(Q,x)
　　●队列的操作:
　　\出队列 del_queue(Q)
　　●队列存储结构:
　　链队列:
　　Typedef struct node{
　　　Datatype data;
　　　Struct node *next;
　　}NODE;
　　Typedef struct {
　　　NODE *front;
　　　NODE *rear;
　　}Queue;
　　顺序队列:
　　struct {
　　　datatype data[max_num];
　　　int front,rear;
　　};
　　问题:
　　队列ó线性表
　　假溢出<=循環队列
　　队列满，队列空条件一样<=浪费一个存储空间

　　递归
　　定义：问题规模为N的解依赖于小规模问题的解。问题的求解通过小规模问题的解得到。
　　包括二个步骤：
　　1） 递推 6!=>5!=>4!=>3!=>2!=>1!=>0!
　　2） 回归 720<=120<=24<=6 <=2 <=1 <=0
　　递归工作栈实现递归的机制。

　　2、有关算法：
　　1） 顺序，链表结构下的出栈，入栈
　　2） 循環，队列的入队列，出队列。
　　3） 链队列的入队列，出队列。
　　4） 表达式计算：后缀表达式 35+6/4368/+*- 
　　　　　　　　　　中缀表达式 （3+5）/6-4*（3+6/8） 

　 　 　 　 　 

　　由于中缀比较难处理，计算机内一般先将中缀转换为后缀。
　　运算：碰到操作数，不运算，碰到操符，运算其前两个操作数。
　　　中缀=>后缀
　　5) 迷宫问题
　　6) 线性链表的递归算法 一个链表=一个结点+一个链表
　　int fuction(NODE *p) {
　　　if(p==NULL) return 0;
　　　else return(function(p->next));
　　}

　　树与二叉树
　　一、 知识点:
　　1. 树的定义: data_struct(D,R);
　　其中:D中有一个根,把D和出度去掉,可以分成M个部分.
　　D1,D2,D3,D4,D5…DM
　　R1,R2,R3,R4,R5…RM
　　而子树Ri形成树.
　　1) 递归定义 高度


　　 2) 结点个数=1 
　　  
    O    --0
 
 O    O  --1
 
O  O  O  O --2
 

 此树的高度为2
 

　　2.二叉树定义:   
　　结点个数>=0 .
　　3. 术语:左右孩子,双亲,子树,度,高度等概念.
　　4. 二叉树的性质
　　●层次为I的二叉树 I层结点 2I 个
　　●高度为H的二叉树结点 2H+1-1个
　　●H(点)=E(边)+1
　　●个数为N的完全二叉树高度为|_LOG2n_|
　　●完全二叉树结点编号:从上到下,从左到右. 

i结点的双亲: |_i/2_| |_i-1/2_|    1    
i结点的左孩子: 2i 2i+1  2    3  
i结点的右孩子: 2i+1 2i+2 4  5  6  7 
(根) 1为起点 0为起点        

　　二叉树的存储结构:
　　　　1) 扩展成为完全二叉树,以一维数组存储。 

     A     
  B      C  
 D      E  F 
G  H    I    

数组下标 0 1 2 3 4 5 6 7 8 9 10 11 12 
元素 A B C D E F G H 　 　 　 　 I 

　　　　2) 双亲表示法  

数组下标 0 1 2 3 4 5 6 7 8 
元素 A B C D E F G H I 
双亲 -1 0 0 1 2 2 3 3 4 

　　　　3) 双亲孩子表示法 

数组下标 0 1 2 3 4 5 … 
元素 A B C D E F … 
双亲 -1 0 0 1 2 2 … 
左子 1 3 4 　 　 　 … 
右子 2 -1 5 　 　 　 … 

　　结构:
　　　　typedef struct {
　　　　　datatype data;
　　　　　int parent;
　　　　　int lchild;
　　　　　int rchild;
　　　　}NODE;
　　　　NODE tree[N]; // 生成N个结点的树
　　　　4) 二叉链表
　　　　5) 三叉链表
　　　　6) 哈夫曼树
　　5.二叉树的遍历
　　　先根 \
　　　中根 栈 中根遍历(左子树)根(右子树),再用相同的方法处理左子树,右子树.
　　　后根 /
　　　先,中序已知求树:先序找根,中序找确定左右子树.
　　　层次遍历(队列实现)
　　6.线索二叉树(穿线树)
　　　中序线索二树树目的:利用空指针直接得到中序遍历的结果.
　　　手段(方法):左指针为空,指向前趋,右指针为空,指向后继.
　　结点结构: 

ltag Lch Data rch rtag 

　　Ltag=0,lch指向左孩子,ltag=1,指向前趋结点
　　Rtag=0,rch指向右孩子;rtag=1,指向后继结点
　　中序遍历: 1) 找最左结点(其左指针为空)
　　　　2) 当该结点的rtag=1,该结点的rch指向的就为后继
　　　　3) 当rtag=0,后继元素为右子树中最左边那个
　　N个结点的二树有空指针N+1个 

　　周六我去了周SIR的办公室，他很热情，我问的是中序线索化二叉树的问题(递归)，关于这个问题我会在以后的笔记中作重点补充。我在这学校从来没有碰到过像他这样热情的老师，真的，大一的时候我们学校就开了C，当时我就连#include<stdio.h>这句话的意思都不晓得，别说是让我写程序了（到这份上也不怕把丑事都抖出来了:《数据结构》的课程设计也是哈科大的littlebob兄帮我做的，很遗憾，他高程就差几分，希望他早日成功，我们都要向他学习）等于说我的C知识九成都是在大二下学期的时候学的。而且全是自学的。拿这个周末来说吧。我三天时间就看完了一本C语言大全。当然，并不是从头到尾，只是根据自己的实际情况，重点是指针和数据结构那块。C最要的便是指针。程序员考试下午试题最重要的便是递归问题（1～2道，没有掌握就没希望了哦）。我说这些并不是为了表明自己多么用功，只是希望每位"学者"都有所侧重。


第三天 时间:9/23/2003 


　　排序查找是我自己觉得最头疼的算法了,常搞混去的啊.不知道各位学得如何,如果不错,还请告诉我一些经验!

查找 

一、 知识点　　　　/静态查找->数组　　　　
　　1、 什么是查找
　　　　　　　　　　\动态查找->链树
　　●顺序查找，时间复杂度 O(n)
　　●折半查找：条件：有序；时间复杂度 O(nlog2n) (时间复杂度实际上是查找树的高度)
　　●索引查找：条件：第I+1块的所有元素都大于第Ｉ块的所有元素。
　　　算法：根据index来确定X所在的块（i） 时间复杂度：m/2　　　　
　　　　　　在第Ｉ块里顺序查找X　　　　 　时间复杂度：n/2 
　　　总的时间复杂度：(m+n)/2
　　●二叉排序树　1）定义：左子树键值大于根节点键值；右子树键值小于根的键值，其左右子树均为二叉排序树。　
　　　　　　　　　2）特点：中序遍历有序->（删除节点用到此性质）
　　　　　　　　　3）二叉排序树的查找：如果根大于要查找的树，则前左子树前进，如果根小于要查找的树，则向右子树前进。
　　　　　　　　　4）结点的插入->二叉排序树的构造方法
　　　　　　　　　5）结点删除（难点）　 1、右子树放在左子树的最右边
　　　　　　　　　　　　　　　　　　　　2、左子树放在右子树的最左边
　　●avl树（二叉平衡树）：左右子树高度只能差１层，即｜h｜<=1其子树也一样。
　　●B树：n阶B树满足以下条件　1）每个结点（除根外）包含有N～2N个关链字。　　　　　　　　　　　　　　　　2）所有叶子节点都在同一层。
　　　　　　　　　　　　　　　　3）B树的所有子树也是一棵B树。
　　　特点：降低层次数，减少比较次数。

排序
一、知识点
　　1、排序的定义
　　　　　　　　　/内排序：只在内存中进行
　　2、排序的分类
　　　　　　　　　\外排序：与内外存进行排序　
　　　内排序：　　　/直接插入排序
　　　　1）插入排序
　　　　　　　　　　\shell排序
　　　　　　　　　　/冒泡排序
　　　　2）交换排序　
　　　　　　　　　　\快速排序
　　　　　　　　　　　/简单选择排序
　　　　3）选择排序 堆
　　　　　　　　　　　\ 锦标赛排序
　　　　4）归并排序（二路）
　　　　5）基数排序（多关链字排序）
　　3、时间复杂度（上午题目常考，不会求也得记住啊兄弟姐妹们！）

　　　　　　　　　* * * * * * 15 * * * 15 * * *
　　　　/稳定　　 * * * * * * * * 15 15 * * * *(前后不变)　
　　排序　　
　　　　\ 不稳定　* * * * * * * * 15 15 * * * *(前后改变)
　　经整理得:选择、希尔、堆、快速排序是不稳定的；直接插入、冒泡、合并排序是稳定的。

　　●锦标赛排序方法：　13　　16　　11　　18　　21　　3　　17　　6 
　　　　　　　　　　　　 \　　/　　　\　　/　　　\　 /　　　 \　/
　　　　　　　　　　　　　 13　　　　　11　　　　　3　　　　　 6 
　　　　　　　　　　　　　　\　　　　　/　　　　　　\　　　　 /
　　　　　　　　　　　　　　　　　11　　　　　　　　　　　3
　　　　　　　　　　　　　　　　　 \　　　　　　　　　　 /
　　　　　　　　　　　 　　　　　　　　　　　　3（胜出，将其拿出，并令其为正无穷&Go On）

　　●归并排序方法：　　13　　16　　11　　18　　21　　3　　17　　6 
　　　　　　　　　　　　 \　　/　　　\　　/　　　\　 /　　　\　 /
　　　　　　　　　　　　　13,16　　　 11,18　　　 3,21　　　 6,17
　　　　　　　　　　　　　　\　　　　　/　　　　　　\　　　　 /
　　　　　　　　　　　　　　11,13,16,18　　　　　　　3,6,17,21
　　　　　　　　　　　　　　　　　\　　　　　　　　　　 /
　　　　　　　　　　　　　　　　　 3,6,11,13,16,17,18,21

　　●shell排序算法：1）定义一个步长（或者说增量）数组D[m]；其中：D[m-1]=1(最后一个增量必须为1，否则可能不完全)
　　　　　　　　　2）共排m趟，其中第i趟增量为D[i],把整个序列分成D[i]个子序列，分别对这D[i]个子序列进行直接插入排序。
　　　　　　 　　程序如下： for(i=0;i<m;i++)
　　　　　　　　　　　　　　{for(j=0;j<d[i];j++)
　　　　　　　　　　　　　　　{对第i个子序列进行直接插入排序；　
　　　　　　　　　　　　　　　　　　注意：下标之差为D[i];
　　　　　　　　　　　　　　　}
　　　　　　　　　　　　　　}

　　●快速排序　( smaller )data ( bigger )
　　　d[]　i->　13　16　11　18　21　3　17　6　24　8　<-j
　　　先从后往前找，再从前往后找。　
　　　思想：空一个插入一个，i空j挪，j空i挪（这里的i,j是指i,j两指针所指的下标）。
　　　一次执行算法：1）令temp=d[0](枢纽)，i=0,j=n-1;
　　 　　　　　　　 2）奇数次时从j位置出发向前找第一个比temp小的元素，找到后放到i的位置(d[i]=d[j];i++;) i往后挪。
　　　　　　　　　　3）偶数次时从i开始往后找第一个比temp大的数，（d[j]=d[i];j--;)
　　　　　　　　　　4）当i=j时，结束循环。d[i]=temp；
　　再用递归对左右进行快速排序，因为快速排序是一个典型的递归算法。

　　●堆排序　
　　　　定义：d[n]满足条件：d[i]<d[2i+1]&&d[i]<d[2i+2] 大堆（上大下小）
　　　　　　　　　　　　　　d[i]>d[2i+1]&&d[i]>d[2i+2] 小堆（上小下大）
　　　　判断是否为堆应该将其转换成树的形式。总共排序n-1次

　　调整(重点)
　　　程序: flag=0;
　　　　　　while(i<=n-1) {
　　　　　　　if(d[i]<d[2*i+1])||(d[i]<d[2*i+2]))
　　　　　　　{ if(d[2*i+1]>d[2*i+2]) 8 24 {d[i]<->d[2*i+1]; 24 21 -> 8 21
　　　　　　　　i=2*i+1;
　　　　　　　　else {
　　　　　　　　　d[i]<->d[2*i+2];
　　　　　　　　　i=2*i+2;
　　　　　　　　}
　　　　　　　}
　　　　　　　else
　　　　　　　　flag=1; //是堆
　　　　　　}

　　堆排序过程：

　　●基数排序(多关键字排序)
　　扑克: 1) 大小->分配
　　　　　2) 花色->分配,收集
　　思想:分配再收集.
　　构建链表:链表个数根据关键字取值个数有关.
　　例:将下面九个三位数排序:
　　　　321 214 665 102 874 699 210 333 600
　　　定义一个有十个元素的数组:

　　　　　　　　　　a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9] 
　　　第一趟(个位): 210　321　102　333　214　665　　　　　　　　 699 
　　　　　　　　　　600　　　　　　　　 874
　　　　　　　结果: 210　600　321　102　333　214　874　665　699
　　　第二趟(十位): 600　210　321　　　 333　　　 665　874　　　 699 
　　　　　　　　　　102　214 
　　　　　　　结果: 600　102　210　214　321　333　665　874　699
　　　第三趟(百位): 102　210　321　　　　　　600　　　 874
　　　　　　　　　　　　 214　333　　　　　　665
　　　　　　　　　　　　　　　　　　　　　　 699