计算机网络实验一层二叉树

㈠ 将一棵有100个结点的完全二叉树从根这一层开始，每一层上从左到右依次对结点进行编号，根结点的编号为1

编号为49的结点的左孩子编号为98，公式是2i，不是2i+1。

举个简单的例子就可以看出来的，比如7个节点时（也就是三层时），编号为1的左子树编号是2，编号2的左子树是4，编号3的左子树编号为6，以此就可以看出来。

一棵深度为k的有n个结点的二叉树，对树中的结点按从上至下、从左到右的顺序进行编号，如果编号为i（1≤i≤n）的结点与满二叉树中编号为i的结点在二叉树中的位置相同。

算法思路

判断一棵树是否旦蔽是完全二叉败敏树的思路

如果树为空，则直接返回错

如果树不为空：层序遍历二叉树

如果一个结点左右孩子都不为空，则pop该节点，将其左右孩子入队列；

如果遇到一个结点，左孩子为空，右孩子不为空，则该树一定不是完全二叉树；

以上内容参考：网络-完察迟枝全二叉树

㈡ 假设一棵二叉树的层次次序（按层次递增顺序排列，同 一层次自左向右）为ABECFGDHI,中序序列为BCDAFEHIG。

【答案】按液丛层次遍历，第羡让一个结点（若树不空）为根，该
结点在中序序列中把序列分成左右两部分：左子树和右子
树。若左子树不空，层次序列中第二个结点为左子树的根
；若右子树为空，则层次序列中第三个结点为右子树的根
。对右子树也作类似的分析。层次序列的特点是，从左到
右每个结点或是当前情况下子树的根或是叶子闹派樱。

㈢ 在计算机程序中，二叉树是一种表示数据结构的方法．如图，-层二叉树的结点总数为1；二层二叉树的结点的总

根消圆据题意分析可得：第掘桥罩n层的二叉树判闹的结点总数为2ⁿ-1；故七层二叉树的结点总数为2⁷-1=127．

㈣ 请教各位一下

二叉树T是有限个结点的集合，它或者是空集，或者由一个根结点u以及分别称为左子树和右子树的两棵互不相交的二叉树u(1)和u(2)组成。若用n,n1和n2分别表示T，u(1)和u(2)的结点数，则有n=1+n1+n2 。u(1)和u(2)有时分别称为T的第一和第二子树。

因此，二叉树的根可以有空的左子树或空的右子树，或者左、右子树均为空。

二叉树有5种基本形态，如图1所示。

图1 二叉树的5种基本形态(其中□表示空)

在二叉树中，每个结点至多有两个儿子，并且有左、右之分。因此任一结点的儿子不外4种情况：没有儿子；只有一个左儿子；只有一个右儿子；有一个左儿子并且有一个右儿子。

--------------------------------------------------------------------------------

注意：二叉树与树和有序树的区别

--------------------------------------------------------------------------------

二叉树与度数不超过2的树不同，与度数不超过2的有序树也不同。在有序树中，虽然一个结点的儿子之间是有左右次序的，但若该结点只有一个儿子时，就无须区分其左右次序。而在二叉树中，即使是一个儿子也有左右之分。例如图2中(a)和(b)是两棵不同的二叉树。虽然它们与图3中的普通树(作为无序树或有序树)很相似，但它们却不能等同于这棵普通的树。若将这3棵树均看作是有序树，则它们就是相同的了。

图2 两棵不同的二叉树

图3 一棵普通的树

由此可见，尽管二叉树与树有许多相似之处，但二叉树不是树的特殊情形。

二叉树的数学性质
二叉树具有以下的重要性质：

高度为h≥0的二叉树至少有h+1个结点；
高度不超过h(≥0)的二叉树至多有2h+1-1个结点；
含有n≥1个结点的二叉树的高度至多为n-1；
含有n≥1个结点的二叉树的高度至少为logn，因此其高度为Ω(logn)。
具有n个结点的不同形态的二叉树的数目在一些涉及二叉树的平均情况复杂性分析中是很有用的。设Bn是含有n个结点的不同二叉树的数目。由于二叉树是递归地定义的，所以我们很自然地得到关于Bn的下面的递归方程：
(1)

即一棵具有n>1个结点的二叉树可以看成是由一个根结点、一棵具有i个结点的左子树和一棵具有n-i-1个结点的右子树所组成。

(1)式的解是

(2)

即所谓的Catalan数。因此，当n=3时,B3=5。于是，含有3个结点的不同的二叉树有5棵，如图4所示。

图4 含有3个结点的不同二叉树

特殊形态的二叉树
满二叉树和近似满二叉树是二叉树的两种特殊情形。

一棵高度为h≥0且有2h+1-1个结点的二叉树称为满二叉树。

若一棵二叉树至多只有最下面的两层结点的度数小于2，并且最下面一念慧层结点都集中在该层的核凳最左边，则称这种二叉树为近似满二叉树(有时也称为完全二叉树)。

(a) 满二叉树

(b) 近似满二叉树

(c) 非近似满二叉树

图5 特殊形态的二叉树

例如图5(a)是一棵高度为3的满二叉树。满二叉树的特点是每一层上的结点数都达到最大值，即对给定的高度，它是具有最多结点数的二叉树。满二叉树中不存在度仔氏答数为1的结点，每个分枝结点均有两棵高度相同的子树，且叶结点都在最下面一层上。图5(b)是一棵近似满二叉树。显然满二叉树是近似满二叉树，但近似满二叉树不一定是满二叉树。在满二叉树的最下层上，从最右结点开始连续往左删去若干个结点后得到的二叉树是一棵近似满二叉树。因此，在近似满二叉树中，若某个结点没有左儿子，则它一定没有右儿子，即该结点是一个叶结点。图5(c)中，结点F没有左儿子而有右儿子L，故它不是一棵近似满二叉树。

二叉树的操作
二叉树的常用操作与树的常用操作相似。

运算 含义
Parent(v,T) 这是一个求父结点的函数，函数值为树T中结点v的父亲。当v是根结点时，函数值为∧，表示结点v没有父结点。
Left_Child(v,T) 这是一个求左儿子结点的函数。函数值为树T中结点v的左儿子。当结点v没有左儿子时，函数值为∧。
Right_Child(v,T) 这是一个求右儿子结点的函数。函数值为树T中结点v的右儿子。当结点v没有右儿子时，函数值为∧。
Create(x,Left,Right,T) 这是一个建树过程。该函数生成一棵新的二叉树T，T的根结点v的标号为x，v的左右儿子分别为Left和Right。
Label(v,T) 这时一个求标号的函数，函数值就是结点v的标号。
Root(T) 这是一个求树根的函数，函数值为树T的根结点。当T是空树时，函数值为∧。
MakeNull(T) 这是一个过程，它使T成为一棵空树。

二叉树的实现
我们已经看到，虽然二叉树与树很相似，但它却不是树的特殊情形。在许多情况下，使用二叉树具有结构简单，操作方便的优点。另外我们也看到，在树的左儿子右兄弟表示法中，实际上已将一棵一般的树转化为一棵二叉树。在更一般的情形，我们还可以将果园或森林转化为一棵等价的二叉树。下面我们来讨论几种二叉树的表示方法。

二叉树的顺序存储结构
此结构是将二叉树的所有结点，按照一定的次序，存储到一片连续的存储单元中。因此，必须将结点排成一个适当的线性序列，使得结点在这个序列中的相应位置能反映出结点之间的逻辑关系。这种结构特别适用于近似满二叉树。

在一棵具有n个结点的近似满二叉树中，我们从树根起，自上层到下层，逐层从左到右给所有结点编号，就能得到一个足以反映整个二叉树结构的线性序列，如图6所示。其中每个结点的编号就作为结点的名称。

图6 近似满二叉树的结点编号

因此，我们可以对树的类型作如下说明：

TPosition=integer;

TreeType=record

NodeCount:integer;

NodeList:array [1..MaxNodeCount] of LabelType;

end;

将数组下标作为结点名称(编号)，就可将二叉树中所有结点的标号存储在一维数组中。例如，图6中的二叉树的顺序存储结构如图7所示。

图7 近似满二叉树的顺序存储结构

在二叉树的这种表示方式下，各结点之间的逻辑关系是隐含表示的。近似满二叉树中，除最下面一层外，各层都充满了结点。可能除最底层外，每一层的结点个数恰好是上一层结点个数的2倍。因此，从一个结点的编号就可推知其父亲，左、右儿子，和兄弟等结点的编号。例如，对于结点i我们有：

仅当i=1时，结点i为根结点；

当i>1时，结点i的父结点为i/2；

结点i的左儿子结点为2i；

结点i的右儿子结点为2i+1；

当i为奇数且不为1时，结点i的左兄弟结点为i-1；

当i为偶数时，结点i的右兄弟结点为i+1。

由上述关系可知，近似满二叉树中结点的层次关系足以反映结点之间的逻辑关系。因此，对近似满二叉树而言，顺序存储结构既简单又节省存储空间。

对于一般的二叉树，采用顺序存储时，为了能用结点在数组中的位置来表示结点之间的逻辑关系，也必须按近似满二叉树的形式来存储树中的结点。显然，这将造成存储空间的浪费。在最坏情况下，一个只有k个结点的右单枝树却需要2k-1个结点的存储空间。例如，只有3个结点的右单枝树，如图8(a)所示，添上一些实际不存在的虚结点后，成为一棵近似满二叉树，相应的顺序存储结构如图8(b)所示。

图8 一般二叉树的顺序存储结构

下面我们就用这种顺序存储结构来实现二叉树的常用操作。在这种表示法中，整数0表示空结点∧。对于非近似满二叉树，我们将其补为近似满二叉树，并规定一个特殊的标号&，用来表示补充的结点，&要根据标号的具体类型来确定。

顺序存储结构实现ADT二叉树的操作

函数 Parent(v,T);

功能

这是一个求父结点的函数，函数值为树T中结点v的父亲。当v是根结点时，函数值为∧，表示结点v没有父结点。

实现

Function Parent(v:TPosition;var T:TreeType):TPosition;

begin

return(v div 2);

end;

说明

根据这种表示法，我们知道，当i>1时，结点i的父结点为i/2。

复杂性

显然为O(1)。

函数 Left_Child(v,T);

功能

这是一个求左儿子结点的函数。函数值为树T中结点v的左儿子。当结点v没有左儿子时，函数值为∧。

实现

Function Left_Child(v:TPosition;var T:TreeType):TPosition;

begin

if (2*v>T.NodeCount)or(T.NodeList[2*v]=&) then return(0)

else return(2*v);

end;

说明

如果结点v的左儿子存在，则其下标为2*v。

复杂性

显然为O(1)。

函数 Right_Child(v,T);

功能

这是一个求右儿子结点的函数。函数值为树T中结点v的右儿子。当结点v没有右儿子时，函数值为∧。

实现

Procere Right_Child(v:TPosition;var T:TreeType):TPosition;

begin

if (2*v+1>T.NodeCount)or(T.NodeList[2*v+1]=&) then return(0)

else return(2*v+1);

end;

说明

如果结点v的左儿子存在，则其下标为2*v+1。

复杂性

显然为O(1)。

函数 Create(x,Left,Right,T);

功能

这是一个建树过程。该函数生成一棵新的二叉树T，T的根结点标号为x，左右儿子分别为Left和Right。

实现

Procere Create(x:LabelType;var Left,Right,T:TreeType);

begin

T.NodeList[1]:=x;

T.NodeCount:=Left.NodeCount+Right.NodeCount+1;

h_left:=cal(Left.NodeCount);

h_right:=cal(Right.NodeCount);

if h_left>h_Right then h:=h_left else h:=h_right;

for i:=Left.NodeCount+1 to (1 shl (h+1))-1 do Left.NodeList[i]:=&；

Left.NodeCount:=(1 shl (h+1))-1;

if h_right<h then

begin

for i:=Right.NodeCount+1 to (1 shl h)-1 do Right.NodeList[i]:=&；

Right.NodeCount:=(1 shl h)-1;

end;

{=======

对于Left中编号为i的结点v，它在新树T中的编号为2h +i，其中h=log2(i+1)-1 ；对于Right中编号为i的结点v，它在新树T中的编号为2h+1+i，其中h=log2(i+1)-1 。

=======}

for i:=1 to Left.NodeCount do

T.NodeList[(1 shl cal(i))+i]:=Left.NodeList[i];

for i:=1 to Right.NodeCount do

T.NodeList[(1 shl (cal(i)+1))+i]:=Right.NodeList[i];

end;

其中cal(i)用来计算含有i个结点的近似满二叉树T的高度，cal(i)=log2(i+1)-1,可以实现如下：

Function cal(i:integer;):integer;

var

x:real;

begin

x:=log2(i+1)-1;

if x=int(x) then return(x) else return(int(x)+1);

end;

其中log2(n)计算实数n以2为底的对数。

说明

在顺序存储的结构下，建立一棵新的二叉树的过程比较复杂。我们首先给出以下几个命题：

命题一

一棵高度为h的满二叉树有2h+1-1个结点。

证明：

满二叉树的第i层有2i个结点，i=0,1,2,...,h(树根为第0层)，因此高度为h的满二叉树有20+21+..+2h = 2h+1-1个结点。

推论一

我们从树根起，自上层到下层，逐层从左到右给二叉树的所有结点编号，如图6所示，则近似满二叉树的第h层的从左到右第k个结点的编号为2h+k-1。

证明：

由于是近似满二叉树，所以第0层到第h-1层是满二叉树，根据命题一知道共有2h-1个结点，因此第h层的从左到右第1个结点的编号为2h-1+1，第h层的从左到右第k个结点的编号为2h-1+k。

推论二

一棵有n个结点的近似满二叉树，高度为log2(n+1)-1 ,其中 是天花板符号， x表示大于等于x的最小整数。

证明：

有n个结点的近似满二叉树，若其高度为h，则满足2h-1<n≤2h+1-1,化简得 log2(n+1)-1 ≤ h < [log2(n+1)-1]+1，即h=log2(n+1)-1。

推论三

在近似满二叉树T中，设编号为i的结点处于T的第h层从左到右第k个位置上，则h=log2(i+1)-1 ，k=i-(2h-1)。

证明：

我们先不考虑编号大于i的结点，则前i个结点构成一棵近似满二叉树，根据推论二知其层数为h=log2(i+1)-1 ，又因为第0层到第h-1层是满二叉树，根据命题一知道共有2h-1个结点，所以编号为i的结点处于第h层的第k=i-(2h-1)个位置上。

我们用T(h,k)表示树T的第h层的第k个结点，则有下列命题：

命题二

Left(h,k)=T(h+1,k)，Right(h,k)=T(h+1,k+2h)，其中Left和Right分别是树T的根结点的左右子树。

证明：

显然。

我们用N(v,T)表示结点v在生成的新树T中的编号，则有下列命题：

命题三

对于Left中编号为i的结点v，N(v,T)=2h +i，其中h=log2(i+1)-1 ；对于Right中编号为i的结点v，N(v,T)=2h+1+i，其中h=log2(i+1)-1 。

证明：

㈤ 计算二叉树指定结点p的层数(设树根为第一层)

int level(struct node *t,struct node *p) {
return t ? _level(t, p, 1) : 0;
}

int __level(struct node *cur, struct node *goal, int depth) {
if (cur == NULL) return 0;
if (cur == goal) return depth;
int l = __level(cur->left, goal, depth + 1);
if (l > 0) return l;
int r = __level(cur->right, goal, depth + 1);
if (r > 0) return r;
return -1
}

㈥ 二叉树有哪些基本特性

1、节点:

二叉树中每个元素都称为节点。

2、度:

二叉树的度代表某个节点的孩子或者说直接后继的个数，1度是只有一个孩子或者说单子树。2度是两个孩子或者说左右子树都有的二叉树最大度为2。

3、叶子:

叶子是叶子节点的简称。叶子也就是leaf指在网络结构中某些计算机，它们从比较靠近中心的计算机处接收信号，而不把信号传送至较远的计算机。叶子节点就是树中最底段的节点，叶子节点没有子节点。格式化叶子节点的结构比中间节点的结构稍微复杂一点。为了能够在一个格式化叶子节点中保存多个条目。

(6)计算机网络实验一层二叉树扩展阅读

二叉树：

1、在计算机科学中，二叉树是每个结点最多有两个子乱派亩树的树结构。通常子树被称作“左子树”（left subtree）和“右子树”（right subtree）。二叉树常被用于实现二叉查找树和二叉堆。

2、一棵深度为k，且有2^k-1个节点的二叉树，称为满二叉树。这种树的特点是每一层上的节点数都是最大节点数。而在一棵二叉树中，除最后一层外，若其余层都是满的，并羡帆且最后一层或者是满的，或者是在右边缺少连续若干节点，则此二叉树为完全二叉树。

具有n个节点的完全二叉树的深度为floor(log2n)+1。深度为k的完全二叉树，至少有2k-1个节点，至多有2k-1个哗森节点。

㈦ 什么是二叉树，举一个二叉树的例子

树是一种重要的非线性数据结构，直观地看，它是数据元素（在树中称为结点）按分支关系组织起来的结构，很象自然界中的树那样。树结构拍核在客观世界中广泛存在，如人类社会的族谱和各种社会组织机构都可用树形象表示。树在计算机领域中也得到广泛应用，如在编译源程序如下时，可用树表示源源程序如下的语法结构。又如在数据库系统中，树型结构也是信息的重要组织形式之一。一切具有层次关系的问题都可用树来描述。树结构的特点是：它的每一个结点都可以有不止一个直接后继，除根结点外的所有结点都有且只有一个直接前趋。以下具体地给出树的定义及树的数据结构表示。树是由一个或多个结点组成的有限集合，其中：⒉剩下的结点被分成n>=0个互不相交的集合T1、T2、......Tn，而且， 这些集合的每一个又都是树。树T1、T2、......Tn被称作根的子树(Subtree)。1.树的度——也即是宽度，简单地说，就是结点的分支数。以组成该树各结点中最大的度作为该树的度，如上图的树，其度为3;树中度为零的结点称为叶结点或终端结点。树中度不为零的结点称为分枝结点或非终端结点。除根结点外的分枝结点统称为内部结点。2.树的深度——组成该树各结点的最大层次，如上图，其深度为4；3.森林——指若干棵互不相交的树的集合，如上图，去掉根结点A，其原来的二棵子树T1、T2、T3的集合{T1,T2,T3}就为森林；4.有序树——指树中同层结点从左到右有次序排袭凳掘列，它们之间的次序不能互换，这样的树称为有序树，否则称为无序树。树的表示方法有许多，常用的方法是用括号：先将根结点放入一对圆括号中，然后把它的子树由左至右的顺序放入括号中，而对子树也采用同样的方法处理；同层子树与它的根结点用圆括号括起来，同层子树之间用逗号隔开，最后用闭括号括起来。如上图可写成如下形式：二叉树也是递归定义的，其结点有左右子树之分，逻辑上二叉树有五种基本形态：注意：尽管二叉树与树有许多相似之处，但二叉树不是树的特殊情形。(1)完全二叉树——只有最下面的两层结点度小于2，并且最下面一层的结点都集中在该层最左边的若干位置的二叉树；(2)满二叉树——除了叶结点外每一个结点都有左右子女且叶结点都处在最底层的二叉树,。(1) 在二叉树中，粗渗第i层的结点总数不超过2^(i-1)；(2) 深度为h的二叉树最多有2h-1个结点(h>=1)，最少有h个结点；(3) 对于任意一棵二叉树，如果其叶结点数为N0，而度数为2的结点总数为N2，(5)有N个结点的完全二叉树各结点如果用顺序方式存储，则结点之间有如下关系：若I为结点编号则 如果I<>1，则其父结点的编号为I/2；如果2*I<=N，则其左儿子（即左子树的根结点）的编号为2*I；若2*I>N，则无左儿子；如果2*I+1<=N，则其右儿子的结点编号为2*I+1；若2*I+1>N，则无右儿子。(2)链表存储方式，如：5.普通树转换成二叉树：凡是兄弟就用线连起来，然后去掉父亲到儿子的连线，只留下父母到其第一个子女的连线。二叉树很象一株倒悬着的树，从树根到大分枝、小分枝、直到叶子把数据联系起来，这种数据结构就叫做树结构，简称树。树中每个分叉点称为结点，起始结点称为树根，任意两个结点间的连接关系称为树枝，结点下面不再有分枝称为树叶。结点的前趋结点称为该结点的"双亲"，结点的后趋结点称为该结点的"子女"或"孩子"，同一结点的"子女"之间互称"兄弟"。二、二叉树：二叉树是一种十分重要的树型结构。它的特点是，树中的每个结点最多只有两棵子树，即树中任何结点的度数不得大于2。二叉树的子树有左右之分，而且，子树的左右次序是重要的，即使在只有一棵子树的情况下，也应分清是左子树还是右子树。定义：二叉树是结点的有限集合，这个集合或是空的，或是由一个根结点和两棵互不相交的称之为左子树和右子树的二叉树组成。对满二叉树，从第一层的结点(即根)开始，由下而上，由左及右，按顺序结点编号，便得到满二叉树的一个顺序表示。据此编号，完全二叉树定义如下：一棵具有n个结点，深度为K的二叉树，当且仅当所有结点对应于深度为K的满二叉树中编号由1至n的那些结点时，该二叉树便是完全二叉树。图4是一棵完全二叉树。遍历是对树的一种最基本的运算，所谓遍历二叉树，就是按一定的规则和顺序走遍二叉树的所有结点，使每一个结点都被访问一次，而且只被访问一次。由于二叉树是非线性结构，因此，树的遍历实质上是将二叉树的各个结点转换成为一个线性序列来表示。设L、D、R分别表示遍历左子树、访问根结点和遍历右子树， 则对一棵二叉树的遍历有三种情况：DLR（称为先根次序遍历），LDR（称为中根次序遍历），LRD （称为后根次序遍历）。

㈧ 求二叉树每一层的结点数 C++，代码加解释，求大神帮助

假设二叉树不会大于100层，可以采用如下算法实现。如果层次不限定建议使用链表来存储。
主函数直接调用TraversalTree(&root, 0)即可其中root为二叉树的根空蠢节点对象。
调用完后nMax表示最大层数，而currentFloor记录每层的结点个数。
const int MAX 100
int nMax = 0;
int nNumArray[MAX] = {0};
void TraversalTree(TreeNode *root, int currentFloor)
{
if (null != root)
{
nNumArray[currentFloor]++; //子二叉树的根结点存在因此本层增加结点数加1
if(nMax < currentFloor)
{
nMax = currentFloor + 1; //记录当前树的最大棚激层次,currentFloor 从0开始，因此需链亏袜要加1
}
}
else
{
return;
}
TraversalTree(root->left,currentFloor+1); //遍历左子数
TraversalTree(root->right,currentFloor+1);//遍历右子数
}

㈨ 用VB编写 二叉树的建立与遍历、二叉树的排序

实验四 二叉树的建立和团空遍历
一、 实验名称
二叉树的建立和遍历。
二、实验目的
掌握二叉树的二叉链表存储结构及二叉树的建立方法。熟悉二叉树的遍历方法。
三、实验内容
（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

㈩ 二叉树相关算法的实验验证 [ 实验目的] 验证二叉树的链接存储结构及其上的基本操作。（c++）

浅谈数据结构-二叉树

二叉树是树的特殊一种，具有如下特点：1、每个结点最多有两颗子树，结点的度最大为2。2、左子树和右子树是有顺序的，次序不能颠倒。3、即使某结点只有一个子树，也要区分左右子树。

一、特殊的二叉树及特点

1、斜树

所有的结点都只有左子树（左斜树），或者只有右子树（右斜树）。这就是斜树，应用较少

基本思想：先后序遍历左子树，然后再后序遍历右子树，最后再访问根结点即左—右—根。

图中后序遍历结果是：4，8，7，5，2，6，3，1。

后序递归遍历代码实现，如下所示。

后序遍历的非递归实现是三种遍历方式中最难的一种。因为在后序遍历中，要保证左孩子和右孩子都已被访问，并且左孩子在右孩子之前访问才能访问根结点，这就为流程控制带来了难题。下面介绍一种思路。

要保证根结点在左孩子和右孩子访问之后才能访问，因此对于任一结点p，先将其入栈。若p不存在左孩子和右孩子，则可以直接访问它，或者p存在左孩子或右孩子，但是其左孩子和右孩子都已经被访问过了，则同样可以直接访问该结点。若非上述两种情况，则将p的右孩子和左孩子依次入栈，这样就保证了每次取栈顶元素的时候，左孩子在右孩子之前别访问，左孩子和右孩子都在根结点前面被访问。

五、二叉树的建立

其实而二叉树的建立就是二叉树的遍历，只不过将输入内容改为建立结点而已，比如，利用前序遍历建立二叉树