绘制二叉树

最近我在学习二叉树相关的很多算法,于是我就在想,能不能把二叉树画出来看看。

比如下图这样:

image1

问题的细化

我们想要在一个平面的画布上绘图,比如一个800像素x600像素的bitmap。首先把这个画布切成一个个正方形的格子(tile)。每个格子的大小比如是20x20。每个格子里面只放一个二叉树节点。我们需要寻找一个算法,给二叉树的每个节点计算出一个(x,y)的值,来对应我们画好的格子。

image2

一旦把(x,y)的值确定下来,剩下就是画圆圈、画线的工作了,就简单多了。

那么依据什么规则来确定x,y的值呢?

  1. Trees impose a distance on the nodes; no node should be closer to the root than any of its ancestors.
  2. 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.
  3. The relative order of nodes on any level should be the same as in the level order traversal of the tree.
  4. For a binary tree, a left child should be positioned to the left of its parent and a right child to the right.
  5. A parent should be centred over its children.
  6. 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}的二叉搜索树,结果为:

image3

用这样的算法,画前序遍历为{6,5,1,3,2,4,10,8,7,9,11}的二叉搜索树,结果为:

image4

这样有两个问题

  1. 父节点并没有位于子节点的中心
  2. 太宽了,浪费纸张。我们希望在满足那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计算出来(怎么实现稍后讲)。

image5

有了相对偏移之后,我们很容易把它变成绝对坐标。我们假设根节点的横坐标为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这个字段里。

image6
但是这样有个问题,计算出来的横坐标有正有负。这非常不利于绘图,因为一般来说,坐标值都是正的。

那么,我们其实只需要找到横坐标最小(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;
  });
}

image7
为了找到横坐标最小的节点,非得遍历所有节点吗?能不能更快速的找到最左边那个节点?这个我想了很久,稍后讨论。

求解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;

不是。请看下图

image8
解决办法是像线索二叉树一样,加入线索边。

image9
即,如果一个叶节点不在最下面一层,那么它会变成一个线索节点,它的左右指针会被用于指向下一层的边界点。于是我们的节点定义就变成了这样:

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}的二叉树,结果为:

image10

此博客中的热门博文

少写代码,多读别人写的代码

在windows下使用llvm+clang

tensorflow distributed runtime初窥