数据结构实验报告-树与二叉树
桂 林 理 工 大 学
实 验 报 告
一、实验名称：
实验6 树和二叉树
二、实验内容：
1.编写二叉树的递归遍历算法，实现:给定一棵二叉树的“扩展先序遍历序列”，创建这棵二叉树。
(1)输出二叉树的先序遍历的结点序列。
(2)输出二叉树的后序遍历的结点序列。
(3)输出二叉树的中序遍历的结点序列。
(4)输出二叉树的叶子结点。
(5)统计二叉树的结点个数。
源码：
#include <stdio.h>
#include <stdlib.h>
typedef struct TreeNode {
char data;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;
// 创建二叉树
TreeNode* createBinaryTree(char *str, int *index) {
if (str[*index] == '\0') {
return NULL;
}
if (str[*index] == '#') {
(*index)++;
return NULL;
}
TreeNode *root = (TreeNode*)malloc(sizeof(TreeNode));
root->data = str[*index];
(*index)++;
root->left = createBinaryTree(str, index);
root->right = createBinaryTree(str, index);
return root;
}
// 先序遍历
void preorder(TreeNode *root) {
if (root != NULL) {
printf("%c ", root->data);
preorder(root->left);
preorder(root->right);
}
}
// 后序遍历
void postorder(TreeNode *root) {
if (root != NULL) {
postorder(root->left);
postorder(root->right);
printf("%c ", root->data);
}
}
// 中序遍历
void inorder(TreeNode *root) {
if (root != NULL) {
inorder(root->left);
printf("%c ", root->data);
inorder(root->right);
}
}
// 输出叶子节点
void printLeaves(TreeNode *root) {
if (root != NULL) {
if (root->left == NULL && root->right == NULL) {
printf("%c ", root->data);
}
printLeaves(root->left);
printLeaves(root->right);
}
}
// 统计节点个数
int countNodes(TreeNode *root) {
if (root == NULL) {
return 0;
}
return 1 + countNodes(root->left) + countNodes(root->right);
}
int main() {
char str[] = "AB#D##CE##"; // 示例扩展先序遍历序列
int index = 0;
TreeNode *root = createBinaryTree(str, &index);
printf("先序遍历序列: ");
preorder(root);
printf("\n");
printf("后序遍历序列: ");
postorder(root);
printf("\n");
printf("中序遍历序列: ");
inorder(root);
printf("\n");
printf("叶子节点: ");
printLeaves(root);
printf("\n");
printf("节点个数: %d\n", countNodes(root));
return 0;
}
2.编写非递归遍历算法,实现:给定一棵二又树的先序 遍历序列和中序通历序列，创建这棵二叉树。
(1)输出二叉树的后序遍历的结点序列。
(2)输出二叉树的叶子结点。
(3)统计二叉树的结点个数。
(4)求二叉树的深度。
(5)输出二叉树指定结点的路径。
源码：
#include <iostream>
#include <stack>
#include <vector>
#include <unordered_map>
using namespace std;
struct TreeNode {
char data;
TreeNode* left;
TreeNode* right;
TreeNode(char val) : data(val), left(NULL), right(NULL) {}
};
TreeNode* buildTree(vector<char>& preorder, vector<char>& inorder) {
if (preorder.empty() || inorder.empty()) return NULL;
unordered_map<char, int> inorder_map;
for (int i = 0; i < inorder.size(); ++i) {
inorder_map[inorder[i]] = i;
}
stack<TreeNode*> stk;
TreeNode* root = new TreeNode(preorder[0]);
stk.push(root);
for (int i = 1; i < preorder.size(); ++i) {
TreeNode* node = new TreeNode(preorder[i]);
TreeNode* top = stk.top();
if (inorder_map[node->data] < inorder_map[top->data]) {
top->left = node;
} else {
TreeNode* parent = NULL;
while (!stk.empty() && inorder_map[node->data] > inorder_map[stk.top()->data]) {
parent = stk.top();
stk.pop();
}
parent->right = node;
}
stk.push(node);
}
return root;
}
void postorderTraversal(TreeNode* root) {
if (root == NULL) return;
stack<TreeNode*> stk;
vector<char> result;
stk.push(root);
while (!stk.empty()) {
TreeNode* node = stk.top();
stk.pop();
result.insert(result.begin(), node->data);
if (node->left) stk.push(node->left);
if (node->right) stk.push(node->right);
}
for (char ch : result) {
cout << ch << " ";
}
}
void printLeaves(TreeNode* root) {
if (root == NULL) return;
if (root->left == NULL && root->right == NULL) {
cout << root->data << " ";
}
printLeaves(root->left);
printLeaves(root->right);
}
int countNodes(TreeNode* root) {
if (root == NULL) return 0;
return 1 + countNodes(root->left) + countNodes(root->right);
}
int maxDepth(TreeNode* root) {
if (root == NULL) return 0;
return 1 + max(maxDepth(root->left), maxDepth(root->right));
}
void findPath(TreeNode* root, char target, vector<char>& path) {
if (root == NULL) return;
path.push_back(root->data);
if (root->data == target) {
for (char ch : path) {
cout << ch << " ";
}
cout << endl;
}
findPath(root->left, target, path);
findPath(root->right, target, path);
path.pop_back();
}
int main() {
vector<char> preorder = {'A', 'B', 'D', 'E', 'C', 'F', 'G'};
vector<char> inorder = {'D', 'B', 'E', 'A', 'F', 'C', 'G'};
TreeNode* root = buildTree(preorder, inorder);
cout << "后序遍历序列: ";
postorderTraversal(root);
cout << endl;
cout << "叶子节点: ";
printLeaves(root);
cout << endl;
cout << "节点个数: " << countNodes(root) << endl;
cout << "二叉树深度: " << maxDepth(root) << endl;
char target = 'D';
cout << "路径(" << target << "): ";
vector<char> path;
findPath(root, target, path);
return 0;
}
3.接1题，编写算法实现二叉树的先序线索化,并查找结点p的先序前驱结点和先序后继结点。
源码：
#include <iostream>
#include <stack>
using namespace std;
struct TreeNode {
char data;
TreeNode *left;
TreeNode *right;
bool isThreaded; // 线索化标记
TreeNode(char val) : data(val), left(NULL), right(NULL), isThreaded(false) {}
};
void preorderThreading(TreeNode* root, TreeNode*& prev) {
if (root == NULL) return;
if (root->left == NULL) {
root->left = prev;
root->isThreaded = true;
}
if (prev != NULL && prev->right == NULL) {
prev->right = root;
prev->isThreaded = true;
}
prev = root;
if (!root->isThreaded) {
preorderThreading(root->left, prev);
}
preorderThreading(root->right, prev);
}
TreeNode* preorderSuccessor(TreeNode* node) {
if (node->isThreaded) {
return node->right;
} else {
TreeNode* curr = node->right;
while (curr != NULL && !curr->isThreaded) {
curr = curr->left;
}
return curr;
}
}
TreeNode* preorderPredecessor(TreeNode* node) {
if (node->left != NULL) {
TreeNode* curr = node->left;
while (curr->right != NULL && !curr->right->isThreaded) {
curr = curr->right;
}
return curr;
} else {
return node->right;
}
}
int main() {
TreeNode *root = new TreeNode('A');
root->left = new TreeNode('B');
root->right = new TreeNode('C');
root->left->left = new TreeNode('D');
root->left->right = new TreeNode('E');
root->right->left = new TreeNode('F');
root->right->right = new TreeNode('G');
TreeNode *prev = NULL;
preorderThreading(root, prev);
TreeNode *target = root->left; // 以结点'B'为例
TreeNode *predecessor = preorderPredecessor(target);
TreeNode *successor = preorderSuccessor(target);
if (predecessor) {
cout << "结点'" << target->data << "'的先序前驱结点是: " << predecessor->data << endl;
} else {
cout << "结点'" << target->data << "'没有先序前驱结点" << endl;
}
if (successor) {
cout << "结点'" << target->data << "'的先序后继结点是: " << successor->data << endl;
} else {
cout << "结点'" << target->data << "'没有先序后继结点" << endl;
}
return 0;
}
四、心得体会：
通过实现二叉树的先序线索化算法，并查找指定结点的先序前驱和后继结点，我深刻体会到了树结构的复杂和线索化的重要性。在操作过程中，我学会了如何处理线索化和利用前序遍历进行结点的查找，进一步加深了对二叉树数据结构的理解。通过这一实践，我意识到了算法设计的精妙之处，同时也深感数据结构对于解决复杂问题的重要性。在编写代码的过程中，我不断思考优化方案，增强了自己的编程能力和逻辑思维能力。总的来说，这次实践让我收获颇丰，同时也更加坚定了我对算法与数据结构学习的重要性，激发了我对计算机科学领域的无限热情。