6-4 用嵌套类写出用链表表示的二叉树的类声明。
把书p170~171页改写成嵌套形式
6-5 在结点个数为n(n>1)的各棵树中，高度最小的树的高度是多少？它有多少个叶结点？多少个分支结点？高度最大的树的高度是多少？它有多少个叶结点？多少个分支结点？
最小高度为1，有两层。n-1个页结点,1个分支结点。
最大高度为n-1，有n层，n-1 个分支结点，1个页结点.
6-7 如果一棵树有n1个度为1的结点，有n2个度为2的结点，...，nm个度为m的结点，试问有多少个度为0的结点？试推导之。
设度为0的结点为n0个。可以想象，每个度必定对应一个结点，或者反过来，除去根结点每个结点都消耗一个度。那么我们可以列出如下等式 n1*1+n2*2+n3*3+...+nm*m=n0+n1+n2+...+nm-1
n0=1+n2*1+n3*2+...+nm*(m-1)
6-8 试分别找出满足以下条件的所有二叉树：
(1) 二叉树的前序序列与中序序列相同；
(2) 二叉树的中序序列与后序序列相同；
(3) 二叉树的前序序列与后序序列相同；
(1)空树，或者所有结点均没有左子树的单支树；
(2)空树，或者所有结点均没有右子树的单枝树；
(3)空树，或者只有根结点的二叉树;
6-9 若用二叉链表作为二叉树的存储表示，试针对以下问题编写递归算法:
(1) 统计二叉树中叶结点的个数。
(2) 以二叉树为参数，交换每个结点的左子女和右子女。
声明：类定义参见教科书
(1)思路：如果有左子女或者右子女，返回左子女或者右子女的叶结点个数，如果没有(本身就是叶结点)，返回1.方便起见，作为类成员函数加入。
(2)思路同上，另一直想把二叉树作为直接参数，函数作为外部函数，但这样写起来要使用很多类函数，很麻烦，每次都要重新构造一棵树，非常麻烦，上题也是这个困惑。看到参考答案直接忽视题目的要求--二叉树作为参数，无语，直接仿效。
把书p170~171页改写成嵌套形式
template< class Type >class BinaryTree{
private:
template< calss Type >class BinTreeNode{
public:
BinTreeNode< Type >* leftChild,*rightChild;
Type data;
}
Type RefValue;
BinTreeNode< Type >* root;
......
结点相关的一些递归操作
......
publick:
//一些构造函数
BinaryTree();
~BinaryTree();
BinTreeNode();
~BinTreeNode();
.......
二叉树的公共操作
.......
}6-5 在结点个数为n(n>1)的各棵树中，高度最小的树的高度是多少？它有多少个叶结点？多少个分支结点？高度最大的树的高度是多少？它有多少个叶结点？多少个分支结点？
最小高度为1，有两层。n-1个页结点,1个分支结点。
最大高度为n-1，有n层，n-1 个分支结点，1个页结点.
6-7 如果一棵树有n1个度为1的结点，有n2个度为2的结点，...，nm个度为m的结点，试问有多少个度为0的结点？试推导之。
设度为0的结点为n0个。可以想象，每个度必定对应一个结点，或者反过来，除去根结点每个结点都消耗一个度。那么我们可以列出如下等式 n1*1+n2*2+n3*3+...+nm*m=n0+n1+n2+...+nm-1
n0=1+n2*1+n3*2+...+nm*(m-1)
6-8 试分别找出满足以下条件的所有二叉树：
(1) 二叉树的前序序列与中序序列相同；
(2) 二叉树的中序序列与后序序列相同；
(3) 二叉树的前序序列与后序序列相同；
(1)空树，或者所有结点均没有左子树的单支树；
(2)空树，或者所有结点均没有右子树的单枝树；
(3)空树，或者只有根结点的二叉树;
6-9 若用二叉链表作为二叉树的存储表示，试针对以下问题编写递归算法:
(1) 统计二叉树中叶结点的个数。
(2) 以二叉树为参数，交换每个结点的左子女和右子女。
声明：类定义参见教科书
(1)思路：如果有左子女或者右子女，返回左子女或者右子女的叶结点个数，如果没有(本身就是叶结点)，返回1.方便起见，作为类成员函数加入。
int count(BinaryTree &t){
count(root);
}
int count(BinTreeNode *current){
if(current==NULL) return 0;
else if(current->leftChild==NULL && current->rightChild==NULL)return 1;
else return count(current->leftChild)+count(current->rightChild);
}
(2)思路同上，另一直想把二叉树作为直接参数，函数作为外部函数，但这样写起来要使用很多类函数，很麻烦，每次都要重新构造一棵树，非常麻烦，上题也是这个困惑。看到参考答案直接忽视题目的要求--二叉树作为参数，无语，直接仿效。
void exchange(BinaryTree & t){
exchange(root);
}
void exchange(BinTreeNode *current){
BinTreeNode *temp;
if(current==NULL)return;
//书里的条件有问题，NULL->link不一定=NULL
temp=current->leftChild;
current->leftChild=current->rightChild;
current->rightChild=temp;
exchange(current->leftChild);
exchange(current->rightChild);
}
Comments (0)