SWUSTOJ #1052 输出利用先序遍历创建的二叉树中的指定结点的双亲结点
SWUSTOJ #1052 输出利用先序遍历创建的二叉树中的指定结点的双亲结点
- 题目
- 输入
- 输出
- 样例输入
- 样例输出
- 源代码
题目
利用先序递归遍历算法创建二叉树并输出该二叉树中指定结点的双亲结点。约定二叉树结点数据为单个大写英文字符。当接收的数据是字符“#”时表示该结点不需要创建，否则创建该结点。最后再输出创建完成的二叉树中的指定结点的双亲结点。注意输入数据序列中的“#”字符和非“#”字符的序列及个数关系，这会最终决定创建的二叉树的形态。
输入
输入用例分2行输入，第一行接受键盘输入的由大写英文字符和“#”字符构成的一个字符串（用于创建对应的二叉树），第二行为指定的结点数据。
输出
用一行输出该用例对应的二叉树中指定结点的双亲结点。若相应双亲结点不存在则以“#”代替。
样例输入
A##
A
ABC####
B
样例输出
A
源代码
#include <iostream>
#include <queue>using namespace std;char parent='#';
class treenode
{friend class tree;
public:treenode(char a) :data(a){left = NULL;right = NULL;}
private:char data;treenode* left;treenode* right;
};
class tree
{
public:tree() :root(NULL){}void precreate(treenode* & current, queue<char> &Q);void find_left(treenode* current, char a);treenode* root;
};
void tree::precreate(treenode* & current, queue<char> &Q)
{if (Q.empty()){return;}if (Q.front() == '#'){current = NULL;Q.pop();}else{current = new treenode(Q.front());Q.pop();precreate(current->left, Q);precreate(current->right, Q);}
}void tree::find_left(treenode* current, char a)
{if (current == NULL){return;}if (current->data == a){return;}else{if (current->left){parent = current->data;find_left(current->left, a);}if (current->right){parent = current->data;find_left(current->right, a);}}
}int main()
{tree T;queue<char> Q;char arr[1000];cin >> arr;for (int i = 0; arr[i] != '\0'; i++){Q.push(arr[i]);}T.precreate(T.root, Q);char x;cin >> x;T.find_left(T.root, x);cout << parent;return 0;
}
发布评论