javascript数据结构7-二叉搜索树（BST）

发表于 | 更新于 | 分类于

二叉树 ：

这里写图片描述

闲话少说，直接上代码：

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
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<title>BST</title>
</head>
<body>
<script>
  //结点
    function Node(data,left,right){
        this.data=data;
        this.left=left;
        this.right=right;
        this.floor=floor;  //层数
        this.show=show;
    }
    function floor(){
      return this.floor;
    }
    function show(){
        return this.data;
    }
  
    function BST(){
        this.root=null;
        this.insert=insert; //插入数据
        this.inOrder=inOrder; //中序排列，详细见后面解释
        this.preOrder=preOrder; //先序排序
        this.postOrder=postOrder; //后续排序
        this.getMax=getMax; //得到最大值
      	this.getMin=getMin; //得到最小值
      	this.find=find; //查找
      	this.remove=remove; //删除节点
    }
    
    function insert(data){
       var n=new Node(data,null,null);
        if(this.root==null){
            this.root=n;
            this.root.floor=1;
        }else{
            var current=this.root;
            var parent;
                var c=1;    
            while(true){
                parent=current;  
                if(data<current.data){
                        current=current.left;
                        c++;  //计算层数的计数器加1
                    if(current==null){
                        parent.left=n;
                        parent.left.floor=c;
                        break;
                    }
                }else{
                    current=current.right;
                        c++;   //加1
                    if(current==null){
                        parent.right=n;
                        //rHeight++;
                        // console.log("**"+rHeight+"**");
                        parent.right.floor=c;
                        break;
                    }
                }
            }
        }
    }
  //中序遍历
  function inOrder(node){
      if(!(node==null)){
          inOrder(node.left);
          document.write(node.show()+" ");
          document.write("层数"+node.floor+"<br/>");
          inOrder(node.right);
      }
       //console.count("inOrder被执行的次数");
  }
  //先序遍历
   function preOrder(node){
      if(!(node==null)){
          document.write(node.show()+" ");
          preOrder(node.left);
          preOrder(node.right);
      }
  }
  
  //后序遍历
   function postOrder(node){
      if(!(node==null)){
          postOrder(node.left);        
          postOrder(node.right);
            document.write(node.show()+" ");
      }
  }
  
  //查找最大值
  function getMax(){
     	var current=this.root;
    	while(!(current.right==null)){
          	current=current.right;
        }
    	return current.data;
  }
  //查找最小值
   function getMin(){
     	var current=this.root;
    	while(!(current.left==null)){
          	current=current.left;
        }
    	return current.data;
  }
  //带参数---查找最小值
  function getSmallest(node){
  		while(!(node.left==null)){
  			node=node.left;
  		}
  	 return node;
  }
  //查找
  function find(data){
    	var current=this.root;
    	while(current!=null){
          	if(current.data==data){
              document.write("<br/>找到【"+data+"】节点<br/>");
              return current;
            }else if(data<current.data){
               current=current.left;
            }else{
               current=current.right;
            }
         
        }
     document.write("<br/>没有找到【"+data+"】 节点<br/>");
//     	return current;
  }
  
  //删除节点-详细解释见后后面
     function remove(data) {
			root = removeNode(this.root, data);
       		//其实root=没有用处，只是保留了函数执行的地址
	}
	function removeNode(node, data) {
          if (node == null) {
				return null;
			}
		if (data == node.data) {
			// 没有子节点的节点
			if (node.left == null && node.right == null) {
					return null;
			}
			// 没有左子节点的节点
			if (node.left == null) {
					return node.right;
			}
			// 没有右子节点的节点
			if (node.right == null) {
					return node.left;
			}
			// 有两个子节点的节点
			var tempNode = getSmallest(node.right);
			node.data = tempNode.data;
			node.right = removeNode(node.right, tempNode.data);
					return node;
			}
			else if (data < node.data) {
				node.left = removeNode(node.left, data);
               
				return node;
			}
			else {
				node.right = removeNode(node.right, data);
              // console.log(node);
				return node;
			}
}
  
  //测试
      var nums=new BST();
      nums.insert(56);
      nums.insert(22);  
      nums.insert(81);
      nums.insert(10);
      nums.insert(30);
      nums.insert(77);
      nums.insert(92);
      nums.insert(100);
      document.write("*****************中序遍历***************</br>");
      inOrder(nums.root);
      document.write("</br>***************先序遍历***************</br>");
      preOrder(nums.root);
      document.write("</br>***************后序遍历***************</br>");
      postOrder(nums.root);
      //nums.show();
      //console.log(nums);  
      document.write("</br>***************最大值/最小值************</br>");
      document.write(nums.getMax()+"/"+nums.getMin());
      document.write("</br>***************查找************</br>");
  	  nums.find(100);
      document.write("</br>***************删除节点81后************</br>");
      nums.remove(81);
      console.log(nums);
      preOrder(nums.root);
</script>
</body>
</html>

结果：
这里写图片描述

遍历

中序遍历：
这里写图片描述
理解双层递归

1
2
3
4
5
6
7
8
9
10
function inOrder(node) {
    if (!(node == null)) {
        inOrder(node.left);                             //@1
        document.document(node.show() + " ");           //@2
        inOrder(node.right);                            //@3
    }
}


inOrder(nums.root);    //开始执行

从根节点开始：
这里写图片描述

这里写图片描述
这里写图片描述

删除节点：

1
2
3
function remove(data) {
		root = removeNode(this.root, data);  
	}

简单接受待删除的数据，具体执行是removeNode函数；

1
2
function removeNode(node, data) {
	}

待删除的节点是：
1.叶子结点，只需要将从父节点只想它的链接指向null；

1
2
3
if (node.left == null && node.right == null) {
		return null;   
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
if (node.left == null && node.right == null) {
				return null;   //递归，找到节点置为空即可
			}
			   //其他情况
			}
			else if (data < node.data) {
				node.left = removeNode(node.left, data);  //#1            
				return node; //#2
			}
			else {
				node.right = removeNode(node.right, data);//#3
				return node; //#4
			}

通过if else逻辑找到node节点

//#1  node.left=null(后面的函数递归后返回的值)
//#3  node.right=null(后面的函数递归后返回的值)

2.只包含一个子节点，原本指向它的节点指向它的子节点。
3.左右子树都有的时候。两种做法：找到左子树的最大值或者右子树的最小值。这里我们用第二种。

  • 查找右子树的最小值，创建一个临时的节点tempNode。
  • 将临时节点的值赋值给待删除节点
  • 删除临时节点

注意：

//#2 //#4必须有，如果没有，则删除节点下面的所有子树都将被删除。
真个过程举个形象的说明，遍历的时候把节点之间的链条解开进行查询，return node；递归查询到最后一级后，由下向上对链条进行缝合。