4. DS二叉树–基于数组存储的构建
题目描述
任意二叉树可以根据完全二叉树性质保存在一个数组中。已知二叉树的数组存储，用程序构建该二叉树。
提示：用递归方法或非递归都可以
递归方法的代码框架如下：
输入
第一行输入一个整数t，表示有t个测试数据
第二行起输入二叉树的数组存储结果，空树用字符‘0’表示，输入t行
数组的数据由大写字母和0表示
输出
逐行输出每个二叉树的先序结果
输入样例
3
ABC0D
ABCDEF000G
ABEC0F0D0
输出样例
ABDC
ABDEGCF
ABCDEF
参考代码
#include <iostream> using namespace std; class treenode { public: char data; treenode *left; treenode *right; treenode() { data = '0'; left = NULL; right = NULL; } }; class tree { public: int len; string strtree; treenode *root; void create(string treearray) { len = treearray.length(); strtree.assign(treearray); root = createtree(0); } treenode *createtree(int pos) { treenode *t; int ch; if (pos > strtree.length()) return NULL; ch = strtree[pos]; if (ch == '0') t = NULL; else { t = new treenode(); t->data = ch; if (2 * (pos + 1) <= len) t->left = createtree(2 * (pos + 1) - 1); if (2 * (pos + 1) + 1 <= len) t->right = createtree(2 * (pos + 1)); } return t; } void Preorder() { preorder(root); } void preorder(treenode *p) { if (p != NULL) { cout << p->data; preorder(p->left); preorder(p->right); } } void inorder(treenode *p) { if (p != NULL) { inorder(p->left); cout << p->data; inorder(p->right); } } void postorder(treenode *p) { if (p != NULL) { postorder(p->left); postorder(p->right); cout << p->data; } } }; int main() { int t; cin >> t; while (t--) { tree p; string a; cin >> a; p.create(a); p.Preorder(); cout << endl; } }
5. DS森林叶子编码
题目描述
给定一组森林，编写程序生成对应的二叉树，输出这颗二叉树叶结点对应的二进制编码.规定二叉树的左边由0表示，二叉树的右边由1表示。
输入
N B 表示N个树，每结点最多B个分支
第2行至第N+1行，每个树的先序遍历
输出
每行表示一个叶结点对应的二进制编码.
输入样例
3 3
A B 0 0 0 C 0 0 0 D 0 0 0
E F 0 0 0 0 0
G H 0 0 0 I J 0 0 0 0 0 0
输出样例
0 1 1
1 0
1 1 0 1 0
参考代码
#include<iostream> #include<string> using namespace std; int B; class BiTreeNode{ public : char data; BiTreeNode *left, *right; BiTreeNode(){ left= NULL; right= NULL; } }; class TreeNode{ public: char data; TreeNode **child; TreeNode(){ child = new TreeNode*[B]; for(int i= 0; i< B; i++) child[i]= NULL; } }; class Tree{ private: TreeNode* root; public : Tree(){ int i= 0; // root= CreateTree(); } TreeNode* CreateTree(){ TreeNode *p= NULL; char c; cin>>c; if(c!= '0'){ p= new TreeNode; p->data= c; for(int k= 0; k< B; k++) p->child[k]= CreateTree(); } return p; } BiTreeNode* change(){ return change(root); } BiTreeNode* change(TreeNode* t){ BiTreeNode *p= NULL; if(t){ p= new BiTreeNode; p->data= t->data; p->left= change(t->child[0]); if(p->left){ BiTreeNode *q= p->left; for(int i= 1; i< B; i++){ q->right= change(t->child[i]); if(q->right) q= q->right; } } } return p; } }; class BiTree{ private: BiTreeNode* root; void get_leaves(BiTreeNode* t, string str){ if(t){ if(!t->left&&!t->right){ int len= str.length(); str= str.substr(0, len- 1); cout<<str<<endl; } get_leaves(t->left, str+ "0 "); get_leaves(t->right, str+ "1 "); } } public : void merge(BiTreeNode** t, int N){ for(int i= 0; i< N- 1; i++) t[i]->right= t[i+ 1]; root= t[0]; } void get_leaves(){ string str= ""; get_leaves(root, str); } }; int main(){ int N; cin>>N>>B; Tree* p= new Tree[N]; BiTreeNode**q= new BiTreeNode*[N]; for(int i= 0; i< N; i++) q[i]= p[i].change(); BiTree tree; tree.merge(q, N); tree.get_leaves(); return 0; }
