데이터 구조의 2 분 검색 트 리 추가 삭제 및 옮 겨 다 니 기
24926 단어 데이터 구조 와 알고리즘개발 류
빈 나무 나 다음 과 같은 성질 을 가 진 이 진 나 무 를 말한다.
1. ， ；
2. ， ；
3. 、 ；
4. 。
2. 이분 검색 트 리 노드 구축
public class TreeNode<E extends Comparable<E>>{
E e;
TreeNode left;
TreeNode right;
public TreeNode(E e){
this.e = e;
}
}
3. 2 분 검색 트 리 삽입 노드
2 분 검색 트 리 b 에 노드 node 알고리즘 을 삽입 합 니 다. 과정 은:
1. b ， node
2. e node.e，
3. e node.e， node
4. e node.e， node
public void add(E e){
root = add(root,e);
}
private TreeNode add(TreeNode node,E e){
if(node == null){
return new TreeNode<>(e);
}
if(e.compareTo(node.e) < 0) {
node.left = add(node.left, e);
}else if(e.compareTo(node.e) > 0) {
node.right = add(node.right, e);
}
return node;
}
4. 2 분 검색 트 리 찾기 노드
이 진 트 리 b 에서 e 를 찾 는 과정 은:
1. b ， ， ：
2. e b ， ； ：
3. e b ， ； ：
4. 。
1.
private boolean find(TreeNode node,E e){
if(node == null)
return false;
if(e.compareTo(node.e) == 0) {
return true;
}else if(e.compareTo(node.e) < 0) {
return find(node.left, e);
}else{ // (e.compareTo(node.e) > 0)
return find(node.right, e);
}
}
2.
//
public E findMin(){
TreeNode node = findMin(root);
return node.e;
}
public TreeNode findMin(TreeNode node){
if(node == null)
return null;
//
// ，
if(node.left == null)
return node;
//
return findMin(node.left);
}
3.
//
public E findMax(){
TreeNode node = findMax(root);
return node.e;
}
public TreeNode findMax(TreeNode node){
if(node == null)
return null;
if(node.right == null)
return node;
return findMax(node.right);
}
5. 이분 검색 트 리 삭제 노드
노드 삭제 3 가지 상황
1.
/**
* node
*
* @param node
* @return
*/
private TreeNode removeMin(TreeNode node){
if(node == null)
return null;
// ， null，
if(node.left == null) {
//
TreeNode rightNode = node.right;
// null
node.right = null;
size--;
return rightNode;
}
// left
node.left = removeMin(node.left);
return node;
}
2.
private E removeMinNR(TreeNode root) {
if(root == null)
return null;
TreeNode current = root;
//
TreeNode parent = current;
//
while (current.left != null){
parent = current;
current = current.left;
}
//
parent.left = current.right;
return current.e;
}
3.
/**
* node
*
* @param node
* @return
*/
private TreeNode removeMax(TreeNode node){
if(node == null)
return null;
if(node.right == null) {
TreeNode leftNode = node.left;
node.left = null;
size--;
return leftNode;
}
node.right = removeMax(node.right);
return node;
}
4.
private E removeMaxNR(TreeNode root) {
if(root == null)
return null;
TreeNode current = root;
TreeNode parent = current;
while (current.right != null){
parent = current;
current = current.right;
}
parent.right = current.left;
return current.e;
}
5.
//
public void remove(E e){
//
root = remove(root,e);
}
/**
*
* @param node
* @param e
* @return
*/
private TreeNode remove(TreeNode node,E e){
if(node == null)
return null;
if(e.compareTo(node.e) < 0){
// ，
node.left = remove(node.left,e);
return node;
}else if(e.compareTo(node.e) > 0){
// ，
node.right = remove(node.right, e);
return node;
}else{
//
//
if(node.left == null){
TreeNode rightNode = node.right;
node.right = null;
size--;
return rightNode;
}else if(node.right == null){
//
TreeNode leftNode = node.left;
node.left = null;
size--;
return leftNode;
}else {
//
//1.
TreeNode successor = findMin(node.right);
//2. ,
successor.right = removeMin(node.right);
//3.
successor.left = node.left;
//4.
node.left = node.right = null;
//5.
return successor;
}
}
}
6.
/**
*
* @param e
*/
public void removeNR(E e){
removeNR(root,e);
}
private void removeNR(TreeNode node,E e){
if(node == null) return;
TreeNode current = node;
TreeNode parent = node;
//
boolean isLeftChild = true;
while (current.e != e){
//
parent = current;
if(e.compareTo(current.e) < 0){
current = current.left;
isLeftChild = true;
}else {
current = current.right;
isLeftChild = false;
}
if(current == null) return;
}
//
if(current.left == null){
if(current == this.root){
// root, root
// root = root.right;
this.root = current.right;
current.right = null;
}else if(isLeftChild){
TreeNode rChild = current.right;
current.right = null;
parent.left = rChild;
size--;
}else{
TreeNode rChild = current.right;
current.right = null;
parent.right = rChild;
size--;
}
}else if(current.right == null){
if(current == this.root){
// root, root
// root = root.left;
this.root = current.left;
current.left = null;
}else if(isLeftChild){
TreeNode lChild = current.left;
current.left = null;
parent.left = lChild;
size--;
}else{
TreeNode lChild = current.left;
current.left = null;
parent.right = lChild;
size--;
}
}else{
//
//
TreeNode successor = findMin(current.right);
// ,
successor.right = removeMin(current.right);
//
successor.left = current.left;
//
current.left = current.right = null;
if(current == this.root){
// root
this.root = successor;
}else if(isLeftChild){
// parent.left =
parent.left = successor;
}else{
// parent.right =
parent.right = successor;
}
}
}
6. 2 분 검색 소 트 리 앞 뒤 순서 옮 겨 다 니 기
1. ， ，
//
public void preOrder(){
System.out.println(" ：");
preOrder(root);
System.out.println();
}
private void preOrder(TreeNode node){
if(node == null)
return;
System.out.print(node.e+" ");
preOrder(node.left);
preOrder(node.right);
}
2. ， ，
//
public void inOrder(){
System.out.println(" ：");
inOrder(root);
System.out.println();
}
private void inOrder(TreeNode node){
if(node == null)
return;
inOrder(node.left);
System.out.print(node.e+" ");
inOrder(node.right);
}
3. ， ，
//
public void postOrder(){
System.out.println(" ：");
postOrder(root);
System.out.println();
}
private void postOrder(TreeNode node){
if(node == null)
return;
postOrder(node.left);
postOrder(node.right);
System.out.print(node.e+" ");
}
7. 2 분 검색 소 트 리 비 재 귀적 순서 옮 겨 다 니 기
// ， ， ，
// ， ， ， ，
// ， ， ，
// ，
private void preOrderNR(TreeNode<E> root){
if(root == null) return;
Stack stack = new Stack();
//
stack.push(root);
System.out.println(" ：");
while ( !stack.isEmpty()){
//
TreeNode node = (TreeNode) stack.pop();
if(node == null) return;
System.out.print(node.e+" ");
if(node.right != null) {
stack.push(node.right);
}
if(node.left != null) {
stack.push(node.left);
}
}
}
8. 2 분 검색 트 리 층 을 옮 겨 다 니 기
// ， ， ， ，
// ， ， ，
private void levelOrder(TreeNode node){
if(node == null)
return;
Queue queue = new LinkedList<>();
//
queue.add(node);
while (!queue.isEmpty()){
//
TreeNode tailNode = (TreeNode) queue.remove();
if(tailNode != null) {
System.out.print(tailNode.e + " ");
queue.add(tailNode.left);
queue.add(tailNode.right);
}
}
}
9. 소결 과 연락처
QQ:1509815887
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
[JAVA] 배열 회전 출력요소 가 출력 을 시작 하 는 위치 에 주의 하 십시오. 모두 몇 라운드 의 수출 이 있 습 니까? n/2 + 1 매 라 운 드 는 상, 우, 하, 좌 로 나 뉜 다. 각 방향의 시작 위치 와 좌표 의 관 계 를 구...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
