树的基本概念以及java实现二叉树（二）
本文是我在学习了树后作的总结文章，接上篇文章，本节大致可以总
结为：
二叉树的遍历与实现（递归和非递归）
获取二叉树的高度和度
创建一棵二叉树
其他应用（层序遍历，复制二叉树，判断二叉树是否相等）
文章传送门：
二叉树的遍历与实现
递归实现二叉树的遍历
非递归实现二叉树的遍历
获取二叉树的高度和度
获取二叉树高度
获取二叉树的度
非递归实现二叉树的遍历
创建一棵二叉树
其他应用（层序遍历，复制二叉树，判断二叉树是否相等）
层序遍历
通过前序遍历复制一棵二叉树
判断两棵树是否相等
4 二叉树的遍历与实现 二叉树遍历：从树的根节点出发，按照某种次序依次访问二叉树中所
有的结点，使得每个结点被访问仅且一次。普遍有三种遍历方式，前序、
中序和后序；这里有两个关键词：访问和次序。有一个基本思想要注意下：
一个根结点+左右子树均可以看作一棵二叉树
4.1 递归实现二叉树的遍历
4.1.1 前序遍历
基本思想：若二叉树为空，则返回。否则从根结点开始，优先访问根
结点，再前序遍历左子树，前序遍历右子树，即根——左——右
图中按照前序遍历的访问结果为：A、B、D、G、H、C、E、I、F
使用代码递归来实现前序遍历，如下所示：
* 前序遍历（中左右）
* output:A、B、D、G、H、C、E、I、F
* @param root
public void preOrder(TreeNode root) {
if (root == null) {
System.out.println("preOrder data:" + root.getData());
preOrder(root.leftChild);
preOrder(root.rightChild);
4.1.2 中序遍历
基本思想：若二叉树为空，则返回。否则优先中序遍历左子树，再访
问根结点，再后序遍历右子树，即左——根——右
..WORD完美格式..
..专业知识编辑整理..
第六章树和二叉树（下载后用阅读版式视图或web版式可以看清）
习 题
一、选择题
1．有一“遗传”关系：设x是y的父亲，则x可以把它的属性遗传给y。表示该遗传关系最适合的数据结构为( )。
A.向量 B.树 C图 D.二叉树
2．树最合适用来表示( )。
A.有序数据元素 B元素之间具有分支层次关系的数据
C无序数据元素 D.元素之间无联系的数据
3．树B的层号表示为la，2b，3d，3e，2c，对应于下面选择的( )。
A. la (2b (3d,3e),2c) B. a(b(D,e),c)
C. a(b(d,e),c) D. a(b,d(e),c)
4.高度为h的完全二叉树至少有( )个结点，至多有( )个结点。
A. 2h_l B.h C．2h-1 D. 2h
5.在一棵完全二叉树中，若编号为f的结点存在右孩子，则右子结点的编号为( )。
A. 2i B. 2i-l C. 2i+l D. 2i+2
6.一棵二叉树的广义表表示为a(b(c)，d(e(，g(h))，f))，则该二叉树的高度为 ( )。
A.3 B.4 C.5 D.6
7.深度为5的二叉树至多有( )个结点。
A. 31 B. 32 C. 16 D. 10
第３４卷第２期 ２０１０年３月 江西师范大学学报（自然科学版） ＪＯＵＲＮＡＬ ＯＦ ＪＩＡＮＧＸＩ Ｎ０ＲＭＡＬ ＵＮＩＶＥＲＳＩＴＹ（ＮＡＴＵＲＡＬ ＳＣＩＥＮＣＥ） Ｖｏ１．３４ Ｎｏ．２ Ｍａｒ．２０１０
文章编号：１０００—５８６２（２０１０｝０２—０１２３—０５
树非递归遍历统一的新解法及其形式证明
化志章， 杨庆红， 揭安全
（江西师范大学计算机信息工程学院，江西南昌３３００２２）
摘要：提出树遍历统一的新解法，使其非递归算法像递归算法一样简单．首先以后序遍历为例，基于结点 状态标记和遍历规则提取，从遍历定义导出遍历的递推公式，由此机械获得非递归算法和循环不变式，并 用形式化方法证明其正确性．之后按不同遍历定义变换公式参数，获得二叉树前序、中序和Ｋ叉树前序、 后序的递推公式，所得算法比传统算法更简洁直观，表明本解法的有效性和通用性． 关键词：树遍历；非递归算法；循环不变式
中图法分类号：ＴＰ ３１１．１ 文献标识码：Ａ
树遍历，就是按某种规则（如前序、后序等）依次枚举出树中的所有结点．传统二叉树遍历算法设计有一
明显缺陷：编写递归算法极为容易，设计非递归算法却十分困难；且设计难度也不尽相同，前序、中序相对简
单，后序则较为困难．算法设计思想也难以适用于Ｋ叉树的前序和后序遍历．纵观国内外经典教材＿ｌ ｊ和 Ｋｎｕｔｈ的巨著《１ｈｅ Ａｒｔ ｏｆ Ｃｏｍｐｕｔｅｒ Ｐｒｏｇｒａｍｍｉｎｇ｝￣ ，该缺陷几十年来始终存在．遍历是二叉树最基本的操作之
一，建树、搜索、比较、穿线、结点计数等操作都可基于遍历实现．二叉树也是一种典型的递归数据结构．解决
上述缺陷，不仅方便二叉树相关算法的开发与应用，而且对一系列基于递归数据结构的算法开发十分有益．
１相关工作
多位学者试图借助形式化技术解决这一问题，在揭示算法如何产生的同时，证明算法正确．文献［４］用谓
词演算技术形式推导二叉树中序遍历非递归算法，通过分析遍历展开过程，猜出其中蕴含的不变式以及所
C++⼆叉树的先序，中序，后序遍历
三种遍历⽅式都分为递归与⾮递归的⽅式。三种遍历⽅式的递归思想相同。后序遍历⾮递归⽅法分为两种，具体见代码。
构造⽅式：
1 #include
2 #include
3 using namespace std;
4
5 typedef struct BiTNode{
6 char data;
7 int lvisited,rvisited;//左、右孩⼦是否访问过，1表⽰已访问（此项只在后序⾮递归2算法中需要）
8 struct BiTNode *lchild,*rchild;
9 }BiTNode,*BiTree;
10
11 void InitBiTree(BiTree &T)//构造空⼆叉树
12 {
13 T=NULL;
14 }
15 void CreateBiTree(BiTree &T)//⽣成⼆叉树
16 {
17 char ch;
18 cin>>ch;
19 if(ch=='0')//0代表空
20 T=NULL;
21 else
22 {
23 T=(BiTree)malloc(sizeof(BiTNode));//⽣成根结点
24 if(!T)
25 {
26 cout<<"⽣成结点错误！"<
27 return;
28 }
29 T->data=ch;
30 T->lvisited=0;
31 T->rvisited=0;
32 CreateBiTree(T->lchild);
33 CreateBiTree(T->rchild);
34 }
35 }
三种遍历⽅式代码：
1 void PreOrder(BiTree T)//先序递归遍历
2 {
3 if(T!=NULL)
4 {
5 cout 6 PreOrder(T->lchild); 7 PreOrder(T->rchild); 8 } 9 } 10 void SqlPreOrder(BiTree T)//先序⾮递归遍历
