排序通過節點列表，它具有二維特性

這是我的節點類排序通過節點列表，它具有二維特性

public class Node 
{ 
    int Data= -1; 
    int X; 
    int Y; 
    Node LeftChild = null; 
    Node RightChild = null; 
    Node(int i) 
    { 
     this.Data = i; 
    } 
}

這是我的序遍歷代碼：

public static void inorder(Node current, int horiz_dist, int verti_dist) 
{ 
    if(current == null) 
     return; 
    inorder(current.LeftChild, ++horiz_dist, ++verti_dist); 
    horiz_dist--; 
    verti_dist--; 
    System.out.println("Node "+current.Data+": X = "+horiz_dist+", Y = "+verti_dist); 
    current.X = horiz_dist; 
    current.Y = verti_dist; 
    node_list.add(current); 
    inorder(current.RightChild, --horiz_dist, ++verti_dist); 
    horiz_dist++; 
    verti_dist--; 
}

我有節點的列表是我從迭代得到Inorder遍歷中的二叉樹。以下是該遍歷輸出：

節點18：X = 3，Y = 3

節點7：X = 2，Y = 2

節點5：X = 1，Y = 1

節點12：X = 1，Y = 3

節點9：X = 0，Y = 2

節點13：X = -1，Y = 3

節點6：X = 0，Y = 0

節點8：X = -1，Y = 1

節點10：X = -2，Y = 2

節點15： X = -3，Y = 3

欲所有節點基於X第一（遞減順序）然後Y（增加的順序）進行排序，並。其中X和Y分別是距根節點的距離。這樣最終輸出將是：

節點18：X = 3，Y = 3

節點7：X = 2，Y = 2

節點5：X = 1，Y = 1

節點12：X = 1，Y = 3

節點6：X = 0，Y = 0

節點9：X = 0，Y = 2

節點8：X = -1，Y = 1

節點13：X = -1，Y = 3

節點10：X = -2，Y = 2

節點15 ：X = -3，Y = 3

編輯：這是我比較邏輯。我更新了它。現在，它的工作

This is comparator logic I wrote:

`Collections.sort（node_list，新的比較（）{

 public int compare(Node second, Node first) 

     { 

      if(first.X > second.X) 
       return 1; 
      else if(first.X < second.X) 
       return -1; 
      else if(first.X == second.X) 
      { 
       if(first.Y < second.Y) 
        return 1; 
       else if(first.Y > second.Y) 
        return -1; 
       else if(first.Y == second.Y) 
        return 0; 
      } 
      return 0; 
     } 
    });`

來源

2015-05-19 Nikhil Redij

當我意識到我誤解了這個問題時，我收回了答案。對於那個很抱歉！但是你可以使用ArrayList :: sort，因爲我認爲你正在使用Java和自定義比較器。這是您最簡單的解決方案。然而，如果這是一個家庭作業解決方案，因爲你在這裏推出自己的BST，那麼這種遍歷所需要的就是一個隊列。你不能遞歸地使用你的標準預定/ inorder /後序遍歷，因爲我們需要一次遍歷一個「行」樹。這些遞歸算法總是深入到樹葉而不是在「行」中處理。 –

因此，如果您想要在不依賴於單獨的排序算法的情況下執行此操作，則必須逐行處理您的樹，從左到右（或從右到左，下降X順序），頂到-底部。爲了做到這一點，你需要從右到左的「階段」中遍歷樹的每一行，並推送到隊列中。或者，如果您使用兩個隊列，一個用於「當前行」，另一個用於「下一行」，則更容易。然後交換隊列當當前變成空的，並重復，直到兩個都是空的。 –

您可以使用std ::某種自定義的比較函數。

讓說你有節點std::vector<Node> vec矢量然後，你可以用它像這樣

std::sort(vec.begin(), vec.end(), compare);

其中compare定義如下

bool compare(Node a, Node b) 
{ 
    if (a.X > a.X) return true; 
    if (a.Y > a.Y) return true; 
}

運行時間該算法O(n*log(n))

來源

2015-05-19 15:56:54

你可以顯示std :: sort的例子嗎？我不熟悉方法。需要多少時間。通常，對於二維比較，它將進入O（N^2）時間。我想知道它是否可以在O（N * logN）時間內完成。 –

編輯答案 –

唷，讓我們再試一次，因爲我最初誤解了這個問題。由於您的整個目標是通過樹遍歷來分配這些X/Y值，所以首先是壞消息：

遞歸算法在這裏不起作用。

無論您使用的是有序還是預定序或者後序遍歷，所有這些算法都會分崩離析，因爲他們想以遞歸的方式以堆棧式的LIFO方式向下挖掘葉子（遞歸像LIFO結構一樣使用調用堆棧）。如果你想以一種先排序然後X排序的方式輸出，那麼它們會很好，但是不會相反。首先做X是相當棘手的。

僞碼的解決方案：

List<Node> current_row; 
List<Node> next_row; 

root_node.x = 0; 
root_node.y = 0; 
current_row.push(root_node); 

// Right-to-Left, Top-to-Bottom 
while (!current_row.empty()) 
{ 
    do 
    { 
     Node node = current_row.pop(); 
     // output node data 

     if (node.right_child) 
     { 
      node.right_child.x = node.x + 1; 
      node.right_child.y = node.y + 1; 
      next_row.push(node.right_child); 
     } 

     if (node.left_child) 
     { 
      node.left_child.x = node.x - 1; 
      node.left_child.y = node.y + 1; 
      next_row.push(node.left_child); 
     } 
    } while (!current_row.empty()); 
    current_row.swap(next_row); 
}

你也可以在這裏使用一個隊列，但我認爲這種「基於行的」的心態可以幫助你多一點初步瞭解發生了什麼事情。

來源

2015-05-19 16:55:57

排序通過節點列表，它具有二維特性

回答

相關問題