最近我在学习二叉树相关的很多算法,于是我就在想,能不能把二叉树画出来看看。
比如下图这样:
(看不见图的说明你的浏览器不支持svg)
问题的细化
我们想要在一个平面的画布上绘图,比如一个800像素x600像素的bitmap。首先把这个画布切成一个个正方形的格子(tile)。每个格子的大小比如是20x20。每个格子里面只放一个二叉树节点。我们需要寻找一个算法,给二叉树的每个节点计算出一个(x,y)的值,来对应我们画好的格子。
一旦把(x,y)的值确定下来,剩下就是画圆圈、画线的工作了,就简单多了。
那么依据什么规则来确定x,y的值呢?
- Trees impose a distance on the nodes; no node should be closer to the root than any of its ancestors.
- Nodes at the same level of the tree should lie along a straight line, and the straight lines corresponding to the levels should be parallel.
- The relative order of nodes on any level should be the same as in the level order traversal of the tree.
- For a binary tree, a left child should be positioned to the left of its parent and a right child to the right.
- A parent should be centred over its children.
- A subtree of a given tree should be drawn the same way regardless of where it occurs in the tree.
根据上面的第二条规则,y的值其实很容易获得,它就对应节点的level值。所以对二叉树进行层序遍历即可。
所以问题的核心是给每个二叉树节点计算横坐标x的值!
一个最直接的做法是,直接以中序遍历的序号作为横坐标的值。
用这样的算法,画前序遍历为{2,1,6,4,3,5,8,7}的二叉搜索树,结果为:
用这样的算法,画前序遍历为{6,5,1,3,2,4,10,8,7,9,11}的二叉搜索树,结果为:
这样有两个问题
- 父节点并没有位于子节点的中心
- 太宽了,浪费纸张。我们希望在满足那6个条件的前提下,画出来的二叉树的宽度越小越好。
如果想要宽度最小,据文献说:“This problem can be solved in polynomial time using linear programming, but it is NP-hard if there is a need for a grid drawing with integer values for the coordinates.”
假如我们不求最优解,只要一个看起来还过得去的结果。那么就稍微简单些。下面描述我从1981年的一篇论文中找到的REINGOLD-TILFORD算法,简称RT算法。
Reingold-Tilford算法
首先定义数据结构,假设二叉树结点的定义为:
template <typename T>
class TreeNode {
public:
T data;
/** left child node */
TreeNode* left;
/** right child node */
TreeNode* right;
};
那么在data中,除了原本的value之外,我们还得再加一个offset值。
struct NodeData {
int value;
int offset;
NodeData(int i = 0) : value(i),offset(0) {}
};
其中offset是指这个节点相当于左右子节点的距离。因为我们要求父节点必须居中,所以它相对于左右子节点的距离必须是相同的。所以这里用一个int值就可以了。
我们递归的计算出这个值
/**
* param node 当前节点
*/
template <typename TreeNode>
void calcOffset(TreeNode* node);
calcOffset函数把当前节点相对于左右子节点的offset计算出来(怎么实现稍后讲)。
有了相对偏移之后,我们很容易把它变成绝对坐标。我们假设根节点的横坐标为0,然后根据offset值,依次推算下面各层节点的绝对坐标。
具体实现我是用一个前序遍历完成的
template <typename TreeNode>
struct TreeNodeWithPos {
TreeNode* node;
int offset;
TreeNodeWithPos(TreeNode* n, int x1) : node(n), offset(x1) {}
};
/**
* 把父子节点之间的相对offset变成绝对的position
* param node 根节点
*/
template <typename TreeNode>
void convertOffsetToAbs(TreeNode* root) {
TreeNode* node=root;
int x=0;
//以前序遍历的方式,把父子节点之间的相对offset变成绝对的position
std::vector<TreeNodeWithPos<TreeNode> > stack;
while (true) {
for (; node; node = node->left) {
const int offset = node->data.offset;
assert(offset >= 0);
node->data.offset = x;
stack.push_back(TreeNodeWithPos<TreeNode>(node, offset));
x -= offset;
}
if (stack.empty()) break;
TreeNodeWithPos<TreeNode>& n = stack.back();
node = n.node->right;
x = n.node->data.offset + n.offset;
stack.pop_back();
}
}
为了减少内存使用量,我把计算出来的格子坐标依然保存在offset这个字段里。
但是这样有个问题,计算出来的横坐标有正有负。这非常不利于绘图,因为一般来说,坐标值都是正的。
那么,我们其实只需要找到横坐标最小(1或2)的那个节点,然后让每个节点的横坐标都减去它的横坐标(-3)即可。改完后的代码如下,我又加了一层循环。
template <typename TreeNode>
struct TreeNodeWithPos {
TreeNode* node;
int offset;
TreeNodeWithPos(TreeNode* n, int x1) : node(n), offset(x1) {}
};
/**
* 把父子节点之间的相对offset变成绝对的position
* param node 根节点
*/
template <typename TreeNode>
void convertOffsetToAbs(TreeNode* root) {
TreeNode* node=root;
int x=0;
int minX=0;
//以前序遍历的方式,把父子节点之间的相对offset变成绝对的position
std::vector<TreeNodeWithPos<TreeNode> > stack;
while (true) {
for (; node; node = node->left) {
minX=std::min(minX,x);
const int offset = node->data.offset;
assert(offset >= 0);
node->data.offset = x;
stack.push_back(TreeNodeWithPos<TreeNode>(node, offset));
x -= offset;
}
if (stack.empty()) break;
TreeNodeWithPos<TreeNode>& n = stack.back();
node = n.node->right;
x = n.node->data.offset + n.offset;
stack.pop_back();
}
root->inOrderTravel([minX](TreeNode* node)->bool{
node->data.offset-=minX;
assert(node->data.offset >= 0);
return true;
});
}
为了找到横坐标最小的节点,非得遍历所有节点吗?能不能更快速的找到最左边那个节点?这个我想了很久,稍后讨论。
求解offset
TR算法的基本思路是采用分治算法,假设根节点的左子树和右子树已经画好,但是这两棵子树距离根节点应该有多远呢?
假设初始情况下,根节点的offset等于1。然后一层层的往下遍历,看左子树在当前层的最右端与右子树在当前层的最左端是否相交,如果相交,那么就增大根节点的offset的值。
那么怎样才能把最右和最左的那个节点找到呢? 顺着右子树向左遍历,是不是就能找到它最左边的节点?不管,先写代码看看。
//calcOffset的代码段1
const int MINSEP=1; //同一层两个节点至少相隔多远
int cursep = MINSEP; // SEPARATION ON CURRENT LEVEL
int rootsep = MINSEP; // CURRENT SEPARATION AT this node
int LOFFSUM = 0; // OFFSET FROM L TO this node
int ROFFSUM = 0; // OFFSET FROM R TO this node
TreeNode* L = node->left;
TreeNode* R = node->right;
//每循环一次,L和R的层数都会加一
//所以跳出循环时谁不为NULL,说明谁更高
//每一次循环,两棵树只会分的越来越开,不会变得更近
//即,rootsep只增加,不减少
while (L && R) {
if (cursep < MINSEP) {
// push them apart until minimum separation
rootsep += (MINSEP - cursep);
cursep += MINSEP;
}
//左子树沿着右边界往下走
if (L->right) {
LOFFSUM += L->data.offset;
cursep -= L->data.offset;
L = L->right;
} else {
LOFFSUM -= L->data.offset;
cursep += L->data.offset;
L = L->left;
}
//右子树沿着左边界往下走
if (R->left) {
ROFFSUM -= R->data.offset;
cursep -= R->data.offset;
R = R->left;
} else {
ROFFSUM += R->data.offset;
cursep += R->data.offset;
R = R->right;
}
}
// SET THE OFFSET IN NODE T, AND INCLUDE IT IN
// ACCUMULATED OFFSETS FOR L AND R
//除以2向上取整,使得2*offset >= rootsep
node->data.offset = (rootsep + 1) / 2;
LOFFSUM -= node->data.offset;
ROFFSUM += node->data.offset;
不是。请看下图
解决办法是像线索二叉树一样,加入线索边。
即,如果一个叶节点不在最下面一层,那么它会变成一个线索节点,它的左右指针会被用于指向下一层的边界点。于是我们的节点定义就变成了这样:
struct NodeData {
int value;
int offset;
bool isThread;
NodeData(int i = 0) : isThread(false), value(i) {}
};
isThread是指这个节点是否是thread节点。如果一个节点是thread节点,那么说明它的left和right的值是我们在计算offset的时候临时改的,原本这两个值都应该是NULL。
template <typename T>
void removeThreadFromNode(T* node) {
if (node->data.isThread) {
node->data.isThread = false;
node->left = NULL;
node->right = NULL;
}
}
为了找到下一层的边界点,我们还需要定义一个名为Extreme的结构体,来记录当前子树形状的边界
template <typename TreeNode>
struct Extreme {
TreeNode* addr;
int off; // offset from root of subtree
int lev; // tree level
Extreme() : addr(NULL), off(0), lev(-1) {}
void init(TreeNode* n, int level) {
this->addr = n;
this->lev = level;
}
};
为了计算Extreme值,我们必须知道左右子树的Extreme的值。所以我们的calcOffset函数的定义就变成了这样:
/**
* param node [in] 当前节点
* param level [in] 当前节点的层数。根节点为第1层
* param leftMost [out] 以当前节点为根的子树的最下一层的右边界
* param rightMost [out] 以当前节点为根的子树的最下一层的左边界
*/
template <typename TreeNode>
void calcOffset(TreeNode* node, int level, Extreme<TreeNode>& rightMost,
Extreme<TreeNode>& leftMost);
当一个节点是叶节点时,它的Extreme值是显然的,最左端和最右端都是它自己,offset等于0。
如果不是叶节点,则根据左右子树来递归计算, 层高者胜
//calcOffset的代码段2
Extreme<TreeNode> ltreeRight; //左子树的最右端
Extreme<TreeNode> ltreeLeft; //左子树的最左端
Extreme<TreeNode> rtreeRight; //右子树的最右端
Extreme<TreeNode> rtreeLeft; //右子树的最左端
if (node->left) calcOffset(node->left, level + 1, ltreeRight, ltreeLeft);
if (node->right) calcOffset(node->right, level + 1, rtreeRight, rtreeLeft);
if (node->isLeaf()) {
// it is a leaf node
rightMost.init(node, level);
leftMost.init(node, level);
node->data.offset = 0;
return;
}
if (rtreeLeft.lev > ltreeLeft.lev || !node->left) {
leftMost = rtreeLeft;
leftMost.off += node->data.offset;
} else {
leftMost = ltreeLeft;
leftMost.off -= node->data.offset;
}
if (ltreeRight.lev > rtreeRight.lev || !node->right) {
rightMost = ltreeRight;
rightMost.off -= node->data.offset;
} else {
rightMost = rtreeRight;
rightMost.off += node->data.offset;
}
有了这些信息后,就可以用它来更新线索。
//calcOffset的代码段3
if (L && L != node->left) {
rtreeRight.addr->data.isThread = true;
rtreeRight.addr->data.offset =
std::abs((rtreeRight.off + node->data.offset) - LOFFSUM);
if (LOFFSUM - node->data.offset <= rtreeRight.off)
rtreeRight.addr->left = L;
else
rtreeRight.addr->right = L;
} else if (R && R != node->right) {
ltreeLeft.addr->data.isThread = true;
ltreeLeft.addr->data.offset =
std::abs((ltreeLeft.off + node->data.offset) - ROFFSUM);
if (ROFFSUM + node->data.offset >= ltreeLeft.off)
ltreeLeft.addr->right = R;
else
ltreeLeft.addr->left = R;
}
有点眼花了?我把以上三段代码合起来你再看看
/**
* param node
* param level current level of this node
* param leftMost the left most node on the lowest level of the subtree rooted by this node
* param rightMost the right most node on the lowest level of the subtree rooted by this node
*/
const int MINSEP = 1;
template <typename TreeNode>
void calcOffset(TreeNode* node, int level, Extreme<TreeNode>& rightMost,
Extreme<TreeNode>& leftMost) {
Extreme<TreeNode> ltreeRight; //左子树的最右端
Extreme<TreeNode> ltreeLeft; //左子树的最左端
Extreme<TreeNode> rtreeRight; //右子树的最右端
Extreme<TreeNode> rtreeLeft; //右子树的最左端
if (node->left) calcOffset(node->left, level + 1, ltreeRight, ltreeLeft);
if (node->right) calcOffset(node->right, level + 1, rtreeRight, rtreeLeft);
if (node->isLeaf()) {
// it is a leaf node
rightMost.init(node, level);
leftMost.init(node, level);
node->data.offset = 0;
return;
}
int cursep = MINSEP; // SEPARATION ON CURRENT LEVEL
int rootsep = MINSEP; // CURRENT SEPARATION AT this node
int LOFFSUM = 0; // OFFSET FROM L TO this node
int ROFFSUM = 0; // OFFSET FROM R TO this node
TreeNode* L = node->left;
TreeNode* R = node->right;
//每循环一次,L和R的层数都会加一
//所以跳出循环时谁不为NULL,说明谁更高
//每一次循环,两棵树只会分的越来越开,不会变得更近
//即,rootsep只增加,不减少
while (L && R) {
if (cursep < MINSEP) {
// push them apart until minimum separation
rootsep += (MINSEP - cursep);
cursep += MINSEP;
}
//左子树沿着右边界往下走
if (L->right) {
LOFFSUM += L->data.offset;
cursep -= L->data.offset;
L = L->right;
} else {
LOFFSUM -= L->data.offset;
cursep += L->data.offset;
L = L->left;
}
//右子树沿着左边界往下走
if (R->left) {
ROFFSUM -= R->data.offset;
cursep -= R->data.offset;
R = R->left;
} else {
ROFFSUM += R->data.offset;
cursep += R->data.offset;
R = R->right;
}
}
// SET THE OFFSET IN NODE T, AND INCLUDE IT IN
// ACCUMULATED OFFSETS FOR L AND R
//除以2向上取整,使得2*offset >= rootsep
node->data.offset = (rootsep + 1) / 2;
LOFFSUM -= node->data.offset;
ROFFSUM += node->data.offset;
// UPDATE EXTREME DESCENDANTS INFORMATION
// 层数高者胜
if (rtreeLeft.lev > ltreeLeft.lev || !node->left) {
leftMost = rtreeLeft;
leftMost.off += node->data.offset;
} else {
leftMost = ltreeLeft;
leftMost.off -= node->data.offset;
}
if (ltreeRight.lev > rtreeRight.lev || !node->right) {
rightMost = ltreeRight;
rightMost.off -= node->data.offset;
} else {
rightMost = rtreeRight;
rightMost.off += node->data.offset;
}
// if subtrees of t were of uneven heights, check
// to see if threading is necessary. at most one
// thread needs to be inserted
if (L && L != node->left) {
rtreeRight.addr->data.isThread = true;
rtreeRight.addr->data.offset =
std::abs((rtreeRight.off + node->data.offset) - LOFFSUM);
if (LOFFSUM - node->data.offset <= rtreeRight.off)
rtreeRight.addr->left = L;
else
rtreeRight.addr->right = L;
} else if (R && R != node->right) {
ltreeLeft.addr->data.isThread = true;
ltreeLeft.addr->data.offset =
std::abs((ltreeLeft.off + node->data.offset) - ROFFSUM);
if (ROFFSUM + node->data.offset >= ltreeLeft.off)
ltreeLeft.addr->right = R;
else
ltreeLeft.addr->left = R;
}
//非leaf node,offset必须大于0
assert(node->data.offset > 0);
}
用上述算法,再画前序遍历为{6,5,1,3,2,4,10,8,7,9,11}的二叉树,结果为:
This article is from: https://www.sunchangming.com/blog/post/4616.html
网友评论已有0条评论, 我也要评论