1、一国标码、区位码、机内码之间的关系五笔输入法、拼音国标码：（“国家标准信息交换用汉字编码”（GB2312-80 标准） ）国标码是一个四位十六进制数，区位码是一个四位的十进制数，每个国标码或区位码都对应着一个唯一的汉字或符号，但因为十六进制数我们很少用到，所以大家常用的是区位码，它的前两位叫做区码，后两位叫做位码区位码：将 GB 231280 的全部字符集组成一个 9494 的方阵，每一行称为一个“区”，编号为 0l94；每一列称为一个“位”，编号为 0l94，这样得到 GB 231280 的区位图，用区位图的位置来表示的汉字编码，称为区位码。机内码：为了避免 ASCII 码和国标码同时使用时
2、产生二义性问题，大部分汉字系统都采用将国标码每个字节高位置 1 作为汉字机内码。这样既解决了汉字机内码与西文机内码之间的二义性，又使汉字机内码与国标码具有极简单的对应关系。汉字交换码：汉字信息处理系统之间或通信系统之间传输信息时，对每一个汉字所规定的统一编码，我国已指定汉字交换码的国家标准“信息交换用汉字编码字符集基本集”，代号为 GB 231280，又称为“国标码”。中国标码=区位码+20 20H（或十进制 32 32，或二进制 00100000 00100000）机内码=国标码+80 80H（或十进制 128 128，或二进制 10000000 10000000）机内码=区位码+A0 A0
3、H（或十进制 160 160，或二进制 10100000 10100000）例：“中”字位于区位码表的第 54 区第 48 位，它的区位码、国标码、机内码如下表所示十进制 十六进制 二进制区位码 国标码 机内码 区位码 国标码 机内码 区位码 国标码 机内码54 48 86 80 214 208 36 30 56 50 D6 D0 00110110 00110000 01010110 01010000 11010110 11010000二十进制、二进制、十六进制、八进制十进制以 D 表示(Decimal)，二进制以 B 表示(Binary) ，十六进制以 H 表示(Hex)，八进制以 O 表示
4、(Octal)。1十进制整数转二进制整数：法 1：除 2 取余，余数倒着写。法 2：按幂展开，如 35=25+21+20，(35) 10=(100011)22二进制整数转十进制整数：乘权相加。如(110010) 2=1*25+1*24+0*23+0*22+1*21+0*20=503二进制整数与十六进制整数互化：从最低位开始，每 4 位二进制化为一位十六进制数；反之每一位十六进制化为 4 位二进制。如(10011) 2=(0001 0011)2=13H， 4AH=(0100 1010)2=(1001010)24二进制整数与八进制整数互化：从最低位开始，每 3 位二进制化为一位八进制数；反之每一位
5、八进制化为 3 位二进制。如(10011) 2=(010 011)2=(23)8， (236)8=(010 011 110)2=(10011110)25十进制小数转二进制小数：法 1：乘 2 取余。法 2：按幂展开，如 0.375=2-2+2-3，(0.375) 10=(0.011)2显然，有些十进制小数转二进制时，是取不尽的，只能是不精确的。比如 0.3，取二进制位数不同时，能得到的不同值如下表所示：2 位 6 位 10 位 13 位(0.01)2=0.25 (0.010011)2=0.296875 (0.0100110011)2=0.2998046875 (0.0100110011001)
6、2=0.29992675781256二进制小数转十进制小数：乘权相加。如(0.1101) 2=1*2-1+1*2-2+0*2-3+1*2-4=0.81257二进制小数与十六进制小数互化：从小数第 1 位开始，每 4 位二进制化为 1 位十六进制数；反之每 1 位十六进制化为 4 位二进制小数。如(0.10011) 2=(0.1001 1000)2=0.98H， 0.4AH=(0.0100 1010)2=(0.0100101)28二进制小数与八进制小数互化：从小数第 1 位开始，每 3 位二进制化为 1 位八进制数；反之每 1 位八进制化为 3 位二进制。如(0.10011) 2=(0.100
7、110)2=(0.46)8， (0.26)8=(0.010 110)2=(0.01011)2三原码、反码和补码 var f:array1.10000of longint;fillchar(f,sizeof(f),$7f); 最高位表示符号，0 代表正数，1 代表负数。其它位表示数的绝对值。1正数的原码=反码=补码。如一个字节 8 位表示时，9 的原、反、补码均为 000010012负数的原码：最高位（符号位）为 1，其它位值=该数的绝对值的二进制表示。负数的反码：最高位为 1，其它位为原码取反。负数的补码：反码加 1（即最低位加 1） 。由负数的补码求原码：符号位为 1 不变，其它位取反，再在
8、最低位加 1。例：以 8 位二进制表示，则-3 的原码 10000011，反码 11111100，补码 11111101。计算机中运算过程中都是以补码进行！not 1 = -2not 2= -333 位二进制，原码、反码只能表示 7 个数，它们为-33。补码能表示 8 个数，它们是-43。其中原码和反码 0 的表示有两种，如下表所示。数值 -4 -3 -2 -1 -0 0 1 2 3原码 无 111 110 101 100 000 001 010 011反码 无 100 101 110 111 000 001 010 011补码 100 101 110 111 无 000 001 010 01
9、1n 位二进制,原码、反码只能表示 2n-1 个数,它们为-(2 n-1-1)2n-1-1。补码能表示 2n 个数,它们是-2 n-12n-1-14实数以科学计数法表示。尾数：二进制纯小数；阶码：二进制整数，表示 2 的次方。例：一个实数，尾数为以原码表示的 011，阶码为以补码表示的 1111，求该数以十进制表示的值尾数值(0.11) 2=0.75，阶码值-1（补码取反，再加 1 得真值） 。于是值为 0.75*2-1=0.375四数据的校验1奇偶校验：n 位二进制数中，n-1 位表示数据，最高位表示校验位。（1）奇校验：校验位的取值使 n 位数据有奇数个 1。当 n-1 位数据有奇数个 1
10、 时，校验位取 0; 当 n-1 位数据有偶数个 1 时，校验位取 1（2）偶校验：校验位的取值使 n 位数据有偶数个 1。当 n-1 位数据有偶数个 1 时，校验位取 0; 当 n-1 位数据有奇数个 1 时，校验位取 1例：数据 10111 采用奇校验时，得 110111，偶校验时得 010111。奇偶校验法能检查出奇数位的错误，不能检查出偶数位的错误。因为 2 位、4 位等同时出错，不会改变数据的奇偶性。奇偶校验法不能知道是哪一位出错。2海明码校验（奇或偶）（1）只能检查出一位出错情况，它能知道是哪一位出错了。不能查出二位及以上的差错。（2）有 m 位数据，最少需要的校验位数为 r，r
11、为使 m+r+12 r 成立的最小整数。所有第 2k 位为校验位，其它为数据位。校验位的值的计算：比如第 6 位（110）将影响第 2 位和第 4 位，第11 位（ 1011）将影响第 1、 2、8 位。比如有 8 位数据，需要 4 位校验位。第 1、2、4、8 位为校验位，第 3、5、6 、7、9、10、11、12 为数据位。以 ak表示第 k 位，采用偶校验时，各校验位的计算如下：(奇校验时，取相反值)a1=a3 xor a5 xor a7 xor a9 xor a11 a2=a3 xor a6 xor a7 xor a10 xor a11a4=a5 xor a6 xor a7 xor a
12、12 a8=a9 xor a10 xor a11 xor a12例：数据为 01001010位数的二进制表示 1 10 11 100 101 110 111 1000 1001 1010 1011 1100位数（第几位） 1 2 3 4 5 6 7 8 9 10 11 12偶校验 1 0 0 0 1 0 1 1 0 0 1 0奇校验 0 1 0 1 1 0 1 0 0 0 1 0五常见运算符及运算次序1几种逻辑运算符及常见的表示符号运算符 非 与 或 异或常见符号 NOT AND * OR + XOR +含义NOT true 得falseNOT false 得trueTrue and true
13、 得true其余情况得 falseFalse or false 得false其余情况得 true相同时得 false不同时得 true注意，我们有时以 1 表示 True，以 0 表示 False。2整数的逻辑运算（实数不能作逻辑运算）将数字转换为二进制补码表示（计算机中，整数是以补码存储的） ，然后按位作逻辑运算，1 作 True,0 作False，结果为二进制补码。例：如果数为 integer 型（16 位二进制） ，则：not 2=not (00000000 00000010)=(11111111 11111101)补 =(10000000 00000011)原 =-3not (-3)=
14、not(10000000 00000011)原 =not(11111111 11111101)补 =00000000 00000010 补 =257 and (-35)=00000000 00111001 and 11111111 11011101=00000000 00011001 补 =2557 or (-35)=00000000 00111001 or 11111111 11011101=11111111 11111101 补 =-357 xor (-35)=00000000 00111001 xor 11111111 11011101=11111111 11100100 补 =-283
15、运算符的级别： （1）括号内运算先运算；（2）级别较高的优先于级别较低的先运算；（3）同级运算从左至右运算；如下表所示，1 级为最高，2 级次之，3 级再次之，5 级为最低级。级别 1 2 3 4 5运算符 NOT（非） *（乘方） * / div mod and Xor + - or in = = 例：15 xor 3 or 10 得 14; 10 or 3 xor 15 得 4; not 1*2 得 4; 1 xor 2+1 得 4; 1+2 xor 1 得 2。4几种应该注意的运算：运算 ab 3 shL 4 25 shr 3 2*3 a mod b inc(a) Inc(s,t) De
16、c(s) Dec(s,t) a in s含义 a div b3 左移 4位即 3*24得 4825 右移 3位即 25 div 23得 323得 8即 a-a div b*b,注意 a 或b 为负数时的情况a:=a+1 S:=s+t S:=s-1 S:=s-t判断元素a 是否在集合 s 中判定元素 a 不在集合 S 中，使用 not (a in s)，不能使用 a not in s(连续两个运算符了，这是英语的说法)5集合运算(1)交集 或 (2)并集 或 (3)差值：以减号表示，A-B 表示从集合 A 除去集合 B 中有的元素。六计算机系统的组成1各种存储设备的速度寄存器高速缓冲存储器内存硬
17、盘 光盘 U 盘软盘、磁带CPU 处理的信息都放在寄存器中，寄存器的速度非常快，可以匹配高速的 CPU 的速度。但是寄存器的价格很高。现在不用的数据，会放在内存中，要用时，向内存中去读取。内存的速度远慢于 CPU，于是，在寄存器与内存之间设置了高速缓冲存储器。2操作系统的分类（1）单任务操作系统：DOS ，它是基于字符命令的操作系统，没有图形界面。（2）多任务操作系统：除了 DOS 以外，均为多任务操作系统。（3）网络操作系统：比如 window NT、windows2000 server（即服务器版） 、Linux、Unix、Netware 等。Windows98、windows2000 p
18、rofession 等不是网络操作系统。3存储容量换算单位 DreamWaver Flash MacroMedia1TB=1024GB 1GB=1024MB 1MB=1024KB 1KB=1024B 1B（字节）=8bit（位）例：下载速度为 10kbps,下载一幅大小为 96KB 的图像文件，需要多少时间？解：10kbps 指每秒 10K 位，所需时间为 96k*8/10k=76.8 秒=1.28 分4N 位二进制数，可以表示 2n 个不同信息。计算机系统软件系统硬件系统运算器控制器存储器输入设备:鼠标、键盘、扫描仪、麦克风( 话筒)等输出设备:显示器、打印机、绘图仪、耳机、音响等中央处理器
19、CPU内存储器外存储器RAM,随机存储器,另配的内存条,插在主板的内存条插槽上, 关机后信息丢失ROM,只读存储器,集成在主板上了,存储的是如何开机的指令等硬盘、光盘、U 盘、软盘、磁带系统软件应用软件 除了系统软件外的其它软件操作系统：如DOS、windows、Linux、Unix、Netware、OS2 、Xnix 等编程语言:如 C、Pascal、Basic、Fortran 等数据库:如 Access、FoxPro 、SQLServer、Oracle 等CPU 中 外存储器5MIPS：指 CPU 每秒执行百万条指令 Million Instructions Per Second七图像、视
20、频、矢量图1图像文件图像文件扩展名为 bmp、jpg、gif 等。其中 bmp 图像为 windows 自带的“画图”软件默认格式。它把一幅图像分为一个个很小很小的矩形，逐个描述每个小矩形的颜色。如果有 x 点，每点颜色会有 y 种可能性，这 y 种可能性需要 z 位二进制表示，则该幅图像需要 xz 位(bit)，即 xz/8 字节(B)。可以将 bmp 图像文件压缩为扩展名为 jpg 或 gif 的图像文件。其中 jpg 为有损压缩。它使用 JPEG 标准来压缩图像。JPEG 是 Joint Photographic Experts Group(联合图像专家组)的缩写。例 1：一幅分辨率为
21、800*600 的 24 位图像，需要多少存储空间？解：该图像有 800*600 格，每个小格图像颜色以 24 位二进制描述，共需存储空间 800*600*24 位=800*600*3B=1406.25KB 1.37MB（注：该图像每格颜色有 224=16777216 种色彩，非常接近真实的大自然了。 ）例 2：一幅分辨率为 1024*768 的 16 色图像，需要多少存储空间？解：该图像有 1024*768 格，每个小格图像颜色有 16 种，以 4 位二进制描述，共需存储空间 1024*768*4 位=1024*768/2B=384KB=0.375MB例 3：一幅分辨率为 1024*768
22、的黑白单色图像，需要多少存储空间？解：该图像有 1024*768 格，每个小格图像颜色有 2 种，以 1 位二进制描述，共需存储空间 1024*768*1 位=1024*768/8B=96KB2视频文件视频文件的扩展名有 avi,mpg,dat,wmv,asf,rm 等，其中 mpg,dat,wmv,asf,rm 为压缩过的视频文件。dat 为 VCD 格式，wmv,asf,rm 三者为流媒体文件，支持在网上边下载边播放。 Wmf 和 asf 为微软的 windows media player 能播放，rm 需要使用 real player 或 real one 软件播放。未压缩过的视频文件大
23、小的计算：例：一段 1 小时的视频，每秒播放 25 帧，画面为 640*480 的 24 位真彩色，问需要多少存储空间？解：该视频相当于每秒放 25 幅图片，每幅图片停留 0.04 秒，利用人的视觉残留，给人以连续的图像感觉。（1）1 幅图片存储空间为：640*480*24/8B=900kB（2）1 秒存储空间为 900KB*25=22500KB（3）1 小时存储空间为：22500kB*360079101MB77.2GB由此可见，未经压缩的 avi 视频文件实在是太大了，不仅需要很大的存储空间，且网上下载也太慢。在的mpeg 标准下，压缩比可以达到 200:1。MPEG 的全名为 Moving
24、 Pictures Experts Group，中文译名是动态图像专家组。八高级语言的执行方式: 1机器语言：二进制数表示的命令2汇编语言：低级的语言，与每台机器密切相关，运行效率比高级语言高。3高级语言：与每台机器无关（可移植性好） ，运行效率不如汇编语言程序.高级语言的执行方式:最终都要转换成二进制数表示的机器语言(目标程序，扩展名为 exe)编译方式：先形成目标程序，然后再一次性执行，如 C,Pascal,Fortran,Visual Basic 语言等。解释方式：逐条解释执行，不形成目标程序，如 Qbasic 语言。九IP 地址每台联网的计算机都会有一个 IP 地址。现在使用的 IP
25、地址系统称为 IPV4，使用 32 位二进制表示。而 IPV6使用 128 位二进制表示。为了方便使用，将 IPV4 的 32 位二进制分成 4 段，每段 8 位二进制，化成十进制值在0255 之间，每段之间加一个小数点，这叫点分十进制。网络设备根据 IP 地址的第一个字节来确定网络类型。A 类网络第一个字节的第一个二进制 位为 0；00000001 01111111，即十进制 1127。B 类网络第一个字节的前两个二进制位 为 10；10000000 10111111，即十进制 128191。C 类网络第一个字节的前三位 二进制位为 110，11000000 11011111，即十进制 19
26、2223。D 类网络第一个字节的前四位 二进制位为 1110，11100000 11101111，即十进制 224239。其余 240 及以上为 E 类地址。Internet 地址授权机构 (IANA)控制 IP 地址分配方案中，留出了三类网络号，给不连到 Internet 上的专用网用，分别用于 A，B 和 C 类 IP 网，具体如下： A 类 10.0.0.010.255.255.255 B 类 172.16.0.0172.31.255.255 C 类 192.168.0.0192.168.255.255 IANA 保证这些网络号不会分配给连到 Internet 上的任何网络，因此任何人都
27、可以自由的选择这些网络地址作为自己的网络地址。十域名在 Internet 上的计算机，可以申请一个域名。域名为以小数点分隔的字符，从右至左逐级递减。如： 表示中国(cn)、网络(net)、镇海中学(zhzx)、提供 www 服务的一台计算机。美国以外的网络，域名的最后一个字段为国名，比如中国 cn，日本 jp，英国 UK，台湾 TW 等。有些英文名的意思是约定俗成的。如下表所示： 英文 com gov edu net mil org含义 商业机构 政府部门 教育机构 网络 军事 其它组织十一一些网络名称名称 www Internet Intranet TCP/IP HTTP HTML含义 万维
28、网 因特网 内部网传输控制协议/ 网际协议Transmission Control Protocol/Internet Protocol超文本传输协议Hypertext Transfer Protocol 超文本标记语言HyperTextMark-upLanguage名称 FTP POP3 SMTP DNS含义 文件传输协议File Transfer Protocal 邮局协议,用于接收邮件 Post Offic Protocal V3简单邮件发送协议Simple Mail Transfer Protocol域名服务器,将域名翻译为IP 地址 Domain Name Server名称 Teln
29、et BBS LAN MAN WAN含义 远程登录 电子公告板Bulletin Board System 局域网LocalAreaNetwork 城域网Metropolitan Area Network 广域网wide area network十二各种排序方法 基于元素之间比较的排序方法，时间复杂度不会快于 O(nlogn)。选择排序 插入排序 冒泡排序 快速排序 归并排序 堆排序 希尔排序时间复杂度 O(n2) O(n2) O(n2) O(nlogn) O(nlogn) O(nlogn) 约 O(n1.5)稳定性 稳定 稳定 稳定 不稳定 稳定 不稳定 不稳定数据有序时 不变 变快 变快 变
30、慢 不变 不变 不变特殊应用 求第 k 大数 求逆序对数 优先队列如果待排序元素值在很小的范围内，则可以使用 O(n)时间的基数排序。十三线性表（一）数组和链表1已知二维数组的首元素地址，每个元素所占存储空间，求其它元素存储地址2下三角矩阵：n 行 n 列的数组，沿主对角线对称时，只要存储下三角即可。n 行 n 列的数组，将下三角按行存储至一维数组中， aj,k（j=k）对应一维数据中第(j-1)j/2+kn 行 n 列的数组，将下三角按列存储至一维数组中， aj,k（j=k）对应第(2n-k+2)(k-1)/2+j-k+13数组的优缺点:每次查询较快,只要 O(1)时间;每次插入和删除较慢
31、,会造成大量元素的移动, 需要 O(n)时间。链表的优缺点: 每次查询元素较慢, 需要 O(n)时间遍历链表 ; 每次插入和删除时间较快只要 O(1)时间。（二）队列和循环队列1先进先出（FIFO） ，一端（队尾）插入，另一端（队首）删除，可以以数组或链表来模拟。2用于宽度优先遍历3以 n 个位置的数组来存储队列时，线性队列中最多可以存储 n 个元素，循环队列可以存储 n-1 个元素。4循环队列中，如果以 head 表示队首，tail 表示下一个插入位置，则当前已有元素个数为(tail-head+n) mod n队空:tail=head 或(tail-head) mod n=0；队满: (ta
32、il-head+n) mod n=n-1 或(tail+1)mod n=head（三）栈1后进先出（LIFO ） ，插入和删除都在同一端（栈顶）进行2用于:语法检查、计算表达式的值、实现递归过程、函数调用、深度优先遍历(如二叉树中序、前序、后序遍历)十四树（一）树1结点的度:结点拥有的子树数;2树的度(Degree): 树内各结点的度的最大值;3叶子(Leaf)结点/终端结点 :度为 0 的结点;4内部结点/非终端结点/分支结点:度不为 0 的非根结点;5结点的层次:一般根为第 1 层;孩子结点的层次为双亲结点的层次+1;也有把根定为第 0 层的,请看题意。6树的深度/高度(Depth):树中
33、结点的最大层次;7树有结点数为 n，则边数 B=n-18一棵 m 度的树，度为 k 的结点有 nk 个，则叶子结点数 n0=1+n2+2n3+(m-1)nm9树的深度优先遍历:遍历根 A,深度优先遍历 A 的第 1 棵子树, 深度优先遍历 A 的第 2 棵子树, 深度优先遍历 A 的最后 1 棵子树。上图深度优先遍历得 ABEKLFCGDHMIJ10树的宽度优先遍历: 相当于层次遍历, 可以借助队列实现。上图宽度优先遍历得 ABCDEFGHIJKLM（二）二叉树1二叉树严格区分左子树和右子树2满二叉树:每层都充满的二叉树,h 层满二叉树有 2h-1 个结点3完全二叉树:最后一层所有结点均尽量向
34、左靠,其它层全部充满。（1）h 层的完全二叉树，结点数在 2h-1 和 2h-1 之间。（2）通过层次遍历顺序（或叫宽度优先遍历） ，使用数组 a 存储完全二叉树，则 ak的左子女为 a2k,右子女为 a2k+1,ak的双亲为 ak div 2。4平衡二叉树:任意点的左子树和右子树的高度差不超过 1（小于等于 1） 。5哈夫曼树:（1）结点的带权路径长度:树根到结点的路径长度与结点上权的乘积叫该结点的带权路径长度;（2）树的带权路径长度:树中所有叶子结点的带权路径长度之和;（3）哈夫曼树:带权路径长度最小的树称做最优二叉树或哈夫曼树.（4）构造哈夫曼树a. 根据给定的 n 个权值 w1,w2,
35、wn,构成 n 棵二叉树的集合 F=T1,T2,Tn,其中每棵二叉树 Ti 中只有一个带权为 wi 的根结点，其左右子树均为空。b在 F 中选取两棵根结点的权值最小的树作为左右子树，构造一棵新的二叉树，且置新的二叉树的根结点的权值为其左、右子树上根结点的权值之和。c在 F 中删除这两棵已用过的子树，并将新得到的树加入 F 中。7246 51118AB C DH I JMGE FK Ld重复 b、c，直至 F 中只有一棵树止，此时得到的树就是哈夫曼树。（5）哈夫曼树没有度为 1 的结点（又称为严格二叉树或正则二叉树）（6）有 n 个叶子结点的哈夫曼树中共有 2n-1 个结点6二叉树的遍历:除了深
36、度优先和宽度优先遍历外，还有前序、后序和中序。（1）前序:遍历根,前序遍历左子树, 前序遍历右子树;（2）后序:后序遍历左子树,后序遍历右子树, 遍历根;（3）中序:中序遍历左子树,遍历根, 中序遍历右子树;（4）已知前序和中序，或者已知后序和中序，可以唯一确定一棵二叉树，从而得到第三种遍历顺序已知前序和后序，不能唯一确定一棵二叉树。7堆:（1）最小堆的定义:首先是一棵完全二叉树;其次每个结点均不大于（小于等于）它的子女。（2）堆的存储:层次遍历存储至数组中。8二叉查找树:对于所有的点，均满足：左子树中所有点值根的值右子树中所有点的值中序遍历二叉查找树，得到所有点的升序排列。二叉查找树中插入和
37、查找的原理：如果值比根小，转向左子树，否则转化右子树！如果二叉查找树是平衡的, 每次插入和查找时间为 logn, n 个点共 O(nlogn)。最坏情况下,所有点成一条线状,共需比较 O(n2)次。十五图（一）图的表示1邻接矩阵表示法:（1）以 aj,k=0 表示点 j 至点 k 没有边;以 aj,k0 表示点 j 至点 k 有边相连。（2）如果边上没有权值,则有边时 aj,k=1，如果边上有值，则让 aj,k等于该值。（3）邻接矩阵需要 n2 的数组空间，与图中的边数是无关的。2邻接表（邻接链表）表示法:链表存储每一点出发有多少条边相连。存储空间与边数有关。当边数较少时，可以节省存储空间，提
38、高算法效率。3关联矩阵:存储第 k 条边与哪二个点相连。（二）图中相关概念1无向图中结点的度:与结点相连的边数n 个结点的无向图中，如果结点没有指向自己的边（即无自环） ，则图中最多有 n(n-1)/2 条边。有 n(n-1)/2 条边的无向图叫完全图。2有向图中，结点的出度为从该结点出发的边数; 结点的入度为指向该结点的边数。有向图中，所有结点的入度之和等于所有结点的出度之和。有向完全图共有 n(n-1)条边。3生成树:一颗哈夫曼树AB CDAB CDAB CDAB CDAB CD从 A 点出发的两棵宽度优先生成树 从 A 点出发的两棵深度优先生成树原始图在以 T 为根的树中插入值 dpT;while p 非空 do beginqp;/保存父结点if dp 处值 then pp 的左子女else p p 的右子女end;产生新结点,值为 d,父结点为 q在以 T 为根的树中查找值 dpT;while p 非空 doif d=p 处值 thenbreak/找到了退出循环else if dp 处值 then pp 的左子女else p p 的右子女 ;if p 非空 then 找到结点 pelse 没有找到
