二叉树节点查找与删除

发表于 | 分类于

在上一篇关于二叉树的js实现的基础上，增加二叉树节点查找与删除操作。

代码如下：

注意：接口写在BinaryTree()中，部分代码已省略

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
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
function BinaryTree(){
    //...
    
    //最小值查找
	this.min = function(){
		return minNode(root);
	}

	function minNode(node){
		if (node) {
			while(node && node.left !== null){
				node = node.left;
			}
			return node.text;
		}

		return null;
	}


	//最大值查找
	this.max = function(){
		return maxNode(root);
	}

	function maxNode(node){
		if (node) {
			while(node && node.right !== null){
				node = node.right;
			}

			return node.text;
		}

		return null;
	}


	//判断某值是否存在
	this.search = function(text){
		return searchNode(root,text);
	}

	function searchNode(node,text){
		if (!node) {
			return false;
		}else if(text>node.text){
			return searchNode(node.right,text);
		}else if(text<node.text){
			return searchNode(node.left,text)
		}else{
			return true;
		}
	}



	//删除节点
	this.remove = function(text){
		root = removeNode(root,text);
	}

	function removeNode(node,text){
		if (node === null) {
			return null;
		}

		if (text<node.text) {
			node.left = removeNode(node.left,text);
			return node;
		}else if (text>node.text) {
			node.right = removeNode(node.right,text);
			return node;
		}else {
			if (node.left === null && node.right === null) {
				node = null;
				return node;
			}
			if (node.left === null) {
				node = node.right;
				return node;
			}else if (node.right === null) {
				node = node.left;
				return node;
			}

			var aux =findMinNode(node.right);
			node.text = aux.text;
			node.right = removeNode(node.right,aux.text);
			return node;
		}
	}

	function findMinNode(node){
		if (node) {
			while(node && node.left !== null){
				node = node.left;
			}

			return node;
		}
		return null;
	}
    
    //...

}
	
	
//查找最小值
//console.log(binaryTree.min());

//查找最大值
//console.log(binaryTree.max());

//判断值是否存在
//console.log(binaryTree.search(7) ? '7 is found' : '7 is no found');
//console.log(binaryTree.search(9) ? '9 is found' : '9 is no found');


//删除节点
//binaryTree.remove(10);