PHP实现完全二叉树

布满荆棘的人生 2022-09-21 15:19 105阅读 0赞

若设二叉树的深度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树。

![Center][]

PHP代码实现（暂时实现添加节点、层次遍历节点，删除节点后续更新）

<?php
    
    class Node{
    
    	public $value;
    	public $leftNode;
    	public $rightNode;
    
    }
    
    /* 找到空节点 */
    function findEmpytNode($node, $parent = null){
    	if(empty($node->value)){
    		return $node;
    	}else{
    		if(empty($node->leftNode->value)){
    			return $node->leftNode;
    		}else if(empty($node->rightNode->value)){
    			return $node->rightNode;
    		}else{
    			if(empty($parent) || $node->value == $parent->rightNode->value){
    				return findEmpytNode($node->leftNode, $node);
    			}else{
    				return findEmpytNode($parent->rightNode, $node);
    			}
    		}
    	}
    }
    
    /* 添加节点 */
    function addNode($node, $value){
    	$emptyNode = findEmpytNode($node);
    	setNode($emptyNode, $value);
    }
    
    /* 设置节点 */
    function setNode($node, $value){
    	$node->value = $value;
    	$node->leftNode = new Node();
    	$node->rightNode = new Node();
    }
    
    /* 打印 */
    function printTree($node, $parent = null){
    	if(empty($node->value)) return ;
    	echo $node->leftNode->value;
    	echo $node->rightNode->value;
    	if(empty($parent) || $node->value == $parent->rightNode->value){
    		printTree($node->leftNode, $node);
    	}else{
    		printTree($parent->rightNode, $node);
    	}
    }
    
    $head = new Node();
    setNode($head, 1);
    addNode($head, 2);
    addNode($head, 3);
    addNode($head, 4);
    addNode($head, 5);
    addNode($head, 6);
    
    printTree($head);

[Center]: /images/20220721/41c5e80067cf43e085cc39595299e2a8.png