用 C++ 打印所有从根节点到子节点的路径以及其相对位置

针对本问题，我们给定了一棵二叉树。我们需要打印从树的根节点到子节点的所有路径。同时，使用下划线“_”表示节点的相对位置。

让我们用一个示例来更好地理解这个主题 −

输入 −

输出 −

_ _ 3
_ 9
1
_3
9
_7
3
_ 4
_ _ 2
3
9 4
1 7 6 2
3
_ 4
6

为了解决这个问题，我们将利用树的元素的垂直顺序概念。

基于这个概念，我们将打印从根节点到子节点的路径。

算法

Step 1: Traverse the binary tree using preorder traversal. And on traversal calculate the horizontal distance based on the order. The horizontal distance of root is 0 and processed as the above diagram.
Step 2: And on traversing to the leaf node, print the path with an underscore “_” at the end.

示例

 实时演示

#include<bits/stdc++.h>
using namespace std;
#define MAX_PATH_SIZE 1000
struct Node{
   char data;
   Node *left, *right;
};
Node * newNode(char data){
   struct Node *temp = new Node;
   temp->data = data;
   temp->left = temp->right = NULL;
   return temp;
}
struct PATH{
   int horizontalDistance;
   char key;
};
void printPath(vector < PATH > path, int size){
   int minimumhorizontalDistance = INT_MAX;
   PATH p;
   for (int it=0; it<size; it++){
      p = path[it];
      minimumhorizontalDistance = min(minimumhorizontalDistance, p.horizontalDistance);
   }
   for (int it=0; it < size; it++){
      p = path[it];
      int noOfUnderScores = abs(p.horizontalDistance -minimumhorizontalDistance);
      for (int i = 0; i < noOfUnderScores; i++) cout<<"_ ";
         cout<<p.key<<endl;
   }
   cout<<"\nNext Path\n";
}
void printAllRtLPaths(Node *root, vector < PATH > &AllPath, int horizontalDistance, int order ){
   if(root == NULL)
      return;
   if (root->left == NULL && root->right == NULL){
      AllPath[order] = (PATH { horizontalDistance, root->data });
      printPath(AllPath, order+1);
      return;
   }
   AllPath[order] = (PATH { horizontalDistance, root->data });
   printAllRtLPaths(root->left, AllPath, horizontalDistance-1, order+1);
   printAllRtLPaths(root->right, AllPath, horizontalDistance+1, order+1);
}
void printRootToLeafPath(Node *root){
   if (root == NULL)
      return;
   vector<PATH> Allpaths(MAX_PATH_SIZE);
   printAllRtLPaths(root, Allpaths, 0, 0);
}
int main(){
   Node *root = newNode('3');
   root->left = newNode('9');
   root->right = newNode('4');
   root->left->left = newNode('1');
   root->left->right = newNode('7');
   root->right->left = newNode('6');
   root->right->right = newNode('2');
   printRootToLeafPath(root);
   return 0;
}

输出

_ _ 3
_ 9
1
Next Path
_ 3
9
_ 7
Next Path
3
_ 4
6
Next Path
3
_ 4
_ _ 2

sudhir sharma

更新日期： 17-Jan-2020

114 次浏览

开启你的职业

通过完成课程获得认证

开始