题解 P1305 【新二叉树】

rui_er

2019-05-23 19:56:00

Solution

# 方法简述 虽然不用建树,我还是建了一个,用的是顺序存储结构(数组) ```cpp char tree[501]; ``` # 头文件 ```cpp #include <iostream> #include <memory.h> #include <map> using namespace std; ``` 其中memory.h是为memset做准备的(我说的是memset,后面没有0!开个玩笑) # 建树 ```cpp char tree[501]; map<char, int> k; memset(tree, '*', 501); int n; cin>>n; char a, b, c; for(int i=0;i<n;i++) { cin>>a>>b>>c; if(!i) { tree[1] = a; k[a] = 1; } k[b] = k[a] * 2; tree[k[b]] = b; k[c] = k[a] * 2 + 1; tree[k[c]] = c; } ``` memset行用于给tree赋值。 > 听说第一行就是有关根节点的一行 if行用于判断是否为第一行,将根节点写入。k用于存字符出现的下标地址,方便查询一个节点的位置。 # 遍历 ```cpp void DLR(int n) { if(tree[n] == '*') return; cout<<tree[n]; DLR(n*2); DLR(n*2+1); } ``` 还记得前文的memset吗?输入的空结点用```*```表示,所以方便起见把树初始化成```*```。如果遇到```*```,则代表该结点不存在,自然就可以退出那个结点了。 根据前序遍历的定义,写出递归函数即可。 # 程序 ```cpp #include <iostream> #include <memory.h> #include <map> using namespace std; char tree[501]; map<char, int> k; void DLR(int n) { if(tree[n] == '*') return; cout<<tree[n]; DLR(n*2); DLR(n*2+1); } int main() { memset(tree, '*', 501); int n; cin>>n; char a, b, c; for(int i=0;i<n;i++) { cin>>a>>b>>c; if(!i) { tree[1] = a; k[a] = 1; } k[b] = k[a] * 2; tree[k[b]] = b; k[c] = k[a] * 2 + 1; tree[k[c]] = c; } DLR(1); return 0; } ```