二叉树定价（共4篇）
二叉树定价 篇1
摘要：在二叉树的一些应用中,常常要求在树中查找具有某种特征的节点,或者对树中全部节点逐个进行某种处理。这就提出了一个遍历二叉树的问题,即如何按某条搜索路径访问树中每个节点,使得树中每个节点都被且仅被访问一次。
关键词：二叉树,遍历二叉树,搜索路径
遍历是二叉树最重要的运算之一,是对二叉树进行其他运算的基础。
1 遍历方案
遍历(Traverse)是指沿着某条搜索路线,依次对树中每个节点均做一次且仅做一次访问。访问结点所做的操作依赖于具体的应用问题。
从二叉树的递归定义可知,一个非空的二叉树由根结点及左、右子树这三个基本部分组成。因此,在任一给定结点上,可以按某种次序执行三个操作:
1)访问根结点(D);
2)遍历该结点的左子树(L);
3)遍历该结点的右子树(R)
以上三种操作有六种执行次序:DLR、LDR、LRD、DRL、RDL、RLD。
2 遍历的命名
根据访问根结点操作发生位置命名:
DLR:先序遍历(Preorder Traverse,亦称前序遍历)访问根结点的操作发生在其左右子树之前。
LDR:中序遍历(Inorder Traverse)访问根结点的操作发生在其遍历左右子树之中(间)。
LRD:后序遍历(Postorder Traverse)访问根结点的操作发生在遍历其左右子树之后。
注意:由于访问是根据根结点D操作位置命名,所以DLR、LDR、LRD分别又称为先根遍历、中根遍历、后根遍历。
3 遍历方法
第一,如何通过给定的二叉树,写出三种遍历序列;
第二,如何通过给定的其中两中遍历序列,求出另一种序列以及画出对应的二叉树图。
下面通过具体的例题给出具体的解答:
如:假设一棵二叉树的先序序列为124536,中序序列为425136。请写出该二叉树的后序序列及其画出对应二叉树
解答过程如下:
1)由先序序列124536,可以得出根结点为1;
2)结合1),由中序序列425136,可以得出425为左子树(中序遍历),36为右子树(中序遍历);
3)结合2),根据先序序列124536,可以得出左子树245采取先序遍历根结点为2(即根结点1的左子树为2);右子树36采取先序遍历根结点为3(即根结点1的右子树为3);再由2),根据425采取中序遍历得出2的左子树为4,右子树为5;再由2,根据36采取中序遍历得出3的右子树为6
所以可以得出:1为根结点,2、3为1的左右子树,4、5为2的左右子树,6为3的右子树;
对应的二叉树如下:
4)根据二叉树图,结合后序遍历的规则LR1,L为根据L也是采取后序遍历为452,R也是采取后序遍历63,代入LR1,得出后序序列为452631。
同理,根据给出的二叉树,采取相同的方法,可以得出先序序列为124536,中序序列为425136。
参考文献
[1]安训国.数据结构[M].4版.大连:大连理工大学出版社,2009:96-101.
[2]严蔚敏.计算机视频教程系列—数据结构教程—清华严蔚敏主讲[M].北京:清华大学出版社,2007.
二叉树定价 篇2
题目：
用先序递归过程监理二叉树（存储结构：二叉链表）
输入数据按先序遍历输入，当某节点左子树或者右子树为空时，输入‘*’号，如输入abc**d**e**时，得到的二叉树为：
并用如下实力测试：
算法思路：
显然，建立一个二叉链表存储的二叉树，如果不考虑效率要求，考虑到程序的简介性，递归建立和递归遍历是一种很好的办法。
利用C++的类模板的方法实现建立，遍历，输出等二叉树操作。首先利用构造函数实现先序遍历建立二叉树，然后调用类模板中已经声明好的四种遍历函数，将遍历结果输出，检验建立好的二叉树是否为要求的二叉树。
初始化：利用构造函数建立二叉树。采用先序递归的调用方法，构造函数主体如下：
template
template
root = new BiNode
//生成一个结点 root->data=aa;
root->lchild = Creat();
//递归建立左子树
root->rchild = Creat();
//递归建立右子树
} return root;} 构造这样的函数，可以在输入时，按先序遍历顺序每次输入一个节点的数据，可以实现任意二叉树的构造。
为了检验构造的二叉树是否为预先设想的二叉树，需要遍历二叉树并进行输出。考虑到单一的输出并不能确定唯一的二叉树，因此对遍历二叉树的四种常用发方法，即先序遍历，中序遍历，后续遍历，层次遍历分别实现，通过遍历结果检验构造的二叉树是否为预先设计好的二叉树。
先序遍历：采用递归的方法建立。template
xianxu(root->lchild);//先序遍历树的左子树 xianxu(root->rchild);//先序遍历树的右子树
} 中序遍历：递归方法建立： template
if(root==NULL)return;
//如果节点为空，则返回空 else{ zhongxu(root->lchild);
//中序递归遍历root的左子树 cout<
//访问根结点
zhongxu(root->rchild);
//中序递归遍历root的右子树
}
} 后序遍历：递归方法建立： template
if(root==NULL)
return;
//如果节点为空，返回空 else{ houxu(root->lchild);
//后序递归遍历root的左子树 houxu(root->rchild);
//后序递归遍历root的右子树 cout<
//访问根节点
} } 层序遍历：采用非递归方法。利用队列的方法层序遍历二叉树。建立一个队列，在访问一个节点的时候，把它的左孩子和右孩子入队，并且将这个节点出队。当队列为空时，就完成了对二叉树的层序遍历。
template
Q[rear++] = root;// 若节点不为空，则该节点入队 while(front!= rear)
{
q = Q[front++];//只要队列不为空，则节点依次出队 cout<
if(q->lchild!= NULL)
Q[rear++] = q->lchild;
if(q->rchild!= NULL)
Q[rear++] = q->rchild;// 同时，该节点的双子入队
} } } 函数主体部分：声明一个类中的对象，调用构造函数，建立二叉树，并输出四种遍历结果，检验输出结果。
int main(){
BiTree
BiNode
cout<<“前序遍历序列为 ”< 程序结构： 主函数建立一个类模板定义构造函数，析构函数，以及成员函数声明类中的一个对象调用构造函数，构造一颗二叉树层序遍历二叉树后序遍历二叉树中序遍历二叉树前序遍历二叉树获取该二叉树的根节点将结果输出，人工检验 源代码： #include template { T data; BiNode template { public: BiTree(); //构造函数，初始化一棵二叉树 ~BiTree(void); //析构函数，释放二叉链表中各结点的存储空间 BiNode //获得指向根结点的指针 void xianxu(BiNode //前序遍历二叉树 void zhongxu(BiNode //中序遍历二叉树 void houxu(BiNode //后序遍历二叉树 void cengxu(BiNode //层序遍历二叉树 private: BiNode BiNode void Release(BiNode };template template if(aa==“*”)root = NULL; else{ root = new BiNode //生成一个结点 root->data=aa; root->lchild = Creat(); //递归建立左子树 root->rchild = Creat(); //递归建立右子树 } return root;} template template template else{ cout< xianxu(root->lchild);//先序遍历树的左子树 xianxu(root->rchild);//先序遍历树的右子树 } } template if(root==NULL)return; //如果节点为空，则返回空 else{ zhongxu(root->lchild); //中序递归遍历root的左子树 cout< //访问根结点 zhongxu(root->rchild); //中序递归遍历root的右子树 } } template if(root==NULL) return; //如果节点为空，返回空 else{ houxu(root->lchild); //后序递归遍历root的左子树 houxu(root->rchild); //后序递归遍历root的右子树 cout< //访问根节点 } } template const int MaxSize = 100;int front = 0;int rear = 0;//利用队列的方法对树进行层序遍历 BiNode BiNode else{ Q[rear++] = root;// 若节点不为空，则该节点入队 while(front!= rear) { q = Q[front++];//只要队列不为空，则节点依次出队 cout< if(q->lchild!= NULL) Q[rear++] = q->lchild; if(q->rchild!= NULL) Q[rear++] = q->rchild;// 同时，该节点的双子入队 } } } template if(root!= NULL){ Release(root->lchild); //释放左子树 Release(root->rchild); //释放右子树 delete root; } } int main(){ BiTree BiNode cout<<“前序遍历序列为 ”< cout<<“层序遍历序列为”< 通过对结果的分析，发现输出结果与建立二叉树时的输入完全符合，说明程序的运行结果是正确的。 心得体会： 1)函数递归的方法可以在相当程度上使程序简洁，避免代码的冗长复杂。2)构造函数如果带参数，在声明对象的时候应该将实参指出来。但是本题中构造函数位递归调用，初始的根节点的数据值由键盘输入，因此无法在声明对象时引入实参。所以最后选择了无参但是引用了this指针的构造函数。可见，对于构造函数的含参调用应该小心谨慎。 关键词：二叉树,遍历,满二叉树,完全二叉树 1二叉树 二叉树是由n (n≥0) 个结点组成的有限集合, n=0时称为空二叉树; n>0的二叉树由一个根结点和两棵互不相交的、分别称为左子树和右子树的子二叉树构成。可见二叉树是递归定义的。 二叉树的结点最多只有两棵子树。因此二叉树的度最多为2。二叉树的子树有左右之分, 即使只有一棵子树也要区分左子树还是右子树。 一棵高度为h的满二叉树是具有2h-1 (h≥0) 个结点的二叉树。满二叉树中每一层的结点数目都达到最大值。对满二叉树的结点按照从根结点开始、 自上层而下层、每层自左而右进行编号, 约定根结点编号为0, 则可以得到一个有序序列。对于一棵高度为h的二叉树, 如果它的每个结点都与高度为h的满二叉树序号为0~n-1的结点一一对应, 则称这棵二叉树为完全二叉树。满二叉树是完全二叉树, 而完全二叉树不一定是满二叉树。完全二叉树的第1~h-1层是满二叉树, 并且该层所有结点都必须集中在该层左边的若干位置上。如图1所示。 二叉树的遍历是按照一定规则和次序访问二叉树中的所有结点, 并且每个结点仅被访问一次。虽然二叉树是非线性结构, 但遍历二叉树访问结点的次序是线性的, 而且访问的规则和次序不止一种。二叉树的遍历规则有孩子优先和兄弟优先。 1.1孩子优先的遍历规则 假设有一棵由A、B、C 3个元素构成的二叉树: A为根结点、B为左孩子、C为右孩子, 对其遍历可得到所有的序列有: ABC、BAC、BCA、CBA、CAB、ACB。可以发现, 后3个序列分别与前3个序列的次序相反, 并且前3个序列的共同特点是, B在C之前, 即先遍历左子树还是右子树在算法设计上没有本质区别, 因此约定遍历子树的次序是先左后右, 则二叉树孩子优先的遍历有3种次序, 分别称为先根次序、中根次序和后根次序。规则如下: (1)先根次序: 访问根结点, 遍历左子树, 遍历右子树; (2)中根次序: 访问左子树, 遍历根结点, 遍历右子树; (3)后根次序: 访问左子树, 遍历右子树, 遍历根结点。 二叉树的遍历过程是递归的。如图2所示的一棵二叉树的3种遍历序 列为 : 先根次序ABDGCEFH、中根次 序DGBAECHF、后根次序GDBEHFCA。由此可知 , 先根次序遍历最先访问根结点; 后根次序遍历最后根结点; 中根次序遍历左子树上的结点在根结点之前访问, 右子树上的结点在根结点之后访问。 将一个中缀表达式 (a+b) ×c-d/e表示为一棵表达式二叉树, 两个操作数分别为运算符结点的左、右孩子结点, 运算符都是分支结点, 操作数都是叶子结点, 则按照后根次序遍历可得到后缀表达式ab+c×de/-。 1.2兄弟优先的遍历原则 二叉树的层次遍历是按照层次次序进行的。遍历过程是从根结点开始, 逐层深入, 从左至右依次访问完当前层的所有结点, 再访问下一层。如图2 (a) 所示的二叉树的层次遍历序列为: ABCDEFGH。这种遍历的特点是兄弟优先。 2二叉树的存储结构 如果将一棵完全二叉树的所有结点按照序号进行顺序存储, 根据二叉树的性质, 由结点序号i可知其父母结点、左孩子结点和右孩子结点的序号。将完全二叉树的结点按照次序进 行编号, 实际上是对完全二叉树的一次层次遍历。与非完全二叉树的层次遍历不同, 完全二叉树在按层次遍历到最后一个结点之前不会遇到空子树。如果对非完全二叉树进行顺序存储, 有以下两种办法: 其一, 仅仅存储结点, 则结点顺序存储的线性关系不能反映二叉树中的结点间的层次关系; 其二, 通过补充空子树的方式将一棵非完全二叉树变成完全二叉树的方式, 则不仅浪费存储空间, 而且线性映射关系也不明确, 也不可行。 因此, 二叉树的顺序存储结构仅适用于完全二叉树和满二叉树。二叉树主要采用链式存储结构。每个结点至少要有两条 链分别连接左、右孩子结点, 才能表达二叉树的层次关系。 采用二叉链表结构的每个结点有3个域: data数据域、left左孩子结点、right右孩子结点。一棵有n个结点的二叉树及其二叉链表存储结构如图3所示, 其中root指向二叉树的根结点。采用二叉链表存储二叉树, 设p指向其中一个结点, 则p.left、p.right分别指向其左、右孩子结点 , 每个结点到达其孩子结点所花费的时间是O (1), 这种方式只存储了结点到孩子结点的单向关系, 没有存储结点到父母结点的关系。因此, 要获得父母结点将花费较多时间, 需要从根结点开始在二叉树中进行查找。 为了解决二叉链表存储的二叉树操作效率问题, 可在二叉链表的基础上采用三叉链表结构, 即增加一条链parent连接父母结点。这样三叉链表存储了父母结点与孩子结点的双向关系。 如图4所示。 后面的二叉树操作都基于二叉链表及Java语言。二叉树的操作主要有创建二叉树、获得父母或孩子结点、 遍历、插入和删除等。描述二叉树抽象数据类型BinaryTTree接口定义如下。其中, 泛型T为结点的元素类型。 二叉树主 要由二叉 树结点类BinaryNode和二叉树 类BinaryTree共同完成。BinaryNode的定义如下。 为了方便地更改结点间的链接关系, BinaryNode类声明中成员变量的访问权限定义为public, 允许其他类访问。否则, 要提供公有方法set、getData、getLeft、getRight等, 提供给其他类调用。 二叉树类BinaryTree及其部分成员方法声明如下, 其中成员变量root指向二叉树的根结点。 3二叉树的遍历 3.1递归遍历算法 作为遍历问题的基本点, 需要在BinaryTree类中增加先根次序、中根次序、后根次序遍历二叉树的成员方法。 这3种遍历算法都是递归算法, 差别只是在于结点的访问时间不同。具体实现如下。 递归方法必须有参数, 通过不同的实际参数区别递归调用执行中的多个方法。一棵二叉树由多棵子树组成, 一个结点也是一棵子树的根。因此, 二叉树中实现遍历规则的递归方法以结点p为参数, 比如preOrder (p) 表示以先根次序遍历以p结点为根的子树, 当p指向不同结点时, 遍历不同的子树; 当p为空子树时, 递归结束。每个遍历算法都有两个重载。 3.2二叉树基本操作 基于二叉树遍历的基本操作有: 构建二叉树、求结点个数、求高度、 查找、求父母结点、替换、插入、 删除等。根据不同的应用需求, 可采用不同的次序进行遍历。 3.2.1 构造二叉树 由于二叉树是数据元素之间具有层次关系的非线性结构, 而且二叉树中每个结点的两棵子树有左右之分, 因此建立一棵二叉树必须明确两点: 结点与父母结点及孩子结点之间的层次关系; 兄弟结点之间的左右子树的次序关系。 二叉树的一种遍历序列将二叉树的非线性关系映射成一种线性关系。因此, 已知一棵二叉树可得到唯一的一组先根、中根和后根或层次遍历序列; 但是, 已知二叉树的一种遍历序列却不能唯一确定一棵二叉树。以下讨论两种能够唯一确定一棵二叉树的表示法。 3.2.1.1 先根和中根序列表示 由于先根次序或后根次序反映父母与孩子结点的层次关系, 中根次序反映兄弟结点间的左右次序。因此, 已知先根和中根两种遍历, 或中根和后根两种遍历序列, 能够唯一确定一棵二叉树。证明过程如下: 已知: 二叉树的先根和中根两种次序遍历序列, 可唯一确定一棵二叉树。 证明: 假设数组prelist和inlist分别表示一棵二叉树的先根和后根次序遍历序列。序列长度均为n。 (1)由先根次序遍历算法可知 , 该二叉树的根为prelist[0];该根结点必定在中根序列中 , 假设它在中根序列inlist中的位置为i, 则有inlist [i] =prelist [0]。 (2) 由中根次序遍历算法可知, inlist [i] 之前的结点在根的左子树上, inlist [i] 之后的结点在根的右子树上。因此, 根的左子树由i个结点组成, 子序列为: 左子树的先根序列: prelist [1] ,…,prelist [i]; 右子树的中根序列: inlist [0] ,…,inlist [i-1]。 根的右子树由n-i-1个结点组成, 子序列为: 右子树的先根序列: prelist [i+1] ,…,prelist [n-1]; 右子树的中根序列: inlist [i+1] ,…,inlist [n-1]。 (3)如此递归, 可唯一地确定一棵二叉树。 同理可证明: 中根与后根次序遍历可唯一地确定一棵二叉树; 先根和后根次序遍历序列不能唯一确定一棵二叉树; 同一个层次遍历序列不能唯一确定一棵二叉树。 上面的证明过程实际上描述了由先根和中根序列如何构造一棵二叉树的过程。在BinaryTree类中增加以下构造方法, 以先根和中根次序遍历序列构造二叉树。 3.2.1.2 标明空子树的先根序列表示 已知一棵二叉树的先根遍历序列为AB, 则能够确定A是根结点, 并且B是A的孩子结点, 但不能确定是哪个孩子, 可能是左孩子, 也可能是右孩子。这是因为先根序列只能反映父母与孩子结点之间的层次关系, 不能反映兄弟结点之间的左右次序。 如果在先根遍历次序中标明空子树, 通过空子树位置反映兄弟结点之间的左右次序, 则可唯一确定一棵二叉树。比如, 以 ^ 表示空子树, 则二叉树及其先根次序遍历序列如图2所示。 这种标明空子树的先根便利序列, 明确了二叉树中结点与父母、孩子以及兄弟结点之间的关系, 因此能够唯一地确定一棵二叉树。设prelist表示一棵已标明空子树的二叉树的先根次序遍历序列, 则构造二叉树的递归算法如下: (1)prelist [0]一定是二叉树的根 , 创建根结点。并且prelist [1] 一定是根的左孩子。 (2)如果prelist [i] 不是空子树 , 则创建一个结点 , 该结点的左孩子结点元素时prelist [i+1], 但父母与孩子之间的链接还未建立; 否则, 当前子树为空, 返回上一层结点。 (3)返回到当前结点时, 下一个元素prelist [i+1] 是当前结点的右孩子结点; 当一个结点的左、右孩子的链接都已建立, 则以当前结点为根的一棵子树已经构建好, 返回上一层结点。 (4)重复执行步骤 (2)、 (3), 直到返回根结点, 则二叉树构建完毕, root指向根结点。 在BinaryTree类中增加以下构造方法, 以标明空子树的先根序列构造一棵二叉树。 其中, prelist数组保存标明空子树的先根序列, create(prelist)方法创建一棵子树 , 子树的根值是prelist [i] 。由于create(prelist)是递归方法, 参数按照层次关系变化, 而i是数组下标, 从0递增到preorder.length-1, 因此i不能作为方法的参数, 也不能作为方法的局部变量, 只能将它作为BinaryTree类的私有成员变量, 相对于create方法是全局变量。 3.2.2 求二叉树结点个数 在BinaryTree类中增加count方法, 返回一棵二叉树或子树的结点个数。 3.2.3 求二叉树高度 一棵二叉树的高度是其较高的一棵子树的高度加1。因此求二叉树的高度必须采用后根次序遍历算法, 首先分别计算出左、右子树的高度, 再计算以当前结点为根的子树高度。在BinaryTree类中增加height方法, 返回一棵二叉树或子树的高度。 3.2.4 查找 在BinaryTree类中增加search方法, 在一棵二叉树或子树中查找关键字为key的元素, 返回首次出现的关键字为key的元素结点。若未找到, 则返回null。该方法采用先根次序遍历算法在二叉树中查找。 3.2.5 获得父母结点 在BinaryTree类中增加getParent方法 , 返回指定 结点node的父母结点。 3.2.6 插入结点 在二叉链表的二叉树中, 链的方向是单向的, 都是由结点指向其孩子结点, 没有指向其父母结点的链。与单链表的插入操作类似, 在二叉链表的二叉树中插入一个结点p, 需要修改p的父母结点的left或right域。因此 , 在二叉树中插入一个结点, 需要指定插入结点作为哪个结点的左孩子还是右孩子。在BinaryTree类中增加以下方法 : insertRoot (x) 方法插入元素x作为根结 点 , 原根结点 作为其左 孩子 ; insertChild ( p,x, leftChild) 方法插入元素x作为p结点的孩子, p结点的原左/右孩子成为新结点的左/右孩子, leftChild指定左/右孩子, 取值为true (左孩子)、false (右孩子), 返回插入结点。 3.2.7 删除一棵子树 在二叉链表的二叉树中删除一个结点p或一棵子树, 需要修改p的父母结点的left或right域。如果只删除一个结点p而不是删除一棵子树, 则需要约定如何调整子树结构的规则。换言之, 若删除一个结点p, 原先以p结点为根的子树则变成由原左子树和右子树组成的森林, 约定一种规则使这个森林组成一棵子树。这里简化, 只讨论删除一棵子树问题。 在BinaryTree类中增加以下删除一棵二叉树或子树的方法: 3.2.8 叶子结点 在BinaryTree类中增加以下方法, 判断某个结点是否为叶子结点; 计算叶子结点的数量。 3.3二叉树的层次遍历 二叉树层次遍历的特点是兄弟优先。两个兄弟结点的访问次序是先左后右, 连续访问; 它们后代结点的访问次序是: 左兄弟的所有孩子一定在右兄弟的所有孩子之前访问, 左兄弟的后代结点一定在右兄弟的同层后代结点之前访问。 在BinaryTree类中增加以下二叉树的层次遍历算法, 其中使用链式队列存储二叉树结点BinaryNode 3.4二叉树的非递归算法 课程名称 数据结构基础 实验项目名称 实验十 二叉树的基本操作 实验成绩 指导老师（签名） 日期 一.实验目的和要求 1、掌握二叉树的链式存储结构。 2、掌握在二叉链表上的二叉树操作的实现原理与方法。 3、进一步掌握递归算法的设计方法。 二.实验内容 1、按照下面二叉树二叉链表的存储表示，编写头文件binary_tree.h，实现二叉链表的定义与基本操作实现函数；编写主函数文件test4_1.cpp，验证头文件中各个操作。 二叉树二叉链表存储表示如下： struct BTreeNode { ElemType data; // 结点值域 BTreeNode *lchild , *rchild;// 定义左右孩子指针 };基本操作如下： ①void InitBTree(BTreeNode *&BT); //初始化二叉树BT ②void CreateBTree(BTreeNode *&BT, char *a); //根据字符串a所给出的广义表表示的二叉树建立二叉链表存储结构 ③int EmptyBTree(BTreeNode *BT); //检查二叉树BT是否为空，空返回1，否则返回0 ④int DepthBTree(BTreeNode *BT);//求二叉树BT的深度并返回该值 ⑤int FindBTree(BTreeNode *BT, ElemType x); //查找二叉树BT中值为x的结点，若查找成功返回1，否则返回0 ⑥void PreOrder(BTreeNode *BT);//先序遍历二叉树BT ⑦void InOrder(BTreeNode *BT);//中序遍历二叉树BT ⑧void PostOrder(BTreeNode *BT); //后序遍历发二叉树BT ⑨void PrintBTree(BTreeNode *BT); //输出二叉树BT ⑩void ClearBTree(BTreeNode *&BT); //清除二叉树BT 2、选做：实现以下说明的操作函数，要求把函数添加到头文件binary_tree.h中，并在主函数文件test4_1.cpp中添加相应语句进行测试。①void LevelOrder(BTreeNode *BT)//二叉树的层序遍历 ②int Get_Sub_Depth(BTreeNode *T , ElemType x)//求二叉树中以元素值为x的结点为根的子树的深度 3、填写实验报告，实验报告文件取名为report10.doc。 4、上传实验报告文件report10.doc、源程序文件test4_1.cpp及binary_tree.h到Ftp服务器上自己的文件夹下。 三.函数的功能说明及算法思路 （包括每个函数的功能说明，及一些重要函数的算法实现思路）函数：void InitBTree(BTreeNode *&BT)功能：初始化二叉树BT 思路：将BT指向NULL 函数：void CBTree(BTreeNode *&BT)功能：输入二叉树 思路：按先序次序输入二叉树中结点的值（一个字符）特殊字符 $ 表示空树 函数：void PBTree(BTreeNode *BT,int n)功能：横向打印二叉树 思路：先递归输出右子树，按层次输出空格和“---”控制格式，再输出当前结点值，最后递归左子树 函数：void CreateBTree(BTreeNode *&BT, char *a)功能：根据字符串a所给出的广义表表示的二叉树建立二叉链表存储结构 思路：根据广义表表示的”(”,”)”和”,”等字符来构建二叉树，用栈S来存储根结点指针，用p来接收当前结点值数据并链接为栈顶元素的左/右孩子 函数：int EmptyBTree(BTreeNode *BT)功能：检查二叉树BT是否为空，空返回1，否则返回0 思路：返回判断BT是否指向NULL 函数：int DepthBTree(BTreeNode *BT)功能：求二叉树BT的深度并返回该值 思路：若一棵二叉树为空，则它的深度为0，否则它的深度等于左子树和右子树中的最大深度加1 函数：int FindBTree(BTreeNode *BT, ElemType x)功能：查找二叉树BT中值为x的结点，若查找成功返回1，否则返回0 思路：类似于前序遍历，若空树则返回0。若根结点值等于查找值x则返回1，否则先调用函数本身查找左子树，还未找到则再查找右子树，所有操作完成均为找到，则返回0 函数：void PreOrder(BTreeNode *BT)功能：先序遍历二叉树BT 思路：使用“根左右”的顺序遍历二叉树 函数：void InOrder(BTreeNode *BT)功能：中序遍历二叉树BT 思路：使用“左根右”的顺序遍历二叉树 函数：void PostOrder(BTreeNode *BT) 功能：后序遍历二叉树BT 思路：使用“左右根”的顺序遍历二叉树 函数：void PrintBTree(BTreeNode *BT) 功能：输出二叉树BT 思路：按照广义表表示方法输出二叉树（与输入时相同） 函数：void ClearBTree(BTreeNode *&BT) 功能：清除二叉树BT 思路：按照先子树后根结点的顺序删除二叉树 函数（选作）：void LevelOrder(BTreeNode *BT)功能：二叉树的层序遍历 思路：初始化一个空队列，若二叉树为空，则空操作；否则，树根指针入队列。当队列非空时循环：出队首元素，并输出该元素（指针）所指结点的值；且若该结点存在左右孩子，则左右孩子指针进队列。输出结果就是层序遍历序列 函数（选作）：求二叉树中以元素值为x的结点为根的子树的深度 功能：int Get_Sub_Depth(BTreeNode *T , ElemType x)思路：在FindBTree函数的基础上修改，将找到结点时的返回值改为调用DepthBTree求出以该结点为根结点的子树深度即可 四.实验结果与分析 （包括运行结果截图、结果分析等） 测试数据：a(b(c),d(e(f,g),h(,i)))，abc$$$def$$g$$h$i$$ 结果分析：针对该二叉树，程序输出深度为4，正确；查找值f能够找到，正确；先序遍历结果为a b c d e f g h i，正确；中序遍历结果为c b a f e g d h i，正确；后续遍历结果为c b f g e I h d a，正确；输出二叉树的结果与输入一致，正确；使用先序输入二叉树和横向输出部分正确。选作部分，层序遍历结果为a b d c e h f g i，正确；以结点d为根结点的子树深度为3，正确。 五.心得体会 （记录实验感受、上机过程中遇到的困难及解决办法、遗留的问题、意见和建议等。）二叉树的遍历算法 篇3
实验10 二叉树的基本操作 篇4