scripts/binaryTree.php at master · jwcn/scripts · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
<?php

Class Node
{
	public $data = null;
	protected $leftNode = null;
	protected $rightNode = null;
	protected $parentNode = null;

	public function __construct ($value) {
		$this->data = $value;
	}

	public function setLeft($node) {
		$this->leftNode = $node;
		$node->setParent($this);
	}

	public function getLeft() {
		return $this->leftNode;
	}

	public function setRight($node) {
		$this->rightNode = $node;
		$node->setParent($this);
	}

	public function getRight() {
		return $this->rightNode;
	}

	public function setParent($node) {
		$this->parentNode = $node;
	}

	public function getParent() {
		return $this->parentNode;
	}
}

Class Tree
{
	public static function insert($root, $node) {
		if ($node->data < $root->data) {
			if ($root->getLeft()) {
				self::insert($root->getLeft(), $node);
			} else {
				$root->setLeft($node);
			}
		} else {
			if ($root->getRight()) {
				self::insert($root->getRight(), $node);
			} else {
				$root->setRight($node);
			}
		}
	}

	public static function find($root, $value) {
		if ($value < $root->data) {
			return self::find($root->getLeft(), $value);
		} else if ($value > $root->data) {
			return self::find($root->getRight(), $value);
		} else {
			return $root;
		}
	}

	public static function findMin($root) {
		if ($root->getLeft()) {
			return self::findMin($root->getLeft());
		}

		return $root;
	}

	public static function findMax($root) {
		if ($root->getRight()) {
			return self::findMax($root->getRight());
		}

		return $root;
	}
}

$root = new Node(20);
Tree::insert($root, new Node(15));
Tree::insert($root, new Node(22));
Tree::insert($root, new Node(13));
Tree::insert($root, new Node(18));

var_dump($root);
// var_dump(Tree::find($root, 13));exit;
// var_dump(Tree::findMin($root));
// var_dump(Tree::findMax($root));