2진검색형트리] binary tree, insert & print for Web browser..

1)
2진트리를 검색용으로 구성하는 방법론은 알지만,

그 이전(?)에,
트리를 구성하고 표시하는 것을 만들어봐야겠다는 생각이 들더라구요.

...

2)

<div id=output120729_1 >&nbsp;</div>
<style>

/* for print TblE */
div#output120729_1 * td {
  vertical-align:top;

  border-style:solid;
  border-width:0px;
  border-color:gray;
  border-bottom-width:1px;
  border-bottom-color:red;
  }

div#output120729_1 * .right {
  text-align:right;
  }

div#output120729_1 * td.blank {
  border-bottom-color:gray;
  }


/* for printDvE */
div#output120729_1 {
  display:inline-block;

  font-size:10pt;
  }

div#output120729_1 * div {
  display:block;

  float:left; /* div size to freezing */

  border-style:solid;
  border-width:0px;
  border-color:gray;

  }

div#output120729_1 * .value {
  height:10pt;
  }

div#output120729_1 * .onLeft {
  margin-top:10pt;
  margin-right:2px; /* 상위Left와 연계표시 분리 */

  float:left;

  border-right-width:1px;
  border-right-color:gray; /* 상위Left 연계표시 */
  }

div#output120729_1 * .onRight {
  margin-top:10pt;
  margin-left:5px;
  margin-right:2px; /* 상위Right와 연계표시 분리 */

  border-top-width:1px;
  border-top-color:red;

  border-right-width:1px;
  border-right-color:yellow; /* 상위Right 연계표시 */
  }

</style>
<script>

(function() {

  // 스트링 연속처리용 모듈 추가
  String.prototype.replaceAll = function() {

    var ov = this,
        i, ar = arguments,
        arl = ar.length;

    for (i = 0; i < arl; i += 2) {
      ov = ov.replace(ar[i], ar[i + 1]);
    }

    return ov;
  }

  // 본문 시작

  var
  nil = undefined,
      preV = {
      l: nil,
      r: nil,
      v: null
      };

  /* tree 준비 (new 안써도 됨) */

  function newV() {
    if (this instanceof newV) return this;

    return new newV();
  }

  newV.prototype = preV; /* newV 선언 후 초기반환값 */


  /* 값 추가하기 */
  preV.insert = function(v) {

    var i, ar = arguments,
        arl = ar.length,
        p, q;


    for (i = 0; i < arl; i++) {
      ov = ar[i];

      if (!this.v) { // 값 지정해본 적이 없다면
        //    top=newV(); // 초기선언은 되어있어야 함수사용 가능하니 하지 말 것.
        this.v = ov;

        return this;
      }

      for (p = this; p.v != ov;) {
        if (p.v > ov) {
          q = p.l;
          if (!q) {
            q = newV();
            p.l = q;
            q.v = ov; // ending of for loop
          }
        } else { // p.v>ov
          q = p.r;
          if (!q) {
            q = newV();
            p.r = q;
            q.v = ov; // ending of for loop
          }
        }
        p = q;
      }

    }

    return p;
  }

  /* TblE 형식으로 출력하기 */
  preV.printTblE = function(p) {
    var ov;

    if (arguments.length < 1) p = this;
    if (!p) return '';

    return ('<'+'table><'+'tr><'+'td class=right colspan=2>{mid}</'+'td></'+'tr>'+
      '<'+'tr><'+'td {isleft}>{left}</'+'td><'+'td class=blank >&nbsp;</'+'td><'+'td {isright}>{right}</'+'td></'+'tr>'+
      '</'+'table>').replaceAll(
      '{mid}', p.v,
      '{isleft}', p.l ? 'class=blank' : '', '{left}', this.printTblE(p.l),
      '{isright}', p.r ? 'class=blank' : '', '{right}', this.printTblE(p.r)
      );
  }

  /* div 형식으로 출력하기 */
  preV.printDvE = function(p) {
    var ov;

    if (arguments.length < 1) p = this;
    if (!p) return '';

    return ('<'+'div>'+
      '<'+'div class=onLeft>{left}</'+'div><'+'div class=value>{mid}</'+'div><'+'div class=onRight>{right}</'+'div>'+
      '</'+'div>').replaceAll(
      '{left}', this.printDvE(p.l),
      '{mid}', p.v,
      '{right}', this.printDvE(p.r)
      );
  }

  // sample 시작..
  var top1 = newV(),
      top2 = newV(),
      i;

  for (i = 0; i < 50; i++) {

    //insert(49-i); // top이 기본값이 아니라서 무시.. 기존에 사용했던 모듈..
    top1.insert(parseInt(Math.random() * 50));
    top2.insert(49 - i);
  }

  // sample 표시..
  document.getElementById('output120729_1').innerHTML = '{top1TblE}<br style=clear:both; />{top1DvE}<br style=clear:both; >{top2TblE}<br style=clear:both; />{top2DvE}<br style=clear:both;>'.replaceAll(
    '{top1TblE}', top1.printTblE(), '{top1DvE}', top1.printDvE(),
    '{top2TblE}', top2.printTblE(), '{top2DvE}', top2.printDvE()
    );

}());

</script>

...

3)

 

-- 새 창에 보여주기.. --

...

4)
앞의 두개는 random 으로 입력한 이진트리이고
뒤의 두개는 역순으로 입력한 이진트리입니다.

random 과 역순으로 구성한 이진트리에서
먼저 나온 것은 table 을 이용했고, ( .printTblE )
뒤에 나온 것은 div 를 이용했죠. ( .printDvE )

...

5)
트리 입력구조는,

해당 트리의 값보다
작으면 l 쪽으로 추적하고, 
크면 r 쪽으로 추적해서 

추적될 값이 없으면 해당 자리에 값을 추가하는 형식으로 만들었습니다. 
(검색용이므로, 중복되는 값은 입력 무시합니다..)

함수 (=newV) 의 prototype 에 기본값 object (=preV) 를 지정해서
l, r, v 초기값을 미리 지정해두고,

해당 prototype object 에 함수를 지정해서,
이후 같은 함수에서 생성될 object 에도 적용할 수 있도록 구성했습니다.

newV 라는 함수에 ( this instanceof newV ) 라는 부분을 추가해서
new 기능을 따로 입력하지 않도록 했구요..

* instanceof 참고*
JavaScript Patterns ISBN 978-89-6626-015-7 
http://cyw.do/03s86 
3.3 new 를 강제하는 패턴 

...

6)
트리 표시구조는,

TblE 에서는 border 와 text-align 을 이용한 표시적용했습니다.
table 의 특성상, 화면 가로표시범위가 작아진다고 해도, 내용물까지 작아지지는 않습니다.

DvE 에서는 border 와 float:left 을 이용한 표시를 적용했죠.

text-align 과 float:right 는 적용하지 못했는데요,
공간의 좌우 전체를 먼저 차지하려고 해서, 쓰지 않는 방법으로 진행했습니다. (IE8)

float:left 의 특성을 빌려,
화면 좌우크기가 표시범위보다(?) 작으면, 다음줄(?)을 이용하려 합니다만,

좌우에 있는 공간을 최대한 활용하려다보니,
세로 길이가 비이성적으로(?) 길어지는 효과가 있더라구요.

가능하다면, div 들 세로길이를 추적해서 style=clear:both 를 먹이(?)고 싶습니다만,
= =;.. 방법 찾을 생각은 못하겠네요.

만들어진 테이블을 가지고 일일이 적용하는 방법 외에는 없을 것 같습니다.

...

6)
그런데,

.. 새 창에 적용시켜보면,
역순 표시한 내용의 table 쪽 갯수가 적게 나오는데요, (IE8)
div 쪽도 비교적(?) 적게 나오더라구요.

블로그에 표시된 내용에서는 그렇게 안나오는데..
브라우져 기본 심도를 어떻게 해결한건지 잘 모르겠군요..

...

easyBow killofki@.