我需要获取所有节点的x,y坐标,例如:
10
8 15
7 9 13
X:访问中序遍历的节点之前已经访问过的节点数
Y:节点距离根的深度
例如对于节点15,x=5(15之前:已经访问过7、8、9、10、13),y=1(第二层)
树没有父指针
int inorder(Node *node, int x) {
if (node->left)
x = inorder(node->left, x);
x++;
if (node->right)
inorder(node->right, x);
return x;
}
int x0(Node *node) {
return inorder(node, -1);
}
int findY(Node *node, Node *from) {
if (node == from)
return 0;
else if (node->item < from->item)
return findY(node, from->left) + 1;
else
return findY(node, from->right) + 1;
}
int y0(Node *node) {
return findY(node, theRoot);
}
结果:x错,y对
打印:
void printCoord() {
queue<Node*> q;
q.push(theRoot);
int curLevel = 0;
while (q.size() > 0) {
Node *n = q.front();
q.pop();
int x = x0(n);
int y = y0(n);
if (y > curLevel) {
curLevel = y;
cout << endl;
}
cout << n->item << "(" << x << "," << y <<")";
if (n->left)
q.push(n->left);
if (n->right)
q.push(n->right);
}
}
AvlTree tree;
tree.insertBalance(10);
tree.insertBalance(8);
tree.insertBalance(15);
tree.insertBalance(7);
tree.insertBalance(9);
tree.insertBalance(13);
tree.printCoord();
结果:
10(2,0)
8(1,1)15(1,1)
7(0,2)9(0,2)13(0,2)
我试过了(我认为这不正确,因为右子树遍历不计入该节点)
int inorder(Node *node, int x) {
if (node->left)
x = inorder(node->left, x);
x++;
if (node->right)
x = inorder(node->right, x);
return x;
}
结果是
10(5,0)
8(2,1)15(1,1)
7(0,2)9(0,2)13(0,2)
最佳答案
// your inorder function is not correct
bool inorder(Node* node, int* x, Node* root) {
if (root==NULL)
return false;
if (inorder(node, x, root->left))
return true;
if (node==root) //inorder property here
return true;
(*x)++;
if (inorder(node, x, root->right))
return true;
return false;
}
int x0(Node *node) {
int x=0;
if (inorder(node, &x, theRoot)) //you did't pass root here
return x;
else //not found
return -1;
}
积分:
- 您没有通过根并与查询节点核对。那是不正确的。您需要从根开始搜索树。
- 对于任何有序属性,基本思想是向左走,做你想做的事,然后向右走。但这可能会因您的问题而异。
- 如果找到查询节点,则不再进行
inorder
调用。它一直返回到x0
,其中x
包含所需的值。
关于c++ - 二叉搜索树计算节点的坐标,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/23453172/