二叉树是个有限元素的集合，该集合或者为空，或者由一个称为“根”的元素及两个不相交的，被分别称为左子树和右子树的二叉树组成。当集合为空时，称该二叉树为空二叉树。在二叉树中，一个元素也称为也称做一个结点。（笔者认为，二叉树可以理解为每一个点最多分成两个叉的树或空树是二叉树，如果有一个分支在三个以上就不是了。）二叉树每一个结点的度最大为2.二叉树是树结构的一种，在树的结构中，每一个结点只有一个前件，称为父结点，没有前件的结点只有一个，称为树的根结点，简称为树的根。在树的图形表示中，总是认为在用直线连起来的两端结点中，上端结点是前件，下端结点是后件。在树的结构中，每一个结点可以有多个后件，它们都称为该结点的子结点。没有后件的结点称为叶子结点。在树的结构中，一个结点所拥有的后件个数称为该结点的度，在树中，所有结点中最大的度称为树的度。
成都创新互联自2013年创立以来，是专业互联网技术服务公司，拥有项目成都网站设计、成都做网站网站策划，项目实施与项目整合能力。我们以让每一个梦想脱颖而出为使命，1280元郸城做网站,已为上家服务,为郸城各地企业和个人服务,联系电话:028-86922220
如图所示的二叉树中ABCDEFG为树的结点，其中A为根结点，BDE为子结点，CGF为叶子结点根结点A度为1 （只有B一个结点）
结点B、D度均为2（有两个结点C、D和E、F），因此树的度为2 二叉树的计算（性质）：(1)
在二叉树中，第i层的结点总数不超过2^(i-1)；
(2)
深度为h的二叉树最多有2^（h+1）-1个结点(h=1)，最少有h个结点；
(3)
对于任意一棵二叉树，如果其叶结点数为N0，而度数为2的结点总数为N2，
则N0=N2+1；
(4)
具有n个结点的完全二叉树的深度为int（log2n）+1
(5)有N个结点的完全二叉树各结点如果用顺序方式存储，则结点之间有如下关系：
若I为结点编号则
如果I1，则其父结点的编号为I/2；
如果2*I=N，则其左结点（即左子树的根结点）的编号为2*I；若2*IN，则无左子树；
如果2*I+1=N，则其右子树的结点编号为2*I+1；若2*I+1N，则无右子树。
(6)给定N个节点，能构成h(N)种不同的二叉树。
h(N)为卡特兰数的第N项。h(n)=C(n,2*n)/(n+1)。
遍历概念
所谓遍历(Traversal)是指沿着某条搜索路线 依次对树中每个结点均做一次且仅做一次访问 访问结点所做的操作依赖于具体的应用问题 遍历是二叉树上最重要的运算之一 是二叉树上进行其它运算之基础
遍历方案
．遍历方案 从二叉树的递归定义可知 一棵非空的二叉树由根结点及左 右子树这三个基本部分组成 因此 在任一给定结点上 可以按某种次序执行三个操作 （ ）访问结点本身(N) （ ）遍历该结点的左子树(L) （ ）遍历该结点的右子树(R) 以上三种操作有六种执行次序 NLR LNR LRN NRL RNL RLN 注意 前三种次序与后三种次序对称 故只讨论先左后右的前三种次序
．三种遍历的命名 根据访问结点操作发生位置命名 ① NLR 前序遍历(PreorderTraversal亦称(先序遍历)) ——访问结点的操作发生在遍历其左右子树之前 ② LNR 中序遍历(InorderTraversal) ——访问结点的操作发生在遍历其左右子树之中(间) ③ LRN 后序遍历(PostorderTraversal) ——访问结点的操作发生在遍历其左右子树之后 注意 由于被访问的结点必是某子树的根 所以N(Node) L(Left subtlee)和R(Right subtree)又可解释为根 根的左子树和根的右子树 NLR LNR和LRN分别又称为先根遍历 中根遍历和后根遍历
遍历算法
．中序遍历的递归算法定义 若二叉树非空 则依次执行如下操作 ( )遍历左子树 ( )访问根结点 ( )遍历右子树
．先序遍历的递归算法定义 若二叉树非空 则依次执行如下操作 ( ) 访问根结点 ( ) 遍历左子树 ( ) 遍历右子树
．后序遍历得递归算法定义 若二叉树非空 则依次执行如下操作 ( )遍历左子树 ( )遍历右子树 ( )访问根结点
．中序遍历的算法实现 用二叉链表做为存储结构 中序遍历算法可描述为 void InOrder(BinTree T) { //算法里①~⑥是为了说明执行过程加入的标号 ① if(T) { // 如果二叉树非空 ② InOrder(T lchild) ③ printf( ％c T data) // 访问结点 ④ InOrder(T rchild); ⑤ } ⑥ } // InOrder
遍历序列
．遍历二叉树的执行踪迹 三种递归遍历算法的搜索路线相同（如下图虚线所示） 具体线路为 从根结点出发 逆时针沿着二叉树外缘移动 对每个结点均途径三次 最后回到根结点 ．遍历序列 （ ） 中序序列 中序遍历二叉树时 对结点的访问次序为中序序列【例】中序遍历上图所示的二叉树时 得到的中序序列为 D B A E C F （ ） 先序序列 先序遍历二叉树时 对结点的访问次序为先序序列【例】先序遍历上图所示的二叉树时 得到的先序序列为 A B D C E F （ ） 后序序列 后序遍历二叉树时 对结点的访问次序为后序序列【例】后序遍历上图所示的二叉树时 得到的后序序列为 D B E F C A 注意 （ ） 在搜索路线中 若访问结点均是第一次经过结点时进行的 则是前序遍历 若访问结点均是在第二次(或第三次)经过结点时进行的 则是中序遍历(或后序遍历) 只要将搜索路线上所有在第一次 第二次和第三次经过的结点分别列表 即可分别得到该二叉树的前序序列 中序序列和后序序列 （ ） 上述三种序列都是线性序列 有且仅有一个开始结点和一个终端结点 其余结点都有且仅有一个前趋结点和一个后继结点 为了区别于树形结构中前趋(即双亲)结点和后继(即孩子)结点的概念 对上述三种线性序列 要在某结点的前趋和后继之前冠以其遍历次序名称 【例】上图所示的二叉树中结点C 其前序前趋结点是D 前序后继结点是E 中序前趋结点是E 中序后继结点是F 后序前趋结点是F 后序后继结点是A 但是就该树的逻辑结构而言 C的前趋结点是A 后继结点是E和F
二叉链表的构造
． 基本思想 基于先序遍历的构造 即以二叉树的先序序列为输入构造 注意 先序序列中必须加入虚结点以示空指针的位置 【例】建立上图所示二叉树 其输入的先序序列是 ABD∮∮CE∮∮F∮∮
实验四 二叉树的建立和遍历
一、 实验名称
二叉树的建立和遍历。
二、实验目的
掌握二叉树的二叉链表存储结构及二叉树的建立方法。熟悉二叉树的遍历方法。
三、实验内容
（1） 根据先序遍历和中序遍历的序列，建立一棵二叉树（二叉树用二叉链表存储）。
（2） 分别以先序和中序遍历二叉树，将假设结果与给定的先序和中序遍历序列进行比较，以证明建立二叉树的正确性。
（3）给出后序遍历序列。
四、实验步骤
（1）编写一个过程，将给出的遍历序列读入一个数组；
（2）编写一个过程，根据先序和中序遍历的序列建立一棵二叉树；
（3）编写一个过程，进行先序遍历，并将结果存入一个数组。
（4）编写一个过程，进行中序遍历，并将结果存入一个数组。
（5） 编写一个函数，用以证明建立的二叉树的正确性。
（6）编写一个过程，进行后序遍历，打印后序遍历结果（前面函数为真时）；
（7）调试程序：
先序遍历序列为：ABDECF；中序遍历序列为：DBEACF；
（8）将实验心得写在程序后面，作为实验报告进行文档备份。
五、实验数据处理
将原程序和实验结果存入计算机室服务器或软盘后，交由指导老师或有关实验人员保存。
实验五 二叉树的排序
一、 实验名称
二叉树的排序。
二、实验目的
通过该实验，进一步熟悉二叉树的建立方法，掌握二叉排序树的建立和使用。
三、实验内容
（1）根据中序遍历，建立一棵二叉排序树用二叉链表存储；
（2）给出先序遍历和后序遍历序列。
四、实验步骤
（1）编写一个过程，将给定的待排序数据读入一个数组；
（2）编写一个过程，建立二叉排序树；
（3）编写一个函数，用中序遍历以证明二叉排序树的正确性；
（4）编写一个过程，进行先序遍历，并打印遍历结果（第3步必须确保正确）；
（5）编写一个过程，进行后序遍历，并打印遍历结果（第3步必须确保正确）；
（6）调试程序；
用以下数据调试程序：（58、48、77、42、64）
（7）将实验心得写在程序后面，作为实验报告进行文档备份。
五、实验数据处理
将原程序和实验结果存入计算机室服务器或软盘后，交由指导老师或有关实验人员保存。
jiuzheyang ban