php-struct_searchtree

class node{	public $value;	public $left;	public $right;	public $parent;	public function __construct($data){		$this->value = $data;	}}class searchtree{	public $root = null;	public $size = 0;	public $depth = 0;	publi本@文来源[email protected]搞@^&代*@码网(搞代gaodaima码c function __construct($value){		$this->root = new node($value);		$this->size++;		$this->depth++;	}	public function addnode($array){		foreach ($array as $key=> $value) {			$current = $this->root;			$parent = null;			$currentdepth = 1;			while($current !== null){				$parent = $current;				if($current->value == $value){					continue 2;				}				elseif($current->value > $value){					$current = $current->left;				}else{					$current = $current->right;				}				$currentdepth++;			}			$node = new node($value);			$node->parent = $parent;			if($parent->value > $value){				$parent->left = $node;			}else{				$parent->right = $node;			}			if($this->depth depth++;			}			$this->size++;		}				return true;	}	public function successor($node){		if ($node->right !== null) {			$current = $node->right;			while($current->left !== null){				$current = $current->left;			}        	return $current;	    }	    $parent = $node->parent;	    while ($parent !== null && $node = $parent->right) {	        $node = $parent;	        $parent = $parent->parent;	    }    	return $parent;	}	public function delnode($value) {		$node = $this->search($value);		if ($node->left === null || $node->right === null) { 			#如果待删除结点无子节点或只有一个子节点，则c = dnode		    $current = $node;		} else { 			#如果待删除结点有两个子节点，c置为dnode的直接后继，以待最后将待删除结点的值换为其后继的值		    $current = $this->successor($node);		}		//print_r($current->value);exit;		if ($current->left !== null) {		    $s = $current->left;		} else {		    $s = $current->right;		}		if ($s !== null) { #将c的子节点的父母结点置为c的父母结点，此处c只可能有1个子节点，因为如果c有两个子节点，则c不可能是dnode的直接后继		    $s->parent = $current->parent;		}		if ($current->parent === null) { #如果c的父母为空，说明c=dnode是根节点，删除根节点后直接将根节点置为根节点的子节点，此处dnode是根节点，且拥有两个子节点，则c是dnode的后继结点，c的父母就不会为空，就不会进入这个if		    $this->root = $s;		} else if ($current == $current->parent->left) { #如果c是其父节点的左右子节点，则将c父母的左右子节点置为c的左右子节点		    $current->parent->left = $s;		} else {		    $current->parent->right = $s;		}		#如果c!=dnode，说明c是dnode的后继结点，交换c和dnode的key值		if ($current != $node) {		    $node->value = $current->value;		}		#返回成功		return true;	}	public function search($value){		$current = $this->root;		while($current !== null){			if($current->value == $value){				return $current;			}			elseif($current->value > $value){				$current = $current->left;			}else{				$current = $current->right;			}		}		return false;	}}$tree = new searchtree(300);$tree->addnode(array(124,360,250,110,260,270,160,350,370,320,352));$tree->delnode(300);print_r($tree);

以上就介绍了php-struct_searchtree，包括了方面的内容，希望对PHP教程有兴趣的朋友有所帮助。

喜欢 (0)赏

[搞代码]

分享 (0)