[자료구조] 트리구현

 

DFS,BFS 공부하기전에 기초가되는 트리구조를 어떻게 구현할 지 생각해 보았다.

답지를 보면 더 빠르겠지만 제대로 된 이해를 하지 못할것 같아서 먼저, 혼자 생각한다음에 트리를 구현해보록 했다.

자바에 익숙해져서 그런지 객체로 구현하는 것이 습관이 되어서 , 비록 자바스크립트이지만 class를 사용하여 객체들만의 특성을 생각하여 변수를 부여하였다.

일단 구현은 했는데,,, 맞는지 검증하는 과정을 더 생각해보아야겠다

 

 

 

class Tree{

        _masterNode;

        _nodes = [];

        _values = [];

        constructor(nowValue , values){

            this._values = values;

           this. _masterNode = new Node(nowValue,0,values,null,this._nodes);

        }

 

        showLeaf(){

            const _leafs = this._nodes.filter(node=> node._depth == this._values.length-1);

 

            _leafs.forEach(node=>{

                let _leaf = node;

 

                node.process = [];

                node.process.push(node._value);

                while(_leaf._parent != null){

                    _leaf = _leaf._parent;

                    node.process.push(_leaf._value);

                }

                node.process = node.process.reverse();

            });

 

            console.log(_leafs);

        }

    }

 

    class Node{

        _value = 0;

        _childs = [];

        _parent = null;

        _depth = 0;

        constructor(value,depth,values,parent,_nodes){

            const _values = [].concat(values);

            this._value = value;

            this._parent = parent;

            this._depth = parent != null ? parent._depth+1 : 0;

            _values.splice(_values.indexOf(value),1);

            arrayDuplicationDelete(_values).forEach((_value,index)=>{

                this._childs.push(new Node(_value,this,_values,this,_nodes));

            })

            _nodes.push(this);

        }

 

        pushChild(child){

            this._childs.push(child);

        }

    }

    function alorism(){

        const TEST_VALUES = [1,2,2,3,4,5];

        const DUPLICATE_DELETE_VALUES = arrayDuplicationDelete(TEST_VALUES);

        const trees = [];

 

        DUPLICATE_DELETE_VALUES.forEach((value,index)=>{

            const _tree = new Tree(value,TEST_VALUES);

            trees.push(_tree);

        });

 

        trees.forEach(tree=>{

            tree.showLeaf();

        })

    }

 

    alorism();

 

    function arrayDuplicationDelete(_array){

        const _result = [];

        _array.forEach(value=>{

            if(!_result.includes(value)){

                _result.push(value);

            }

        });

        return _result;

    }