@blog.justoneplanet.info

日々勉強

二分木(Binary Tree)

全ての接点(ノード)が左と右の子を持つ事ができる。

■Node

まずはノードを定義(二分木用)。

function Node(key, element){
    this._key        = key;
    this._parentNode = null;
    this._lChildNode = null;
    this._rChildNode = null;
}
Node.prptotype = {
    "getKey" : function(){
        return this._key;
    },
    "hasParent" : function(){
        return (this._parentNode != null);
    },
    "getParent" : function(){
        return this._parentNode;
    },
    "setParent" : function(element){
        this._parentNode = element;
    },
    "isEmpty" : function(){
        return ((this._lChildNode == null) && (this._rChildNode == null));
    },
    "hasLeftChild" : function(){
        return (this._lChildNode != null);
    },
    "hasRightChild" : function(){
        return (this._rChildNode != null);
    },
    "getLeftChild" : function(){
        return this._lChildNode;
    },
    "getRightChild" : function(){
        return this._lChildNode;
    },
    "setLeftChild" : function(element){
        this._lChildNode = element;
    },
    "setRightChild" : function(element){
        this._lChildNode = element;
    }
}

なるほど!

■二分木

ノードを利用して二分木を定義。

function BinaryTree(){
    this._root = new Node(null, null);
}
BinaryTree.prototype = {
    "isEmpty" : function(){
        return (this._root.getKey() == null);
    },
    "isRoot" : function(node){
        return (this._root == node);
    },
    "getRoot" : function(){
        return this._root;
    },
    "replaceRoot" : function(node){
        this._root = node;
    },
    "hasParent" : function(node){
        return (node.hasParent());
    },
    "getParent" : function(node){
        return node.getParent();
    },
    "setParent" : function(node, element){
        return node.setParent(element);
    },
    "isEmpty" : function(node){
        return node.isEmpty();
    },
    "hasLeftChild" : function(node){
        return node.hasLeftChild();
    },
    "hasRightChild" : function(node){
        return node.hasRightChild();
    },
    "getLeftChild" : function(node){
        return node.getLeftChild();
    },
    "getRightChild" : function(node){
        return node.getRightChild();
    },
    "setLeftChild" : function(node, element){
        return node.setLeftChild(element);
    },
    "setRightChild" : function(node, element){
        return node.setRightChild(element);
    }
}

デザインパターンでいうところのadapterパターンだ。

参考

コメントはまだありません»

No comments yet.

RSS feed for comments on this post.TrackBack URL

Leave a comment