(3)一个结点所拥有的后件个数称为树的结点度； (4)树的最大层次称为树的深度。
在计算机中，可以用树结构来表示算术表达式，用树来表示算术表达式的原则是： (1)表达式中的每一个运算符在树中对应一个结点，称为运算符结点；
(2)运算符的每一个运算对象在树中为该运算符结点的子树(在树中的顺序为从左到右)；
(3)运算对象中的单变量均为叶子结点。 树在计算机中通常用多重链表表示。 考点17 二叉树的定义及其基本性质 1什么是二叉树
二叉树(binary tree)是由n(≥0)个结点的有限集合构成，此集合或者为空集，或者由一个根结点及两棵互不相交的左右子树组成，并且左右子树都是二叉树。二叉树可以是空集合，根可以有空的左子树或空的右子树。二叉树不是树的特殊情况，它们是两个概念。 二叉树具有如下两个特点：
(1)非空二叉树只有一个根结点；
(2)每一个结点最多有两棵子树，且分别称为该结点的左子树与右子树。
二叉树的每个结点最多有两个孩子，或者说，在二叉树中，不存在度大于2的结点，并且二叉树是有序树(树为无序树)，其子树的顺序不能颠倒，因此，二叉树有5种不同的形态 在二叉树中，一个结点可以只有左子树而没有右子树，也可以只有右子树而没有左子树。当一个结点既没有左子树也没有右子树时，该结点即是叶子结点) 2二叉树的基本性质
性质1：在二叉树的第入层上至多有2k-1个结点(k≥1)。 性质2：深度为m的二叉树至多有2m-1个结点。
深度为m的二叉树的最大的结点数是为二叉树中每层上的最大结点数之和，由性质1得到最大结点数。
性质3：对任何一棵二叉树，度为0的结点(即叶子结点)总是比度为2的结点多一个。 如果叶子结点n0，度为2的结点数为n2，则n0=n2+l。
设二叉树中度为1的结点数为n1，二叉树中总结点数为N，因为二叉树中所有结点均小于或等于2，所以有 N=n0+n1+n (1)
再看二叉树中的分支数，除根结点外，其余结点都有一个进入分支，设m为二叉树中的分支总数，则有
N=m+1 (2)
又由于二叉树中这m个分支是分别由非叶子结点射出的。其中度为1的每个结点射出1个分支，度为2的每个结点射出2个分支。因此，二叉树中所有度为1与度为2的结点射出的分支总数为n1+2n2 ，而在二叉树中，总的射出分支数应与总的进入分支数相等，即 m=n1+2n2 (3) 将(3)代入(2)式有 N=n1+2n2+1
比较(1)和(4)并化简得
n0=n2+1
性质4：具有n个结点的完全二叉树的深度至少为[log2n]+ 1，其中[log2n]表示log2n的整数部分。
3满二叉树与完全二叉树 (l)满二叉树
满二叉树是指这样的一种二叉树：除最后一层外，每一层上的所有结点都有两个子结点。深度为k的二叉树具有2k-1个结点。即在满二叉树的第k层上有2k-1个结点。 从上面满二叉树定义可知，必须是二叉树的每一层上的结点数都达到最大，否则就不是满二叉树。深度为m的满二叉树有2m-1个结点。 (2)完全二叉树
完全二叉树是指这样的二叉树：除最后一层外，每一层上的结点数均达到最大值；在最后一层上只缺少右边的若干结点。 转贴于：计算机二级考试_考试大【责编:daiy 纠错】 如果一棵具有n个结点的深度为k的二叉树，它的每一个结点都与深度为k的满二叉树中编号为1~n的结点一一对应。
为满二叉树和完全二叉树的结构比较。
从完全二叉树定义可知，结点的排列顺序遵循从上到下、从左到右的规律。所谓从上到下，表示本层结点数达到最大后，才能放入下一层。从左到右，表示同一层结点必须按从左到右排列，若左边空一个位置时不能将结点放入右边。完全二叉树除最后一层外每一层的结点数都达到最大值，最后一层只缺少右边的若干结点。
满二叉树也是完全二叉树，反之完全二叉树不一定是满二叉树。 性质5：具有n个结点的完全二叉树深度为[log2n]+ 1或[log2(n+1)]。 性质6：如果对一棵有n个结点的完全二叉树的结点按层序编号(从第1层到第[log2n]+1层，每层从左到右)，则对任一结点i(1≤i≤n)，有：
(1)如果i=1，则结点i无双亲，是二叉树的根；如果i>1，则其双亲是结点[i/2]； (2)如果2i≤n，则结点i为叶子结点，无左孩子；否则，其左孩子是结点2i； (3)如果2i+1≤n，则结点i无右孩子；否则，其右孩子是结点2i+1。 4二叉树的存储结构 在计算机中，二叉树通常采用链式存储结构。用于存储二叉树中各元素的存储结点由两部分组成：数据域与指针域。但在二叉树中，由于每一个元素可以有两个后件(两个子结点)，因此，用于存储二叉树的存储结点的指针域有两个：一个用于指向该结点的左子结点的存储地址，称为左指针域；另一个用于指向该结点的右子结点的存储地址，称为右指针域。 考点18 二叉树的遍历
所谓遍历二叉树，就是遵从某种次序，访问二叉树中的所有结点，使得每个结点仅被访问一次。
1前序遍历
前序遍历是指在访问根结点、遍历左子树与遍历右子树这三者中，首先访问根结点，然后遍历左子树，最后遍历右子树；并且，在遍历左右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树。前序遍历描述为：
若二叉树为空，则执行空操作。否则：①访问根结点；②前序遍历左子树；③前序遍历右子树。
2中序遍历
中序遍历是指在访问根结点、遍历左子树与遍历右子树这三者中，首先遍历左子树，然后访间根结点，最后遍历右子树；并且，在遍历左、右子树时，仍然先遍历左子树，然后访问根结点，最后遍历右子树。中序遍历描述为：
若二叉树为空，则执行空操作。否则：①中序遍历左子树；②访问根结点；③中序遍历右子树。
3后序遍历
后序遍历是指在访问根结点、遍历左子树与遍历右子树这三者中，首先遍历左子树，然后遍历右子树，最后访问根结点，并且，在遍历左、右子树时，仍然先遍历左子树，然后遍历右子树，最后访问根结点。后序遍历描述为：
若二叉树为空，则执行空操作。否则：①后序遍历左子树；②后序遍历右子树；③访问根结点
第2章 程序设计基础
2．1 程序设计方法与风格
就程序设计方法和技术的发展而言，主要经过了结构化程序设计和面向对象的程序设计阶段。
一般来讲。程序设计风格是指编写程序时所表现出的特点、习惯和逻辑思路。程序是由人来编写的，为了测试和维护程序，往往还要新闻记者和跟踪程序，因此程序设计的风格总体而言应该强调得意和清晰，程序必须是可以理解的。
要形成良好的程序设计风格，主要应注重和考虑下述一些因素。 1、源程序文档化
2、源程序文档化应考虑如下几点： （1） 符号名的命名：符号名的命名应具有一定的实际含义，以便于对程序功能的理解。 （2） 程序注释：下克的注释能够帮助读者理解程序。
（3） 礼堂组织：为使程序的结构一目了然，可以在程序中利用空格、空行、缩进待技巧使程序层次清晰。
2、数据说明的方法 在编写程序时，需要注意数据说明的风格，以便使程序中的数据说明更易于理解和维护。一般应注意如下几点：
（1） 数据说明的次序规范化鉴于程序理解、新闻记者和维护的需要，使数据说明次序固定，可以使数据的发生容易查找，也有利于测试、排错和维护。
（2） 说明语句中变量安排有序化。当一个说明语句说明多个变量时，变量按照字母顺序为好。
（3） 使用注释来说明复杂数据的结构。 3、 语句的结构
程序应该简单易懂，语句构造应该简单直接，不应该为提高效率而把语句复杂化。一般应注意如下：
（1） 在一行内只写一条语句；
（2） 程序编写应优先考虑清晰性；
（3） 除非对效率有特殊要求，程序编写要做清晰第一，效率第二； （4） 首先要保证程序正确，然后才要求提高速度； （5） 避免使用临时变量而使程序的可读性下降； （6） 避免不必要的转移； （7） 尽可能使用库函数；
（8） 避免采用复杂的条件语句；
（9） 尽量减少使用“否定”条件的条件语句； （10） 数据结构要有利于程序的简化；
（11） 要模块化，使模块功能尽可能单一化；
（12） 利用住处隐蔽，确保每一个模块的独立性； （13） 从数据出发去构造程序；
（14） 不要修补不好的程序，要重新编写； 4、输入和输出
无论是批处理的输入和输出方式，还是交互式的输入和输出方式，在设计和编程时都应该考虑如下原则：
（1） 对所有的输入数据都要检验数据的合法性； （2） 检查输入项的各种重要组合的合理性；
（3） 输入格式要简单，以使得输入的步骤和操作尽可能简单； （4） 输入数据时，应允许使用自由格式； （5） 应允许缺省值；
（6） 输入一批数据时，最好使用输入结束标志；
（7） 在以交互式输入/输出方式进行输入时，要在屏幕上使用提示符明确提示输入的请求，同时在数据输入过程中的输入结束时，应在屏幕上给出状态信息。
（8） 当程序设计语言对输入格式有严格要求时，应保持输入格式与输入语句的一致性；给所有的输入出加注释，并设计输出报表格式。
2．2结构化程序设计
一、结构化程序设计的原则
结构化程序设计方法的主要原则可以概括为自顶向下，逐步求精，模块化，限制使用goto语句。
1、 自顶向下：程序设计时，应先考虑总体，后考虑细节；先考虑全局目标，后考虑局部目标。不要一开始就过多追求众多的细节，先从最上层总目标开始设计，逐步使问题具体化。
2、 逐步求精：对复杂问题，应设计一些子目标作过渡，逐步细化。
3、 模块化：一个复杂问题，肯定是由若干稍简单的问题构成。模块化是把程序要解决的总目标分解为分目标，再进一步分解为具体的小目标，把每个小目标称为一个模块。
4、 限制使用goto语句 使用goto语句经实验证实：
（1）滥用GOTO语句确实有害，应昼避免；
（2）完全避免使用GOTO语句也并非是个明智的方法，有些地方使用GOTO语句，会使程序流程更清楚、效率更高；
（3）争论的焦点不应该放在是否取消GOTO语句，而应该放在用什么样的程序结构上。 其中最关键的是，肯定以提高程序清晰性为目标的结构化方法。 二、结构化程序的基本结构与特点
1、顺序结构：顺序结构是简单的程序设计，它是最基本、最常用的结构，所谓顺序执行，就是按照程序语句行的自然顺序，一条语句一条语句地执行程序程序。
2、选择结构：选择结构又称为分支结构，它包括简单选择和多分支选择结构，这种结构可以根据设定的条件，判断应该选择哪一条分支来执行相应的语句序列。
3、重复结构：重复结构又称为循环结构，它根据给定的条件，判断是否需要重复执行某一相同的或类似的程序段，利用重复结构可简化大量的程序行。分为两类：一是先判断后执行，一是先执行后判断。
优点：一是程序易于理解、使用和维护。二是编程工作的效率，降低软件开发成本。 三、结构化程序设计原则和方法的应用
要注意把握如下要素：
1、 使用程序设计语言中的顺序、选择、循环等有限的控制结构表示程序的控制逻辑。 2、 选用的控制结构只准许有一个入口和一个出口；
3、 程序语句组成容易识别的块，每块只有一个入口和一个出口； 4、 复杂结构应该嵌套的基本控制结构进行组合嵌套来实现； 5、 语言中所没有的控制结构，应该采用前后一致的方法来模拟； 6、 严格控制GOTO语句的使用。其意思是指：
（1） 用一个非结构化的程序设计语言去实现一个结构化的构造； （2） 若不使用GOTO语句会使功能模糊；
（3） 在某种可以改善而不损害程序可读性的情况下。 2．3面向对象的程序设计 一、关于面向对象方法 面向对象方法的本质，就是主张从客观世界固有的事物出发来构造系统，提倡用人类在现实生活中常用的思维方法来认识、理解和描述客观事物，强调最终建立的系统能够映射问题域，也就是说，系统中的对象以及对象之间的关系能够如实地反映问题域中固有事物及其关系。
优点：1、与人类习惯的思维方法一致 面向对象方法和技术以对象为核心。对象是由数据和容许的操作组成的封装体，与客观实体有直接的关系。对象之间通过传递消息互相联系，以模拟现实世界中不同事物彼此之间的联系。
面向对象的设计方法与传统的面向过程的方法有本质不同，这种方法的基本原理是：使用现实世界的概念抽象地思考问题从而自然地解决问题。它强调模拟现实世界中的概念而不强调算法，它鼓励开发者在软件开发的绝大部分过程中都用应用领域的要领去思考。
2、稳定性好 3、可重用性好
软件重用是指在不同的软件开发过程中重复作用相同或相似软件元素的过程。重用是提高软件生产率的最主要的方法。
4、易于开发大型软件产品 5、可维护性好
（1）用面向对象的方法开发的软件稳定性比较好 （2）用面向对象的方法开发的软件比较容易修改； （3）用面向对象的方法开发的软件比较容易理解。 （4）易于测试和调试。
二、面向对象方法的基本概念 1、对象（object）
对象是面向对象方法中最基本的概念。对象可以用来表示客观世界中的任何实体，也就是说，应用领域中有意义的、与所要解决的问题有关系的任何事物都可以作为对象，它既可以是具体的物理实体的抽象，也可以是人为的概念，或者是任何有明确边界的意义的东西。总之，对象是对问题域中某个实体的抽象，设立某个对象就反映软件系统保存有关它的信息并具有与它进行交互的能力。
面向对象的程序设计方法中涉及的对象是系统中用来描述客观事物的一个实体，是构成系统的一个基本单位，它由一组表示其静态特征的属性和它可执行的一组操作组成。
对象可以做的操作表示它的动态行为，在面向对象分析和面向对象设计中，通常把对象的操作也称为方法或服务。