① 求一棵二叉树的结点数，算法如下，先、中、后根次序遍历均可。

public int size() //返回二叉树的结点数

{ return size(this.root); }

private int size(BinaryNode p) //返回以p结点为根子树的结点数，先根次序遍历

{

if (p==null) return 0;

return 1+size(p.left)+ size(p.right); }

② 一棵二叉树的高度=其较高的一棵子树高度+1。因此求二叉树高度必须采用后根次序遍历算法如下，首先分别计算出左、右子树的高度，再计算以当前结点为根的子树高度。

public int height() //返回二叉树的高度

{ return height(this.root); }

private int height(BinaryNode p) //返回以p结点为根的子树高度，后根次序遍历

{

if (p==null) return 0;

int lh = height(p.left); //返回左子树的高度

int rh = height(p.right); //返回右子树的高度

return (lh>=rh) ? lh+1 : rh+1; //当前子树高度=较高子树高度+1

}

【实验6-1】BinaryTree二叉树类，递归方法参数与返回值问题讨论。

6-1 如果size(p)方法声明如下，有什么错误？

- 53 -

int size(BinaryNode p) //返回以p结点为根子树的结点数

{

static int n=0; if (p!=null) { n++;

size(p.left); size(p.right); } }

【答】存在错误：① Java语言方法体中的局部变量不能声明为static。

② 如果用局部变量n计数，每次n=0，再n++，n=1，无法实现计数，并且结果无法返回给调用者。

6-2 如果BinaryTree类的构造方法声明如下，有什么错误？为什么？

public BinaryTree(T[] prelist) //构造二叉树，prelist数组指定二叉树标明空子树的先根遍历序列

{

int i=0;

this.root = create(prelist,0); }

//以从i开始的标明空子树的先根序列，创建一棵以prelist[i]为根的子树，返回根结点，递归方法

private BinaryNode create(T[] prelist,int &i) {

BinaryNode p = null; if (i

{ T elem=prelist[i++];

if (elem!=null) //不能elem!=\∧\，因为T不一定是String

{ p = new BinaryNode(elem); //创建叶子结点

p.left = create(prelist,i); //创建p的左子树，递归调用

- 54 -

p.right = create(prelist,i); //创建p的右子树，递归调用

} }

return p; }

【答】存在错误：Java语言，基本数据类型作为方法的参数只能是数值参数，不能使用&声明为引用参数。

【思考题6-3】 实现BinaryTree二叉树类的拷贝构造方法。 【答】

public BinaryTree(BinaryTree bitree) //深拷贝，由已知的bitree构造二叉树

{ this.root = copy(bitree.root); }

//复制以p根的子二叉树，返回新建子树的根结点。先根次序遍历和构造算法

private BinaryNode copy(BinaryNode p) {

if (p==null) return null;

BinaryNode q = new BinaryNode(p.data);

q.left = copy(p.left); //复制左子树，递归调用

q.right = copy(p.right); //复制右子树，递归调用

return q; //返回建立子树的根结点

}

其中，copy(p)采用遍历算法和构造算法，在以先根次序遍历参数p表示的二叉树时，创建另一棵二叉树，结点值相同，且子树结构相同；方法返回创建子树的根结点q，逐层返回，建立父母与孩子结点的链接关系。

- 55 -

6.3 线索二叉树

1. 中根次序遍历

中序线索二叉树类ThreadBinaryTree声明以下成员方法，按中根次序遍历。算法首先寻找第一个访问结点，即根的左子树上最左边的一个后代结点，此后，反复求得当前访问结点的后继结点，即可遍历整棵二叉树。

public void inorder() //中根次序遍历中序线索二叉树，非递归算法

{

ThreadNode p=this.root;

while (p!=null && !p.ltag) //寻找根的最左边的后代结点，即第一个访问结点

p=p.left; while (p!=null)

{ System.out.print(p.data.toString()+\

p=inNext(p); //返回p在中根次序下的后继结点，声明见教材第170页

}

System.out.println(); }

2. 后根次序遍历

在中序线索二叉树中，求结点p在后根次序下前驱结点，算法描述如下，如图6.8所示。

① 若p有右孩子，则p的右孩子是p的前驱结点。如A的前驱结点是C。

② 若p没有右孩子有左孩子，则p的左孩子是p的前驱结点。如E的前驱结点是G。

③ 若p是叶子结点，则p的左兄弟是p的前驱结点。如K的前驱结点是F。

如果p没有左兄弟，则p的前驱结点是p结点作为后根次序下最先访问结点所在子树的左兄弟。沿着left线索向上遇到p的祖先结点ancestor的左孩子是p的前驱结点。H是没有左兄弟的叶子结点，例如，

- 56 -

沿着left线索（H的left和F的left）向上到达A，确定H是A的右子树上第一个访问结点，因此A的左孩子B即为H的前驱结点。

p的后根前驱BDGE沿着左线索向上寻找某个祖先FHAp的某个祖先ancestorC

K没有左兄弟的叶子结点p图6.8 中序线索二叉树，求结点p在后根次序下的前驱结点

按后根次序遍历中序线索二叉树，最后一个访问的结点是根，但第一个到达的结点是根。从根开始访问，再反复求得当前访问结点在后根次序下的前驱结点，即可遍历一棵二叉树，所得到的序列与二叉树的后根次序遍历序列正好相反。

3. 求父母结点

在中序线索二叉树中，寻找指定结点的父母结点有左右二条路径。例如，如图6.9所示，寻找结点J的父母结点，首先从J开始，沿着左孩子链经过K、L到达最左边最深的一个子孙结点M，通过M的前驱线索到达结点A，A即是J的一个祖先结点；判断该祖先A是否是J的父母结点，若不是，到达A的右孩子H，再沿着H的左孩子链逐层向下，直到找到J的父母结点I。此时，寻找经过的结点序列由以下成分组成一条三角形的环形路径：

左孩子链逐层向下→前驱线索到达祖先→祖先的右孩子→左孩子链逐层向下

也可沿着以下右孩子链和后继线索路径寻找，寻找J父母结点的路径是{O,P,Q,I}。

右孩子链逐层向下→后继线索到达祖先→祖先的左孩子→右孩子链逐层向下

对于结点J，选择上述两条路径之一即可。而对于结点B，一条路径是不够的。因为，如果先走左边，沿着左孩子链到达C，经C的前驱线索得到的祖先结点为空，此路不通；则必须再转而向右孩子链继续寻找，沿右孩子链逐层向下经过D、E直到G，经G的后继线索向上到达祖先结点A，再判断。如果选择先向右孩子链寻找，同样存在

- 57 -