# 恢復二進制搜索樹

BST上的錯誤節點被檢測到（突出顯示），然後交換以獲取正確的BST。

1. 幼稚
2. 遞歸
3. 迭代
4. 莫里斯遍歷

### 幼稚

#### 算法

1. 執行樹的有序遍歷並將遍歷存儲在動態數組中。
2. 動態排序 排列 使用插入排序（以最小化複雜度）。
3. 再次執行有序遍歷，並將節點值更改為已排序數組中的值。
4. 返回更正後的二進制搜索樹的根節點。

#### 履行

##### C ++程序
```#include <iostream>
#include <bits/stdc++.h>
using namespace std;

// blueprint of the tree node
class Node
{
public :
int data;
Node *left, *right, *next;

Node(int key)
{
data = key;
left = right = next = NULL;
}
};

// function that performs inorder traversal based on the mode
/*
Their are 3 modes :
1. traversal ('t') : simply perform traversal
2. storage ('s') : store data of tree into a vector
3. modify ('m'): store data of vector into a tree
*/
void inorder(Node *root,vector <int> &arr,char mode)
{
if(!root)
return;

inorder(root->left,arr,mode);
if(mode == 't')
cout<<root->data<<" ";
else if(mode == 's')
arr.push_back(root->data);
else if(mode == 'm')
{
int n = arr.size();
root->data = arr[n-1];
arr.pop_back();
}
inorder(root->right,arr,mode);
}

// function that corrects the BST and returns it's root
Node* fixBST(Node *root)
{
// array to store inorder traversal
vector <int> arr;
// store the inorder traversal into arr
inorder(root,arr,'s');

// apply insertion sort to arr
// insertion sort is used to minimize time complexity to o(n)
int i,j,key;
for (i = 1; i < arr.size(); i++)
{
key = arr[i];
j = i - 1;
while (j >= 0 && arr[j] < key)
{
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key;
}

// perform inorder on tree and modify the the node value of tree
inorder(root,arr,'m');
return root;
}

int main()
{
/* create the incorrect BST*/
Node *root = new Node(4);
root->left = new Node(7);
root->right = new Node(6);
root->left->left = new Node(1);
root->left->right = new Node(3);
root->right->left = new Node(5);
root->right->right = new Node(2);

vector <int> arr;

cout<<"Inorder traversal before : ";
inorder(root,arr,'t');

root = fixBST(root);

cout<<endl;

cout<<"Inorder traversal after : ";
inorder(root,arr,'t');
return 0;
}```
```Inorder traversal before : 1 7 3 4 5 6 2
Inorder traversal after : 1 2 3 4 5 6 7```
##### Java程序
```import java.util.*;
import java.io.*;

class tutorialCup
{
// blueprint of the tree node
static class Node
{
int data;
Node left, right, next;

Node(int key)
{
data = key;
left = right = next = null;
}
}

// function that performs inorder traversal based on the mode
/*
Their are 3 modes :
1. traversal ('t') : simply perform traversal
2. storage ('s') : store data of tree into a vector
3. modify ('m'): store data of vector into a tree
*/
static void inorder(Node root,ArrayList <Integer> arr,char mode)
{
if(root == null)
return;

inorder(root.left,arr,mode);
if(mode == 't')
System.out.print(root.data+" ");
else if(mode == 's')
else if(mode == 'm')
{
int n = arr.size();
root.data = arr.get(n-1);
arr.remove(n-1);
}
inorder(root.right,arr,mode);
}

// function that corrects the BST and returns it's root
static Node fixBST(Node root)
{
// array to store inorder traversal
ArrayList <Integer> arr = new ArrayList<>();
// store the inorder traversal into arr
inorder(root,arr,'s');

// apply insertion sort to arr
// insertion sort is used to minimize time complexity to o(n)
int i,j,key;
for (i = 1; i < arr.size(); i++)
{
key = arr.get(i);
j = i - 1;
while (j >= 0 && arr.get(j) < key)
{
arr.set(j+1,arr.get(j));
j = j - 1;
}
arr.set(j+1,key);
}

// perform inorder on tree and modify the the node value of tree
inorder(root,arr,'m');
return root;
}

public static void main (String[] args)
{
/* create the incorrect BST*/
Node root = new Node(4);
root.left = new Node(7);
root.right = new Node(6);
root.left.left = new Node(1);
root.left.right = new Node(3);
root.right.left = new Node(5);
root.right.right = new Node(2);

ArrayList <Integer> arr = new ArrayList<>();

System.out.print("Inorder traversal before : ");
inorder(root,arr,'t');

root = fixBST(root);

System.out.println();
System.out.print("Inorder traversal after : ");
inorder(root,arr,'t');
}

}```
```Inorder traversal before : 1 7 3 4 5 6 2
Inorder traversal after : 1 2 3 4 5 6 7```

#### 恢復二叉搜索樹的複雜度分析

• 時間複雜度：T（n）= O（n）
• 空間複雜度：A（n）= O（n）

### 遞歸

#### 恢復二進制搜索樹的方法

1. 考慮 在上面的示例中給出。 BST的節點可以通過兩種方式交換。
2. 1st方式：交換了2個非相鄰樹節點（即這些節點之間至少有一個節點。例如：交換非相鄰節點的樹的有序遍歷為：1 7 3 4 5 6 2.正如我們觀察到的2和7從各自的位置調換。
1. 我們執行順序遍歷並使用 第一 第二 變量以存儲兩個錯誤放置的節點。 我們用 上一頁 存儲在當前節點之前訪問的上一個節點 （根） 有序遍歷期間的節點。
2. 在順序遍歷期間，我們發現一個違反BST順序的節點。 即prev-> data> root-> data（其中root是要訪問的當前節點），我們將prev存儲到第一個，然後將root存儲到第二個。
3. 在進一步遍歷期間，如果我們發現另一個違反BST標準的節點（如上所述），但是這次已經為第一個節點分配了一個值。 因此，我們將當前節點分配給第二個節點。
4. 遍歷結束後，我們交換存儲在第一節點和第二節點中的數據。
3. 2nd方式：交換了2個相鄰節點（即，節點是父子對）。例如：交換相鄰節點的樹的有序遍歷為：1 2 4 3 5 6 7.正如我們觀察到的，從其交換了3和4各自的職位。
1. 我們執行順序遍歷並使用 第一 第二 變量以存儲兩個錯誤放置的節點。 我們用 上一頁 存儲在當前節點之前訪問的上一個節點 （根） 有序遍歷期間的節點。
2. 在順序遍歷期間，我們發現一個違反BST順序的節點。 即prev-> data> root-> data（其中root是要訪問的當前節點），我們將prev存儲到第一個，然後將root存儲到第二個。
3. 遍歷結束後，我們交換存儲在第一節點和第二節點中的數據。

#### 算法

1. 定義prev（遍歷存儲先前的節點），first（無序存儲第一個節點），second（無序存儲第二個節點）變量以存儲各種樹節點地址。
2. 執行簡單的順序遍歷。
3. 如果在順序遍歷期間，我們發現一個違反BST順序的節點。 即prev-> data> root-> data.we將prev存儲到 第一 並紮根 第二。
4. 在進一步遍歷期間，如果發現另一個違反BST標準的節點，即prev-> data> root-> data。 但是這一次已經為第一個節點分配了一個值。 所以我們將當前節點分配給 第二。
5. 執行順序遍歷後。 交換第一個和第二個節點的數據。樹是固定的。

#### 履行

##### C ++程序
```#include <iostream>
#include <bits/stdc++.h>
using namespace std;

// blueprint of the tree node
class Node
{
public :
int data;
Node *left, *right, *next;

Node(int key)
{
data = key;
left = right = next = NULL;
}
};
/* function that performs inorder traversal
and checks for the incorrectly set nodes*/
void inorderFix(Node *root,Node* &prev,Node* &first,Node* &second)
{
if(root == NULL)
return;

inorderFix(root->left,prev,first,second);

if(prev != NULL && prev->data > root->data)
{
// first misordering found
if(first == NULL)
{
first = prev;
second = root;
}

// second misordering found (if exists)
else
second = root;
}

prev = root;

inorderFix(root->right,prev,first,second);
}
// function that corrects the BST and returns it's root
Node* fixBST(Node *root)
{
Node *prev,*first,*second;
prev = first = second = NULL;

inorderFix(root,prev,first,second);
swap(first->data,second->data);

return root;
}

// function to simply perform inorder traversal of the tree
void inorder(Node *root)
{
if(root == NULL)
return;

inorder(root->left);
cout<<root->data<<" ";
inorder(root->right);
}

int main()
{
/* create the incorrect BST*/
Node *root = new Node(4);
root->left = new Node(7);
root->right = new Node(6);
root->left->left = new Node(1);
root->left->right = new Node(3);
root->right->left = new Node(5);
root->right->right = new Node(2);

cout<<"Inorder traversal before : ";
inorder(root);

root = fixBST(root);
cout<<endl;

cout<<"Inorder traversal after : ";
inorder(root);

return 0;
}```
```Inorder Traversal before : 1 7 3 4 5 6 2
Inorder Traversal after : 1 2 3 4 5 6 7```
##### Java程序
```import java.util.*;
import java.io.*;

class tutorialCup
{
// blueprint of the tree node
static class Node
{
int data;
Node left, right, next;

Node(int key)
{
data = key;
left = right = next = null;
}
}

/* function that performs inorder traversal
and checks for the incorrectly set nodes*/
static void inorderFix(Node root,ArrayList <Node> nodes)
{
if(root == null)
return;

inorderFix(root.left,nodes);

if(nodes.get(0) != null && nodes.get(0).data > root.data)
{
// first misordering found
if(nodes.get(1) == null)
{
// first is set to previous
nodes.set(1,nodes.get(0));
// second is set to current node
nodes.set(2,root);
}
// second misordering found (if exists)
else
nodes.set(2,root);
}

// 1st element of ArrayList stores previous nodes
nodes.set(0,root);

inorderFix(root.right,nodes);
}
// function that corrects the BST and returns it's root
/*
here,
prev -> nodes.get(0)
first -> nodes.get(1)
second -> nodes.get(2)
*/
static Node fixBST(Node root)
{
// we use ArrayList to store previous(nodes[0]),first(nodes[1]) and second(nodes[2])
// initially all nodes are set to null
ArrayList <Node> nodes = new ArrayList<>(Arrays.asList(null,null,null));
inorderFix(root,nodes);

// swap the values of the nodes
int temp = nodes.get(1).data;
nodes.get(1).data = nodes.get(2).data;
nodes.get(2).data = temp;

return root;
}

// function to simply perform inorder traversal of the tree
static void inorder(Node root)
{
if(root == null)
return;

inorder(root.left);
System.out.print(root.data+" ");
inorder(root.right);
}

public static void main (String[] args)
{
/* create the incorrect BST*/
Node root = new Node(4);
root.left = new Node(7);
root.right = new Node(6);
root.left.left = new Node(1);
root.left.right = new Node(3);
root.right.left = new Node(5);
root.right.right = new Node(2);

System.out.print("Inorder Traversal before : ");
inorder(root);

root = fixBST(root);
System.out.println();

System.out.print("Inorder Traversal after : ");
inorder(root);

}
}```
```Inorder Traversal before : 1 7 3 4 5 6 2
Inorder Traversal after : 1 2 3 4 5 6 7```

#### 恢復二叉搜索樹的複雜度分析

• 時間複雜度：T（n）= O（n）
• 空間複雜度：A（n）= O（n），使用的遞歸堆棧空間。

### 迭代

#### 算法

1. 定義prev（遍歷存儲先前的節點），first（無序存儲第一個節點），second（無序存儲第二個節點）變量以存儲各種樹節點地址。
2. 執行簡單的順序遍歷。
3. 如果在順序遍歷期間，我們發現一個違反BST順序的節點。 即prev-> data> root-> data.we將prev存儲到 第一 並紮根 第二。
4. 在進一步遍歷期間，如果發現另一個違反BST標準的節點，即prev-> data> root-> data。 但是這一次已經為第一個節點分配了一個值。 所以我們將當前節點分配給 第二。
5. 執行順序遍歷後。 交換第一和第二節點的數據。 樹是固定的。

#### 履行

##### C ++程序
```#include <iostream>
#include <bits/stdc++.h>
using namespace std;

// blueprint of the tree node
class Node
{
public :
int data;
Node *left, *right, *next;

Node(int key)
{
data = key;
left = right = next = NULL;
}
};

// function that corrects the BST by performing iterative inorder
// and returns it's root
Node* fixBST(Node *root)
{
Node *prev,*first,*second;
prev = first = second = NULL;

Node* curr = root;

stack <Node*> st;

while(!st.empty() ||  root != NULL)
{
if(root != NULL)
{
// visit current node's (root) left subtree
st.push(root);
root = root->left;
}
else
{
// done left subtree of current node
root = st.top();
st.pop();

// compare root.val with root.val if we have one
if(prev != NULL && root->data < prev->data)
{
// incorrect smaller node is always found as prev node
if(first == NULL)
first = prev;

// incorrect larger node is always found as current root node
second = root;
}

// visit root's right subtree
prev = root;
root = root->right;
}
}

// fix the BST by swapping values
int temp = first->data;
first->data = second->data;
second->data = temp;

// return address of the original root node
return curr;
}

// function to simply perform inorder traversal of the tree
void inorder(Node *root)
{
if(root == NULL)
return;

inorder(root->left);
cout<<root->data<<" ";
inorder(root->right);
}

int main()
{
/* create the incorrect BST*/
Node *root = new Node(4);
root->left = new Node(7);
root->right = new Node(6);
root->left->left = new Node(1);
root->left->right = new Node(3);
root->right->left = new Node(5);
root->right->right = new Node(2);

cout<<"Inorder traversal before : ";
inorder(root);

root = fixBST(root);
cout<<endl;

cout<<"Inorder traversal after : ";
inorder(root);

return 0;
}```
```Inorder Traversal before : 1 7 3 4 5 6 2
Inorder Traversal after : 1 2 3 4 5 6 7```
##### Java程序
```import java.util.*;
import java.io.*;

class tutorialCup
{
// blueprint of the tree node
static class Node
{
int data;
Node left, right, next;

Node(int key)
{
data = key;
left = right = next = null;
}
}

// function that corrects the BST and returns it's root
static Node fixBST(Node root)
{
Node prev,first,second;
prev = first = second = null;

Node curr = root;

Stack<Node> st = new Stack<Node>();

while(!st.isEmpty() ||  root != null)
{
if(root != null)
{
// visit current node's (root) left subtree
st.push(root);
root = root.left;
}
else
{
// done left subtree of current node
root = st.pop();

// compare root.val with root.val if we have one
if(prev != null && root.data <= prev.data)
{
// incorrect smaller node is always found as prev node
if(first == null)
first = prev;

// incorrect larger node is always found as current root node
second = root;
}

// visit root's right subtree
prev = root;
root = root.right;
}
}

// fix the BST by swapping values
int temp = first.data;
first.data = second.data;
second.data = temp;

// return address of the original root node
return curr;
}

// function to simply perform inorder traversal of the tree
static void inorder(Node root)
{
if(root == null)
return;

inorder(root.left);
System.out.print(root.data+" ");
inorder(root.right);
}

public static void main (String[] args)
{
/* create the incorrect BST*/
Node root = new Node(4);
root.left = new Node(7);
root.right = new Node(6);
root.left.left = new Node(1);
root.left.right = new Node(3);
root.right.left = new Node(5);
root.right.right = new Node(2);

System.out.print("Inorder Traversal before : ");
inorder(root);

root = fixBST(root);
System.out.println();

System.out.print("Inorder Traversal after : ");
inorder(root);
}
}```
```Inorder Traversal before : 1 7 3 4 5 6 2
Inorder Traversal after : 1 2 3 4 5 6 7```

#### 恢復二叉搜索樹的複雜度分析

• 時間複雜度：T（n）= O（n）
• 空間複雜度：A（n）= O（n）

### 莫里斯遍歷

#### 恢復二進制搜索樹的方法

Morris遍歷類似於遞歸/迭代遍歷，但是我們需要在遍歷期間修改樹結構。 在訪問根的左樹之前，我們將在左樹中最右邊的節點與根之間建立一條後沿。 因此，遍歷左側樹後，我們可以返回到根節點。

#### 算法

1. 執行Morris遍歷並按順序處理每個節點。
2. 對於每個節點（樹的最左邊的節點除外），請跟踪其上一個節點 上一頁。 當前正在處理的節點存儲在 發生。
3. 如果在遍歷期間，我們發現一個違反BST順序的節點。 即prev-> data> root-> data.we將prev存儲到 第一 並紮根 第二。
4. 在進一步遍歷期間，如果我們發現另一個違反BST標準的節點，即prev-> data> root-> data。 但是從那以後，第一個節點已經被分配了一個值。 所以我們將當前節點（違反BST標準）分配給 第二。
5. 執行順序遍歷後。 交換的數據 第一第二 節點和樹變得固定。

#### 履行

##### C ++程序
```#include <iostream>
#include <bits/stdc++.h>
using namespace std;

// blueprint of the tree node
class Node
{
public :
int data;
Node *left, *right, *next;

Node(int key)
{
data = key;
left = right = next = NULL;
}
};

// function that corrects the BST by performing iterative inorder
// and returns it's root
Node* fixBST(Node *root)
{
Node *prev,*first,*second;
prev = first = second = NULL;

// stores rightmost node in left subtree of root
Node* rightMost = NULL;
// stores current node starting with root node
Node* curr = root;

while(curr != NULL)
{
// for each node, we compare it with prev node as we did in in-order-traversal
if(prev != NULL && curr->data < prev->data)
{
if(first == NULL)
first = prev;

second = curr;
}

if(curr->left != NULL)
{
// got left tree, then let's locate its rightmost node in left tree
rightMost = curr->left;
// we may have visited the left tree before, and connect the rightmost node with curr node (root node)
while(rightMost->right != NULL && rightMost->right != curr)
rightMost = rightMost->right;

if(rightMost->right == curr)
{
// if this left tree has been visited before, then we are done with it
// cut the connection with currNode and start visit curr's right tree
rightMost->right = NULL;
prev = curr;
curr = curr->right;
}
else
{
// if this left tree has not been visited before, then we create a back edge from rightmost node
// to curr node, so we can return to the start point after done the left tree
rightMost->right = curr;
curr = curr->left;
}

}
else
{
// no left tree, then just visit its right tree
prev = curr;
curr = curr->right;
}
}

// swap the values of incorrect nodes
swap(first->data,second->data);
return root;
}

// function to simply perform inorder traversal of the tree
void inorder(Node *root)
{
if(root == NULL)
return;

inorder(root->left);
cout<<root->data<<" ";
inorder(root->right);
}

int main()
{
/* create the incorrect BST*/
Node *root = new Node(4);
root->left = new Node(7);
root->right = new Node(6);
root->left->left = new Node(1);
root->left->right = new Node(3);
root->right->left = new Node(5);
root->right->right = new Node(2);

cout<<"Inorder traversal before : ";
inorder(root);

root = fixBST(root);
cout<<endl;

cout<<"Inorder traversal after : ";
inorder(root);

return 0;
}```
```Inorder Traversal before : 1 7 3 4 5 6 2
Inorder Traversal after : 1 2 3 4 5 6 7```
##### Java程序
```import java.util.*;
import java.io.*;

class tutorialCup
{
// blueprint of the tree node
static class Node
{
int data;
Node left, right, next;

Node(int key)
{
data = key;
left = right = next = null;
}
}

// function that corrects the BST using morris traversal and returns it's root
static Node fixBST(Node root)
{
Node prev,first,second;
prev = first = second = null;

// stores rightmost node in left subtree of root
Node rightMost = null;
// stores current node starting with root node
Node curr = root;

while(curr != null)
{
// for each node, we compare it with prev node as we did in in-order-traversal
if(prev != null && curr.data < prev.data)
{
if(first == null)
first = prev;

second = curr;
}

if(curr.left != null)
{
// got left tree, then let's locate its rightmost node in left tree
rightMost = curr.left;
// we may have visited the left tree before, and connect the rightmost node with curr node (root node)
while(rightMost.right != null && rightMost.right != curr)
rightMost = rightMost.right;

if(rightMost.right == curr)
{
// if this left tree has been visited before, then we are done with it
// cut the connection with currNode and start visit curr's right tree
rightMost.right = null;
prev = curr;
curr = curr.right;
}
else
{
// if this left tree has not been visited before, then we create a back edge from rightmost node
// to curr node, so we can return to the start point after done the left tree
rightMost.right = curr;
curr = curr.left;
}

}
else
{
// no left tree, then just visit its right tree
prev = curr;
curr = curr.right;
}
}

// swap the values of incorrect nodes
int temp = first.data;
first.data = second.data;
second.data = temp;

return root;
}

// function to simply perform inorder traversal of the tree
static void inorder(Node root)
{
if(root == null)
return;

inorder(root.left);
System.out.print(root.data+" ");
inorder(root.right);
}

public static void main (String[] args)
{
/* create the incorrect BST*/
Node root = new Node(4);
root.left = new Node(7);
root.right = new Node(6);
root.left.left = new Node(1);
root.left.right = new Node(3);
root.right.left = new Node(5);
root.right.right = new Node(2);

System.out.print("Inorder Traversal before : ");
inorder(root);

// fixing the BST
root = fixBST(root);
System.out.println();

System.out.print("Inorder Traversal after : ");
inorder(root);
}
}```
```Inorder Traversal before : 1 7 3 4 5 6 2
Inorder Traversal after : 1 2 3 4 5 6 7```

#### 恢復二叉搜索樹的複雜度分析

1. 時間複雜度：T（n）= O（n）
2. 空間複雜度：A（n）= O（1），也不使用數據結構，也不使用遞歸堆棧空間。