我有一棵二进制表示的树;
1
/
2
3
/
6 4
7 5
/
8
/
9
10
11
但实际上这不是二叉树,而是像
1
/ | |
2 3 4 5
/ |
6 7 8
/|
9 10 11
你能帮我打印出来吗(孩子按相反的顺序打印出来)
1 : 5 4 3 2
5 : 8
3 : 7 6
8 : 11 10 9
我的 TNode 类看起来像。
class TNode {
public:
unsigned long int data;
TNode * left;///first child
TNode * right;/// sibling
TNode * parent;/// parent
TNode(unsigned long int d = 0, TNode * p = NULL, TNode * n = NULL)///konstruktors
{
left = NULL;
right = NULL;
parent = p;
data = d;
}
};
这需要堆栈实现吗?
这种方法怎么样:按预顺序遍历树(访问每个节点)。对于每个节点(当移动到它时),检查它是否有左子节点。如果是这样(表示原始树中具有子元素的节点)使用":"打印节点数据,并获取其子树并递归地跟随所有正确的儿子(代表所有兄弟姐妹),然后打印每个正确的儿子数据(您以相反的顺序打印它。在代码中:
void print_siblings() {
if (this->right != NULL) {
this->right->print_siblings();
}
cout << data << ", ";
}
void traverse(void) {
if (this->left != NULL) {
cout << data << ":";
this->left->print_siblings();
cout << endl;
this->left->traverse();
}
if (this->right != NULL) {
this->right->traverse();
}
}
编辑:这是一个无序遍历:
void traverse_inorder(void) {
if (this->left != NULL) {
this->left->traverse_inorder();
cout << data << ":";
this->left->print_siblings();
cout << endl;
}
if (this->right != NULL) {
this->right->traverse_inorder();
}
}
预购的输出为:
1:5, 4, 3, 2,
3:7, 6,
5:8,
8:11, 10, 9,
无序的输出将是:
3:7, 6,
8:11, 10, 9,
5:8,
1:5, 4, 3, 2,
编辑2:只是为了完整起见,后序遍历也是如此:-)
void traverse_postorder(void) {
if (this->left != NULL) {
this->left->traverse_postorder();
}
if (this->right != NULL) {
this->right->traverse_postorder();
}
if (this->left != NULL) {
cout << data << ":";
this->left->print_siblings();
cout << endl;
}
}
及其输出:
8:11, 10, 9,
5:8,
3:7, 6,
1:5, 4, 3, 2,
尝试如下操作:(尚未测试)
printTree(TNode root) {
queue <TNode> proc;
proc.push(root);
while (!proc.empty()) {
TNode front = proc.front();
proc.pop();
// add front's children to a stack
stack <Tnode> temp;
Tnode current = front->left;
while (current != NULL) {
temp.push(current);
current = current->right;
}
// add the children to the back of queue in reverse order using the stack.
// at the same time, print.
printf ("%lld:", front->data);
while (!temp.empty()) {
proc.push(temp.top());
printf(" %lld", temp.top()->data);
temp.pop();
}
printf("n");
}
}
我仍在努力使它更优雅。感谢您的有趣问题!
编辑:将格式说明符更改为 lld
我做了这样的事情,但由于 while 循环,有点不递归。有没有办法让它更推荐
void mirrorChilds(TNode * root)//
{
if(!root) return;
cout << root->data << " ";
//tmp = tmp->right;
if(!root->left) return;
TNode * tmp = root->left;
while(tmp != NULL)
{
root->left = tmp;
tmp = tmp->right;
}
tmp = root->left;
while(root != tmp)
{
cout << tmp->data << " ";
tmp = tmp->parent;
}
cout << endl;
tmp = root->left;
while(root != tmp)
{
if(tmp->left) mirrorChilds(tmp);
//if(tmp->left) cout << tmp->left->data << endl;
tmp = tmp->parent;
}
}
它工作得很好,但是是的,我有点想得到 O(n*log(n)) 时间......