Прямая нарезка двоичного дерева

Question

У меня чертовски время, пытаясь понять это. Всюду, где я смотрю, я, кажется, только натолкнулся на объяснения того, как фактически переходить через список нерекурсивно (часть, которую я действительно понимаю). Может ли кто-нибудь там забивать, как именно я могу сначала пройти список и найти фактические узлы-предшественники/преемники, чтобы я мог их отмечать в классе узлов? Мне нужно создать простое двоичное дерево поиска и просмотреть список и перенаправить нулевые ссылки на предшественника/преемника. У меня было немного удачи с раствором несколько, как следующее:

thread(node n, node p) { 
    if (n.left !=null) 
     thread (n.left, n); 
    if (n.right !=null) { 
     thread (n.right, p); 
    } 
    n.right = p; 
} 

Answer 1

Из вашего описания, я предполагаю, что у вас есть узел со структурой ищет что-то вроде:

Node { 
    left 
    right 
} 

... и что у вас есть двоичное дерево из этих настроек, используя левое и правое, и что вы хотите повторно назначить значения слева и справа, чтобы он создавал двусвязный список из первого пересечения дерева по глубине.

Проблема с корнем (без каламбур) с тем, что у вас есть до сих пор, заключается в том, что «узел p» (короткий для предыдущего?), Который передается во время обхода, не зависит от того, где в дереве, которое вы в настоящее время - всегда нужно содержать ранее посещаемый узел. Чтобы сделать это, каждый раз, когда выполняется поток, он должен ссылаться на ту же «предыдущую» переменную. Я сделал некоторый псевдо-код Python-ish с одним C-ism - если вы не знакомы, «&» означает «ссылка на» (или «ref» на C#), а «*» означает «разыменование и дайте мне объект, на который он указывает ».

Node lastVisited 
thread(root, &lastVisisted) 

function thread(node, lastVisitedRef) 
    if (node.left) 
    thread(node.left, lastVisitedRef) 
    if (node.right) 
    thread(node.right, lastVisitedRef) 

    // visit this node, reassigning left and right 
    if (*lastVisitedRef) 
    node.right = *lastVisitedRef 
    (*lastVisitedRef).left = node 
    // update reference lastVisited 
    lastVisitedRef = &node 

Если вы собираетесь осуществить это в C, вы на самом деле должны были бы двойной указатель содержать ссылку, но идея та же - вы должны сохраняться местоположение «последней посещенной узел» во время всего обхода.