Алгоритм обхода дерева

[Profic]

Алгоритм обхода дерева

Вопрос к гуру, хоть и к PHP отношения не имеет, но все-же очень надеюсь на помощь

Делаю динамическое дерево, вот возникла необходимость расширить класс для возможности изменеия статуса у каждого элемента. Отображение, изменение статуса - все работает хорошо, но вот встрял с алгоритмом обхода дерева для получения собирательного статуса всего дерева.

Каждый элемент дерева имеет следующие свойства:
treeNode.dtState - статус (0 начальный статус; -1 означает, что у какого-то из парентов статус > 0, а текущий находится в положении 0)
treeNode.dtOpened - указывает открыта ли ветвь
treeNode.dtChild - указывает, если ли дети (если нет, то это лист)
treeNode.id - уникальный идентификатор елемента

Само дерево есть пачка <p>, заключенных в <div>, который соответственно append-иться к парентному <p>.

Нужно: обойти дерево таким образом, чтобы в результате получился список элементов по такому принципу:
1) если элемент имеет имеет статус > 0, и ни у кого из парентов нет статуса > 0, то добавить в список положительных
2) если элемент имеет статус отличный от статуса парента, то добавить в список в зависимоти от статуса парента.

Пример: из такого дерева (отмеченные обозначаются =, неотмеченные – |)

Дерево | id | статус
|      | 1  |  0
 =     | 2  |  1
  |    | 3  | -1
   |   | 4  | -1
   =   | 5  |  1
  =    | 6  |  1
  =    | 7  |  1
   =   | 8  |  1
   |   | 9  | -1
  =    | 10 |  1
  =    | 11 |  1
 |     | 12 |  0
 |     | 13 |  0
|      | 14 |  0
|      | 15 |  0

должно получиться, что-то типа:
+2, -3, +5, -9
порядок, в принципе, не важен, т.к. потом это будет использоваться в запросе к базе.
Вот текущаяя реализация:

dynTreeState.prototype.stateGet = function () {
 var loopArr = new Array ();
 var loopObj = null;
 var loopState = 0;
 var loopStates = new Array ();
 for (var i = 1; i < this.stateImages.length; i++) {
  loopStates[i] = new Array ();
 } // for
 var stateChanged = false;
 loopArr.push (this.treeObject.lastChild);
 while (loopArr.length) {
  loopObj = loopArr.pop ();
  for (var i = 0; i < loopObj.childNodes.length; i++) {
   var curObj = loopObj.childNodes[i];
   if (curObj.dtChild == undefined) continue;
   if (curObj.dtOpened && loopObj.parentNode.id == this.treeObject.id && curObj.dtState > 0) {
    loopStates[curObj.dtState].push ('+' + curObj.id);
   } // if
   if (!curObj.dtOpened && loopObj.dtState == undefined && curObj.dtState > 0) {
    loopStates[curObj.dtState].push ('+' + curObj.id);
   } // if
   if (loopObj.dtState != undefined && curObj.dtState != loopObj.dtState) {
    loopStates[loopObj.dtMainState].push ((loopObj.dtState > 0 ? '-' : '+') + curObj.id);
   } // if
   if (curObj.dtOpened && curObj.dtState > 0) {
    curObj.lastChild.dtMainState = curObj.dtState;
   } else if (curObj.dtOpened) {
    curObj.lastChild.dtMainState = loopObj.dtMainState;
   } // if
   if (curObj.dtOpened) {
    curObj.lastChild.dtState = curObj.dtState;
    loopArr.push (curObj.lastChild);
   } // if
  } // for
  loopObj.dtState = undefined;
  loopObj.dtMainState = undefined;
 } // while
 var resultArray = new Array ();
 for (var i = 1; i < this.stateImages.length; i++) {
  resultArray[i] = '{' + i + ':' + loopStates[i].join (',') + '}';
 } // for
 var result = '';
 result = resultArray.join (';');
 alert (result);
 return result;
} // function

Делает то, что нужно (на выходе получам, что-то типа "{1:+1,-40};{2:+610,-611,+613,-614}", но как-то, по моему мнению, ну очень громоздко и ненаглядно (лично я не понимаю алгоритм работы этого кода, хотя сам же его и написал )
Нет ли другого способа сделать тоже самое, только меньшими жертвами и более понятно, что ли?

ЗЫ. Если есть вопросы, задавайте - отвечу.

 

[Profic]

Хм, молчание знак согласия.
Что данный алгоритм является самым оптимальным? Неверю. Чую, что есть более оптимальное решение, но найти его пока не могу

 

[Profic]

Хех, спасибо за молчание
Для тех кто интересуется, вот вариант который у меня получился после мозгового штурма

dynTreeState.prototype.stateGet = function () {
 var states = new Array ();
 var state = null;

 var treeWalkState = function (treeNode) {
  for (var i = 0; i < treeNode.childNodes.length; i++) {
   var curNode = treeNode.childNodes[i];
   var parentState = (treeNode.parentNode ? treeNode.parentNode : treeNode).dtState;
   if (parentState != curNode.dtState) {
    (parentState ? state.idsNeg : state.idsPos).push (curNode.id);
   } // if
   if (curNode.dtNodeStatus & dtNodeOpened) treeWalkState (curNode.lastChild);
  } // for
  if (treeNode.dtState != undefined) treeNode.dtState = undefined;
 } // function

 var treeWalk = function (treeNode) {
  for (var i = 0; i < treeNode.childNodes.length; i++) {
   var curNode = treeNode.childNodes[i];
   var treeSubNode = null;
   if (curNode.dtNodeStatus & dtNodeOpened) {
    treeSubNode = curNode.lastChild;
   } else if (!(curNode.dtNodeStatus & dtNodeOpened) && (curNode.dtNodeStatus & dtNodeCached)) {
    treeSubNode = curNode.dtNodeCache;
    treeSubNode.dtState = curNode.dtState;
   } // if
   if (curNode.dtState) {
    state = {state : curNode.dtState, idsPos : [curNode.id], idsNeg : []};
    if (treeSubNode) treeWalkState (treeSubNode);
    states.push (state);
    state = null;
   } else if (treeSubNode) {
    treeWalk (treeSubNode);
   } // if
  } // for
 } // function

 treeWalk (this.treeObject.lastChild);
 alert (dumpVarForEval (states) + '\n' + states);
 return states;
} // function

Согласитесь, намного более понятный, чем первый