数据结构习题解析与实验指导第五章(树和二叉树)课后算法设计题
·
1.以二叉链表作为二叉树的存储结构，统计二叉树的叶子结点个数。
#include <iostream>
using namespace std;
struct Node {
int data;
Node* left;
Node* right;
Node(int data = 0, Node* left = 0, Node* right = 0):
data(data),
left(left),
right(right)
{
}
};
int countLeaves(Node* tree) {
if (tree->left == 0 && tree->right == 0) {
return 1;
}
return
(tree->left == 0 ? 0 : countLeaves(tree->left)) +
(tree->right == 0 ? 0 : countLeaves(tree->right));
}
void release(Node* tree) {
if (tree != 0) {
release(tree->left);
release(tree->right);
delete tree;
}
}
int main() {
Node* tree = new Node(1, new Node(2, new Node(4, new Node(5), new Node(6)), new Node(3)));
cout << countLeaves(tree) << endl;
release(tree);
return 0;
}
2.以二叉链表便利作为存储结构，判断两棵树是否相等。
#include <iostream>
#include <vector>
using namespace std;
struct Node {
int data;
Node* left;
Node* right;
Node(int data = 0, Node* left = 0, Node* right = 0):
data(data),
left(left),
right(right)
{
}
};
bool isTheSameTree(Node* tree1, Node* tree2) {
if (tree1 == 0 || tree2 == 0) {
return tree1 == tree2;
}
return tree1->data == tree2->data &&
isTheSameTree(tree1->left, tree2->left) &&
isTheSameTree(tree1->right, tree2->right);
}
void release(Node* tree) {
if (tree != 0) {
release(tree->left);
release(tree->right);
delete tree;
}
}
int main() {
Node* tree = new Node(1, new Node(2, new Node(4, new Node(5), new Node(6)), new Node(3)));
Node* test = new Node(1, new Node(2, new Node(4, new Node(5), new Node(7)), new Node(3)));
Node* test2 = new Node(1, new Node(2, new Node(4, new Node(5), new Node(6)), 0));
cout << isTheSameTree(tree, tree) << endl;
cout << isTheSameTree(tree, test) << endl;
cout << isTheSameTree(tree, test2) << endl;
release(tree);
release(test);
release(test2);
return 0;
}
3.以二叉链表便利作为存储结构，交换二叉树每个结点的左孩子和右孩子。
#include <iostream>
#include <vector>
using namespace std;
struct Node {
int data;
Node* left;
Node* right;
Node(int data = 0, Node* left = 0, Node* right = 0):
data(data),
left(left),
right(right)
{
}
};
void exchange(Node* tree) {
if (tree != 0) {
Node* temp = tree->left;
tree->left = tree->right;
tree->right = temp;
exchange(tree->left);
exchange(tree->right);
}
}
void preview(Node* tree) {
if (tree != 0) {
cout << tree->data << " ";
preview(tree->left);
preview(tree->right);
}
}
void release(Node* tree) {
if (tree != 0) {
release(tree->left);
release(tree->right);
delete tree;
}
}
int main() {
Node* tree = new Node(1, new Node(2, new Node(4, new Node(5), new Node(6)), new Node(3)));
preview(tree);
exchange(tree);
cout << endl;
preview(tree);
release(tree);
return 0;
}
4.设计二叉树的双序遍历算法（双序遍历是指对于二叉树的每一个结点来说，先访问这个结点，再按双序遍历它的左子树，然后再一次访问这个结点，接下来按照双序遍历它的右子树）。
#include <iostream>
#include <vector>
using namespace std;
struct Node {
int data;
Node* left;
Node* right;
Node(int data = 0, Node* left = 0, Node* right = 0):
data(data),
left(left),
right(right)
{
}
};
void doubleOrderTraverse(Node* tree) {
if (tree != 0) {
cout << tree->data << " ";
doubleOrderTraverse(tree->left);
cout << tree->data << " ";
doubleOrderTraverse(tree->right);
}
}
void release(Node* tree) {
if (tree != 0) {
release(tree->left);
release(tree->right);
delete tree;
}
}
int main() {
Node* tree = new Node(1, new Node(2, new Node(4, new Node(5), new Node(6)), new Node(3)));
doubleOrderTraverse(tree);
cout << endl;
release(tree);
return 0;
}
5.计算二叉树的最大宽度（二叉树的最大宽度是指二叉树所有层次中结点个数的最大值）。
#include <iostream>
#include <queue>
using namespace std;
struct Node {
int data;
Node* left;
Node* right;
int level;
Node(int data = 0, Node* left = 0, Node* right = 0):
data(data),
left(left),
right(right)
{
}
};
void levelMax(Node* tree, int m[], int level = 0) {
if (tree != 0) {
m[level] ++;
levelMax(tree->left, m, level + 1);
levelMax(tree->right, m, level + 1);
}
}
int levelMax(Node* tree) {
int buf[10] = { 0 };
levelMax(tree, buf);
int max = 0;
for (int i = 0; i < 10; i++) {
if (buf[i] > max) {
max = buf[i];
}
}
return max;
}
int levelTraverseMax(Node* tree) {
if (tree == 0) {
return 0;
}
int max_v = 0; //全局最大的数量
int cur_level = 0; //当前层次
int cur_num = 0; //当前数量
//宽度优先遍历
tree->level = 0;
queue<Node*> q; q.push(tree);
while (!q.empty()) {
Node* node = q.front(); q.pop();
if (node->level == cur_level) {
cur_num++;
}
else {
if (cur_num > max_v) {
max_v = cur_num;
}
cur_level++;
cur_num = 1;
}
if (node->left != 0) {
node->left->level = node->level + 1;
q.push(node->left);
}
if (node->right != 0) {
node->right->level = node->level + 1;
q.push(node->right);
}
}
if (cur_num > max_v) {
max_v = cur_num;
}
return max_v;
}
void release(Node* tree) {
if (tree != 0) {
release(tree->left);
release(tree->right);
delete tree;
}
}
int main() {
Node* tree = new Node(1, new Node(2, new Node(4, new Node(5), new Node(6)), new Node(3, new Node(7))));
cout << "法1：" << levelMax(tree) << endl;
cout << "法2：" << levelTraverseMax(tree) << endl;
release(tree);
return 0;
}
6.用按层次遍历二叉树的方法，统计树中具有度为1的结点数目。
#include <iostream>
#include <queue>
using namespace std;
struct Node {
int data;
Node* left;
Node* right;
Node(int data = 0, Node* left = 0, Node* right = 0):
data(data),
left(left),
right(right)
{
}
};
int countDegreeOne(Node* tree) {
if (tree == 0) {
return 0;
}
queue<Node*> q;
q.push(tree);
int count = 0;
while (!q.empty())
{
Node* node = q.front(); q.pop();
if ((node->left == 0) + (node->right == 0) == 1) {
count++;
}
if (node->left != 0) {
q.push(node->left);
}
if (node->right != 0) {
q.push(node->right);
}
}
return count;
}
void release(Node* tree) {
if (tree != 0) {
release(tree->left);
release(tree->right);
delete tree;
}
}
int main() {
Node* n1 = new Node(1);
Node* n2 = new Node(2);
Node* n3 = new Node(3, n1, n2);
Node* n4 = new Node(4, 0, n3);
Node* tree = new Node(5, n4, 0);
cout << countDegreeOne(tree) << endl;
release(tree);
return 0;
}
7.求任意二叉树中第一条最长的路径长度，并输出此路径上各结点的值。
标准答案中，利用一个数据结构（栈）来保存后序遍历时的路径信息，遇到叶子时，如果此时是最长的路径，则把整个结构复制一遍保存。事实上，这种方法挺费劲，因为要经常复制。所以本例中，利用一个parent指针，指向节点的父结点，这样，就可以从叶子结点追溯到根结点了。
#include <iostream>
using namespace std;
struct Node {
int data;
Node* left;
Node* right;
Node* parent; //指向父结点
Node(int data = 0, Node* left = 0, Node* right = 0):
data(data),
left(left),
right(right)
{
}
};
void maxLengthPathDo(Node* tree, int level, int& maxLevel, Node* & maxLeave) {
if (tree != 0) {
if (tree->left == 0 && tree->right == 0) {
if (level > maxLevel) {
maxLevel = level;
maxLeave = tree;
}
}
if (tree->left != 0) {
tree->left->parent = tree;
maxLengthPathDo(tree->left, level + 1, maxLevel, maxLeave);
}
if (tree->right != 0) {
tree->right->parent = tree;
maxLengthPathDo(tree->right, level + 1, maxLevel, maxLeave);
}
}
}
Node* maxLengthPath(Node* tree) {
tree->parent = 0;
int maxLevel = 0;
Node* maxLeave = 0;
maxLengthPathDo(tree, 0, maxLevel, maxLeave);
return maxLeave;
}
void release(Node* tree) {
if (tree != 0) {
release(tree->left);
release(tree->right);
delete tree;
}
}
int main() {
Node* n1 = new Node(1);
Node* n2 = new Node(2);
Node* n3 = new Node(3, n1, n2);
Node* n4 = new Node(4, new Node(6), n3);
Node* tree = new Node(5, n4, 0);
Node* path = maxLengthPath(tree);
while (path != 0)
{
cout << path->data << " ";
path = path->parent;
}
release(tree);
return 0;
}
8.输出二叉树中从每个叶子结点到根结点的路径。
#include <iostream>
#include <vector>
using namespace std;
struct Node {
int data;
Node* left;
Node* right;
Node* parent; //指向父结点
Node(int data = 0, Node* left = 0, Node* right = 0) :
data(data),
left(left),
right(right)
{
}
};
void release(Node* tree) {
if (tree != 0) {
release(tree->left);
release(tree->right);
delete tree;
}
}
void displayPath(Node* leave) {
while (leave != 0)
{
cout << leave->data << " ";
leave = leave->parent;
}
}
void displayLeaveToRoot(Node* tree, int level = 0) {
if (tree != 0) {
if (level == 0) {
tree->parent = 0;
}
if (tree->left == 0 && tree->right == 0) {
displayPath(tree);
cout << endl;
}
if (tree->left != 0) {
tree->left->parent = tree;
displayLeaveToRoot(tree->left, level + 1);
}
if (tree->right != 0) {
tree->right->parent = tree;
displayLeaveToRoot(tree->right, level + 1);
}
}
}
void displayLeaveToPath2(Node* tree, vector<Node*> & stack) {
if (tree != 0) {
stack.push_back(tree);
if (tree->left == 0 && tree->right == 0) {
for (int i = stack.size() - 1; i >= 0; i--) {
cout << stack[i]->data << " ";
}
cout << endl;
}
if (tree->left != 0) {
displayLeaveToPath2(tree->left, stack);
}
if (tree->right != 0) {
displayLeaveToPath2(tree->right, stack);
}
stack.pop_back();
}
}
int main() {
Node* n1 = new Node(1);
Node* n2 = new Node(2);
Node* n3 = new Node(3, n1, n2);
Node* n4 = new Node(4, new Node(6), n3);
Node* tree = new Node(5, n4, 0);
cout << "法1:" << endl;
displayLeaveToRoot(tree);
cout << "法2:" << endl;
vector<Node*> stack;
displayLeaveToPath2(tree, stack);
release(tree);
return 0;
}
9.二叉树的带权路径长度（WPLWPLWPL）是二叉树中所有叶子结点带权路径长度之和。给定一棵二叉树TTT，采用二叉链表存储，结点结构为（left,weight,right）（left, weight, right）（left,weight,right）,其中叶子结点的weightweightweight域保存该结点的非负权值。设rootrootroot为TTT的根结点指针，请设计求TTT的WPLWPLWPL的算法。要求：
（1）给出算法的基本设计思想。
（2）使用C或C++语言，给出二叉树结点的数据类型定义。
（3）根据设计思想，采用C或C++语言描述算法，关键之处给出注释。
#include <iostream>
#include <queue>
using namespace std;
struct Node {
int data;
Node* left;
Node* right;
int weight; //此域只在叶子结点中有用
Node(int data = 0, Node* left = 0, Node* right = 0, int weight = 1):
data(data),
left(left),
right(right),
weight(weight)
{
}
};
void release(Node* tree) {
if (tree != 0) {
release(tree->left);
release(tree->right);
delete tree;
}
}
void WPL(Node* tree, int& wpl, int level = 0) {
if (tree) {
if (tree->left == 0 && tree->right == 0) {
wpl += tree->weight * level;
}
if (tree->left != 0) {
WPL(tree->left, wpl, level + 1);
}
if (tree->right != 0) {
WPL(tree->right, wpl, level + 1);
}
}
}
int WPL2(Node* tree, int level = 0) {
if (tree) {
if (tree->left == 0 && tree->right == 0) {
return (tree->weight) * level;
}
return WPL2(tree->left, level + 1) + WPL2(tree->right, level + 1);
}
return 0;
}
int main() {
Node* n1 = new Node(1, 0, 0, 3);
Node* n2 = new Node(2, 0, 0, 4);
Node* n3 = new Node(3, n1, n2);
Node* n4 = new Node(4, new Node(6, 0, 0, 5), n3);
Node* tree = new Node(5, n4, 0);
int wpl = 0;
WPL(tree, wpl);
cout << "法1: wps is :" << wpl << endl;
cout << "法2: wps is :" << WPL2(tree) << endl;
release(tree);
return 0;
}
魔乐社区（Modelers.cn) 是一个中立、公益的人工智能社区，提供人工智能工具、模型、数据的托管、展示与应用协同服务，为人工智能开发及爱好者搭建开放的学习交流平台。社区通过理事会方式运作，由全产业链共同建设、共同运营、共同享有，推动国产AI生态繁荣发展。
更多推荐
1
0- 0
已为社区贡献3条内容
所有评论(0)