引线的练习实作

规则

为达到节省叶节点指向NULL的空间浪费

说明

• 1.在建立节点的同时，设置左右引线布林值为Ture。
• 2.当节点有向下的子节点，将该位置引线值改为false。
• 3.先利用中序追踪，建立阵列。
• 4.从根节点开始向下追踪，遇到布林值为Ture时跳过，表示为引线节点。
• 5.在实线节点时判断左右分支是否为引线节点，若是则将中序阵列的前後位置存入分支。

函式

void print(tree_p root) {
  printf("\n---------------------------------\n");
  printf("\nInorder:\n");
  new_search(root);
  inorder(root);
}

void inorder(tree_p root) {
  if (root != NULL) {
    if(root->t_left==false){
      inorder(root->left);
    }
    show_line(root);
    if (root->t_right == false) {
      inorder(root->right);
    }
  }
}

void show_line(tree_p point) {
  printf("\n----------%d----------", point->data);
  get_L(point);
  get_R(point);
}

结果

原树示意图:

结果显示:

LR为0表示该分支存在连接节点

LR为1表示该分支为NULL，於是引线连接回去