[数据结构与算法]设一棵二叉树以二叉链表表示，试以成员函数形式编写有关二叉树的递归算法：

设一棵二叉树以二叉链表表示，试以成员函数形式编写有关二叉树的递归算法：

(1) 统计二叉树中度为1的结点个数。

(2) 统计二叉树中度为2的结点个数。

(3) 统计二叉树中度为0（叶结点）的结点个数。

(4) 统计二叉树的高度。

(5) 统计二叉树的宽度，即在二叉树的各层上，具有结点数最多的那一层上结点总数。???

?

(6) 从二叉树中删去所有叶结点。

(7) 计算二叉树中指定结点 *p?所在层次。

(8) 计算二叉树中各结点中的最大元素的值。

(9) 以前序次序输出一棵二叉树所有结点的数据值及结点所在层次。

?

?

【解答】

(1)666 统计二叉树中度为1的结点个数。
template <class Type> 
int?BinaryTree<Type> ::?Degrees1 ( BinTreeNode<Type>?* t ) const {
	???if ( t == NULL ) return 0;
	???if ( t->leftChild != NULL &&?t->rightChild == NULL ||
			?t->leftChild == NULL &&?t->rightChild != NULL ) 
            return?1;
	???return?Degrees1 ( t->leftChild, k ) + Degrees1 ( t->rightChild, k );
	}

(2) 统计二叉树中度为2的结点个数。
template <class Type> 
int?BinaryTree<Type> ::?Degrees2 ( BinTreeNode<Type>?* t )?const?{
	???if ( t == NULL ) return?0;
	???if ( t->leftChild != NULL &&?t->rightChild != NULL ) 
            return 1;
??    ?return?Degrees2 ( t->leftChild, k ) + Degrees2 ( t->rightChild, k );
	}

	(3) 统计二叉树中度为0（叶结点）的结点个数。
template <class Type> 
int?BinaryTree<Type> ::?leaves ( BinTreeNode<Type>?* t ) const?{
   if ( t == NULL )?return 0;
???if ( t->leftChild == NULL &&?t->rightChild == NULL ) 
        return?1;
???return?leaves ( t->leftChild ) + leaves ( t->rightChild );
}

	(4) 统计二叉树的高度。
template <class Type>
int BinaryTree<Type>?::?height ( BinTreeNode<Type>?*t )?{
???if ( t ==?NULL ) return?–1;
???int?hl = height ( t->leftChild );
???int hr = height ( t->rightChild );
???return?1+ ( hl > hr ??hl :?hr );
}

(5) 统计二叉树的宽度，即在二叉树的各层上，具有结点数最多的那一层上结点总数。
本题的想法是：先用前序遍历求出每一层的宽度，再求出最大宽度，即树的宽度。
①?求每一层宽度的算法：
template <class Type>?
int BinaryTree<Type>?::?levelNumber ( BinTreeNode<Type>?*t, int a[ ], int?h )?{
//求以*t为根的子树中各层的宽度, 存放在a[ ]?中, h是?*t所在层次号,
//要求在主程序中将a[h]初始化为0
???if?( t != NULL ) {		//若空树, 不统计
	?a[h] += 1;		//第h层宽度加一
	?levelNumber ( t->leftChild, a, h+1 );	//递归统计左子树中各层宽度
	?levelNumber ( t->rightChild, a, h+1 );//递归统计右子树中各层宽度
	???}
	}
② 求二叉树的宽度的算法
template <class Type>
int BinaryTree<Type>?::?width ( BinTreeNode<Type>?*t )?{
???int a[n+1], h = 0, i, wid;
	???for?( i = 0; i <= n; i++ ) 
            a[i] = 0;//统计数组a[ ]初始化
	???levelNumber ( t, a, h );	//调用求各层宽度的算法
	???wid = a[0];
	???for ( i = 1; i <= n; i++ )
		?if ( a[i] > wid ) wid = a[i];
	???return wid;
	}

?(6) 从二叉树中删去所有叶结点。
template <class Type>
void BinaryTree<Type>?:: defoliate ( BinTreeNode<Type> *&?t ) {
???if ( t ==?NULL ) return;
???if ( t->leftChild ==?NULL &&?t->rightChild ==?NULL ) 
?       { delete?t;??t = NULL; }
???else { 
?       defoliate ( t->leftChild );
?       defoliate ( t->rightChild );
	???}
}

(7) 计算二叉树中指定结点 *p?所在层次。
template <class Type>
int?BinaryTree<Type>?::?level ( BinTreeNode<Type>?* t, BintreeNode<Type>?*p ) {
???if ( t ==?NULL ) return?-1;
???if ( t ==?p )?return 0;
???if ( ( leftSubTreelevel = level ( t->leftChild, p ) ) > -1 )?
?         return 1 + leftSubTreelevel;
???if ( ( rightSubTreelevel = level ( t->rightChild, p ) ) > -1 ) 
?         return?1 + rightSubTreelevel;
???return?-1;
}

	(8) 计算二叉树中各结点中的最大元素的值。
template <class Type> 
Type?BinaryTree<Type> ::?MaxValue ( BinTreeNode<Type>?* t, Type?max ) {
	???if ( t != NULL ) {
		??if ( t->data > max ) max = t->data;
		??max = MaxValue ( t->leftChild, max );
		??max = MaxValue ( t->rightChild, max );
	???}
	???return?max;
	}

	(9) 以前序次序输出一棵二叉树所有结点的数据值及结点所在层次。
#include <iostream.h>
template <class Type>
void?BinaryTree <Type> :: nodePrint ( BinTreeNode<Type> *t, int?i ) {
???if ( t != NULL )?{
??        cout <<?t->data <<?“,” << i << endl;
??        nodePrint ( t->leftChild, i+1 );
?        ?nodePrint ( t->rightChild, i+1 );
???????}
	}

?