郑州新密网站建设,建网站学什么,怎样换网站logo,新手学做网站pdf桂 林 理 工 大 学
实 验 报 告
一、实验名称#xff1a;
实验6 树和二叉树 二、实验内容#xff1a;
1.编写二叉树的递归遍历算法#xff0c;实现:给定一棵二叉树的“扩展先序遍历序列”#xff0c;创建这棵二叉树。 (1)输出二叉树的先序遍历的结点序列。 (2)输出二…桂 林 理 工 大 学
实 验 报 告
一、实验名称
实验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(vectorchar preorder, vectorchar inorder) { if (preorder.empty() || inorder.empty()) return NULL; unordered_mapchar, int inorder_map; for (int i 0; i inorder.size(); i) { inorder_map[inorder[i]] i; } stackTreeNode* 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; stackTreeNode* stk; vectorchar 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, vectorchar 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() { vectorchar preorder {A, B, D, E, C, F, G}; vectorchar 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 ): ; vectorchar 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;
}
四、心得体会
通过实现二叉树的先序线索化算法并查找指定结点的先序前驱和后继结点我深刻体会到了树结构的复杂和线索化的重要性。在操作过程中我学会了如何处理线索化和利用前序遍历进行结点的查找进一步加深了对二叉树数据结构的理解。通过这一实践我意识到了算法设计的精妙之处同时也深感数据结构对于解决复杂问题的重要性。在编写代码的过程中我不断思考优化方案增强了自己的编程能力和逻辑思维能力。总的来说这次实践让我收获颇丰同时也更加坚定了我对算法与数据结构学习的重要性激发了我对计算机科学领域的无限热情。
