mycodeschool的数据结构总结

P1：时间复杂度

https://blog.csdn.net/qq_41523096/article/details/82142747 讲的贼清楚

P2：链表：单链表

https://blog.csdn.net/Shuffle_Ts/article/details/95055467

https://blog.csdn.net/Endeavor_G/article/details/80552680?depth_1-utm_source=distribute.pc_relevant.none-task-blog-BlogCommendFromMachineLearnPai2-2&utm_source=distribute.pc_relevant.none-task-blog-BlogCommendFromMachineLearnPai2-2

顺序增加一组数据：

 1 #include <iostream>
 2 
 3 struct Node
 4 {
 5     int data;
 6     Node* next;
 7     //struct Node* next;   //C语言中
 8 };
 9 
10 Node* Insert(Node* head, int x)
11 {
12     //struct Node* temp = (Node*)malloc(sizeof(Node));  //C语言写法
13     Node* temp = new Node();
14     temp->data = x;
15     temp->next = NULL;
16     if (head != NULL)
17         temp->next = head;  //这里因为是链表是倒着插入的，相当于堆书
18     head = temp;
19     return head;
20 }
21 
22 void Print(Node* head)
23 {
24     while (head != NULL)
25     {
26         std::cout << head->data << "  " ;
27         head = head->next;
28     }
29 }
30 
31 int main()
32 {
33     Node* head = NULL;
34     int n, x;
35     std::cout << "需要输入多少个数字？" << std::endl;
36     std::cin >> n;
37     for (int i = 0; i < n; i++)
38     {
39         std::cout << "请输入数字" << std::endl;
40         std::cin >> x;
41         head = Insert(head,x);
42         std::cout << "这个链表是：" ;
43         Print(head);
44          std::cout << "" << std::endl;
45     }
46     std::cin.get();
47     return 0;
48 }

View Code

插入一个数据：

 1 #include <iostream>
 2 
 3 struct Node
 4 {
 5     int data;
 6     Node* next;
 7 };
 8 
 9 Node* Insert(int x, int n, Node* head)  //x为值，n为插入的位置
10 {
11     Node* temp = new Node();
12     temp->data = x;
13     if(1 == n)
14     { 
15         temp->next = head;
16         head = temp;
17     }
18     else
19     {
20         Node* temp1 = nullptr;
21         temp1 = head;
22         for (int i = 0; i < n-2; i++)    
23             head = head->next; 
24         temp->next = head->next;
25         head->next = temp;
26         head = temp1;
27     }
28     return head;    
29 }
30 
31 void Print(Node* head)
32 {
33     while (head != nullptr)
34     {
35         std::cout << head->data;
36         head = head->next;        
37     }
38 }
39 
40 int main()
41 {
42     Node* head = nullptr;
43     
44     head = Insert(5, 1, head);
45     head = Insert(4, 2, head);
46     head = Insert(3, 3, head);
47     head = Insert(2, 3, head);
48     Print(head);
49     std::cin.get();
50     return 0;
51 }

View Code

删除一个数据：

 1 #include <iostream>
 2 
 3 struct Node
 4 {
 5     int data;
 6     Node* next;
 7 };
 8 
 9 Node* Insert(int x, int n, Node* head)  //x为值，n为插入的位置
10 {
11     Node* temp = new Node();
12     temp->data = x;
13     if(1 == n)
14     { 
15         temp->next = head;
16         head = temp;
17     }
18     else
19     {
20         Node* temp1 = nullptr;
21         temp1 = head;
22         for (int i = 0; i < n-2; i++)    
23             head = head->next; 
24         temp->next = head->next;
25         head->next = temp;
26         head = temp1;
27     }
28     return head;    
29 }
30 
31 void Print(Node* head)
32 {
33     while (head != nullptr)
34     {
35         std::cout << head->data;
36         head = head->next;        
37     }
38 }
39 
40 Node* Delete(int n, Node* head)   //n为要删除的位置
41 {
42     Node* temp = nullptr;
43     temp = head;
44     if (1 == n)
45     {    
46         head = head->next;
47         delete temp;        
48     }
49     else
50     {
51         for (int i = 0; i < n-2; i++)
52             temp = temp->next;
53         Node* temp1 = temp->next;
54         temp->next = temp1->next;;
55         delete temp1;
56     }
57     return head;
58 }
59 
60 int main()
61 {
62     Node* head = nullptr;
63     
64     head = Insert(5, 1, head);
65     head = Insert(4, 2, head);
66     head = Insert(3, 3, head);
67     head = Insert(2, 3, head);
68     head = Delete(2, head);
69     Print(head);
70     std::cin.get();
71     return 0;
72 }

View Code

反向链表：迭代方法

 1 struct Node
 2 {
 3     int data;
 4     Node* next;
 5 };
 6 
 7 Node* Insert(int x, int n, Node* head)  //x为值，n为插入的位置
 8 {
 9     Node* temp = new Node();
10     temp->data = x;
11     if(1 == n)
12     { 
13         temp->next = head;
14         head = temp;
15     }
16     else
17     {
18         Node* temp1 = nullptr;
19         temp1 = head;
20         for (int i = 0; i < n-2; i++)    
21             head = head->next; 
22         temp->next = head->next;
23         head->next = temp;
24         head = temp1;
25     }
26     return head;    
27 }
28 
29 void Print(Node* head)
30 {
31     while (head != nullptr)
32     {
33         std::cout << head->data;
34         head = head->next;        
35     }
36 }
37 
38 Node* Replace(Node* head)
39 {
40     Node* prv, *mid, *beh;
41     prv = nullptr;
42     mid = head;
43     while (mid != nullptr)
44     {
45         beh = mid->next;
46         mid->next = prv;
47         prv = mid;
48         mid = beh;
49     }
50     return prv;
51 }
52 
53 int main()
54 {
55     Node* head = nullptr;
56     
57     head = Insert(5, 1, head);
58     head = Insert(4, 2, head);
59     head = Insert(3, 3, head);
60     head = Insert(2, 3, head);
61     head = Replace(head);
62     Print(head);
63     std::cin.get();
64     return 0;
65 }

View Code

打印链表：正向和反向

 1 #include <iostream>
 2 
 3 struct Node
 4 {
 5     int data;
 6     Node* next;
 7 };
 8 
 9 Node* Insert(int x, int n, Node* head)  //x为值，n为插入的位置
10 {
11     Node* temp = new Node();
12     temp->data = x;
13     if(1 == n)
14     { 
15         temp->next = head;
16         head = temp;
17     }
18     else
19     {
20         Node* temp1 = nullptr;
21         temp1 = head;
22         for (int i = 0; i < n-2; i++)    
23             head = head->next; 
24         temp->next = head->next;
25         head->next = temp;
26         head = temp1;
27     }
28     return head;    
29 }
30 
31 void Print(Node* head)
32 {
33     if (head == nullptr) return;
34     std::cout << head->data <<"  ";
35     head = head->next;
36     Print(head);
37 }
38 
39 void ProcPrint(Node* head)
40 {
41     if (head == nullptr) return;
42     ProcPrint(head->next);
43     std::cout << head->data << "  ";            
44 }
45 
46 int main()
47 {
48     Node* head = nullptr;
49     
50     head = Insert(5, 1, head);
51     head = Insert(4, 1, head);
52     head = Insert(3, 1, head);
53     head = Insert(2, 1, head);
54     Print(head);
55      std::cout << "" << std::endl;
56     ProcPrint(head);
57     std::cin.get();
58     return 0;
59 }

View Code

反向链表：递归方法

 1 #include <iostream>
 2 
 3 struct Node
 4 {
 5     int data;
 6     Node* next;
 7 };
 8 
 9 static Node* node = nullptr;
10 
11 Node* Insert(int x, int n, Node* head)  //x为值，n为插入的位置
12 {
13     Node* temp = new Node();
14     temp->data = x;
15     if(1 == n)
16     { 
17         temp->next = head;
18         head = temp;
19     }
20     else
21     {
22         Node* temp1 = nullptr;
23         temp1 = head;
24         for (int i = 0; i < n-2; i++)    
25             head = head->next; 
26         temp->next = head->next;
27         head->next = temp;
28         head = temp1;
29     }
30     return head;    
31 }
32 
33 void Print(Node* head)
34 {
35     if (head == nullptr) return;
36     std::cout << head->data <<"  ";
37     head = head->next;
38     Print(head);
39 }
40 
41 void Reserver(Node* temp)
42 {    
43     if (temp->next == nullptr)
44     {
45         node = temp;
46         return;
47     }
48     Reserver(temp->next);
49     Node* temp1;
50     temp1 = temp->next;
51     temp1->next = temp;
52     temp->next = nullptr;
53 }
54 
55 int main()
56 {
57     Node* head = nullptr;
58     
59     head = Insert(5, 1, head);
60     head = Insert(4, 1, head);
61     head = Insert(3, 1, head);
62     head = Insert(2, 1, head);
63     Print(head);
64     std::cout << "" << std::endl;
65     Reserver(head);
66     Print(node);
67     std::cin.get();
68     return 0;
69 }

View Code

P12：双链表

双链表的增插删打印：

  1 #include <iostream>
  2 
  3 struct Node
  4 {
  5     int data;
  6     Node* prev;
  7     Node* next;
  8 };
  9 
 10 static Node* head;
 11 
 12 Node* GetNewNode(int x)
 13 {
 14     Node* temp = new Node();
 15     temp->prev = nullptr;
 16     temp->data = x;
 17     temp->next = nullptr;
 18     return temp;
 19 }
 20 void Add(int x)
 21 {
 22     Node* temp = GetNewNode(x);
 23     if(head == nullptr)
 24         head = temp;
 25     else
 26     {
 27         temp->next = head;
 28         head = temp;
 29     }
 30 }
 31 
 32 void Insert(int n,int x)
 33 {
 34     Node* temp = GetNewNode(x);
 35     Node* node,*node1;
 36     if (head == nullptr)
 37         head = temp;
 38     else
 39     {
 40         node = head;
 41         for (int i = 0; i < n-2; i++)
 42             node = node->next;
 43         if (1 == n)
 44         {
 45             temp->next = node;
 46             node->prev = temp;
 47             head = temp;
 48         }
 49         else
 50         {
 51             if (node->next != nullptr)
 52             { 
 53                 node1 = node->next;
 54                 node1->prev = temp;
 55                 temp->next = node->next;
 56             }
 57             node->next = temp;
 58             temp->prev = node;
 59         }
 60     }
 61 }
 62 
 63 void Delete(int n)
 64 {
 65     Node* temp;
 66     temp = head;
 67     if (1 == n)
 68     {
 69         head = head->next;
 70         head->prev = nullptr;
 71         delete temp;
 72     }
 73     else
 74     {
 75         for (int i = 0; i < n-1; i++)
 76             temp = temp->next;
 77         if (temp->next != nullptr)
 78         {
 79             (temp->prev)->next = temp->next;
 80             (temp->next)->prev = temp->prev;
 81         }
 82         else
 83             (temp->prev)->next = nullptr;
 84     }
 85 }
 86 
 87 void Print(Node* head)
 88 {
 89     Node* temp;
 90     temp = head;
 91     if (temp == nullptr) return;
 92     std::cout << temp->data;
 93     Print(temp->next);
 94 }
 95 
 96 void PrvePrint(Node* head)
 97 {
 98     Node* temp;
 99     temp = head;
100     if (temp == nullptr) return;
101     while (temp->next != nullptr)
102     {
103         temp = temp->next;
104     }
105     while(temp != nullptr)
106     {
107         std::cout << temp->data;
108         temp = temp->prev;
109     }
110 }
111 int main()
112 {   
113     Insert(1, 1);
114     Insert(1, 2);
115     Insert(1, 5);
116     Insert(2, 4);
117     Insert(3, 3);
118     std::cout << "链表为：";
119     //Delete(5);
120     Print(head);
121     std::cout << "" << std::endl;
122     std::cout << "链表为：";
123     PrvePrint(head);
124     std::cin.get();
125     return 0;
126 }

View Code

P14：堆栈

基本方法：

Push 增加一个数据

Pop 删除一个数据

Top 到栈顶部

IsEmpty判断是否为空

用堆栈反转字符串：

 1 #include <iostream>
 2 #include<stack>
 3 #define MAX_SIZE 51
 4 
 5 void Reverse(char* c, int n)
 6 {
 7     std::stack<char> s;
 8     for (int i = 0; i < n; i++)
 9         s.push(c[i]);
10 
11     for (int i = 0; i < n; i++)
12     {
13         c[i] = s.top();
14         s.pop();
15     }
16 }
17 int main()
18 {   
19     char c[MAX_SIZE];
20     std::cin >> c;
21     Reverse(c, strlen(c));
22     std::cout << c << std::endl;
23     std::cin.get();
24     return 0;
25 }

View Code

用堆栈反转链表：

 1 #include <iostream>
 2 #include<stack>
 3 
 4 struct Node
 5 {
 6     int data;
 7     Node* next;
 8 };
 9 
10 static Node* head;
11 
12 void Reverse()
13 {
14     std::stack<Node*> s;
15     Node* temp = head;
16 
17     while (temp != nullptr)
18     {
19         s.push(temp);
20         temp = temp->next;
21     }
22         
23     head = s.top();
24     temp = s.top();
25     s.pop();
26     while (!s.empty())
27     {
28         temp->next = s.top;
29         s.pop();
30         temp = temp->next;
31     }
32     temp->next = nullptr;
33 
34 }

View Code

用堆栈判断括号是否匹配：

 1 #include <iostream>
 2 #include <stack>
 3 #include <string>
 4 
 5 bool CheakIt(char open, char end)
 6 {
 7     if ('(' == open && ')' == end) return true;
 8     else if ('[' == open && ']' == end) return true;
 9     else if ('{' == open && '}' == end) return true;
10     return false;
11 }
12 
13 bool Cheak(std::string str)
14 {
15     std::stack<char> ST;
16     for (int i = 0; i < str.length(); i++)
17     {
18         if ('(' == str[i] || '[' == str[i] || '{' == str[i])
19         {
20             ST.push(str[i]);
21         }
22         else if (')' == str[i] || ']' == str[i] || '}' == str[i])
23         {
24             if (ST.empty() || !CheakIt(ST.top(), str[i]))
25                 return false;
26             else
27                 ST.pop();
28         }
29     }
30     return ST.empty() ? true : false;
31 }
32 
33 int main()
34 {
35     bool IsTrue = Cheak("(((({}))))");
36     std::cout << "This string is " << IsTrue << std::endl;
37     std::cin.get();
38     return 0;
39 }

View Code

中缀，前缀，后缀：

后缀用堆栈实现，前缀从最后一位开始操作即可

 1 #include <iostream>
 2 #include <stack>
 3 #include <string>
 4 
 5 int GetResule(std::string str)
 6 {
 7     std::stack<int> st;
 8     for (int  i = 0; i < str.length(); i++)
 9     {
10         if ('+' != str[i] && '-' != str[i] && '*' != str[i] && '/' != str[i])
11             st.push((str[i]) - '0');        //把符号前面的操作数压入栈中
12         else
13         {
14             int open, end;
15             open = st.top();       //遇到符号则取出栈中的操作数进行操作
16             st.pop();
17             end = st.top();
18             st.pop();
19             switch (str[i])
20             {
21             case '+':st.push(open + end); break;
22             case '-':st.push(open - end); break;
23             case '*':st.push(open * end); break;
24             case '/':st.push(open / end); break;
25             }
26         }
27     }
28     return st.top();
29 }
30 
31 int main()
32 {
33     int x = GetResule("123*+");
34     std::cout << x << std::endl;
35     std::cin.get();
36     return 0;
37 }

View Code

把中缀转换为后缀：

 1 #include <iostream>
 2 #include <stack>
 3 #include <string>
 4 
 5 bool CheakMax(char open, char end)
 6 {
 7     if ('+' == open && ('*' == end || '/' == end)) return true;
 8     else if ('-' == open && ('*' == end || '/' == end)) return true;
 9     else if (('+' == open || '-' == open ) && ('+' == end || '-' == end)) return true;
10     else if (('*' == open || '/' == open) && ('*' == end || '/' == end)) return true;
11     return false;
12 }
13 
14 std::string  GetResule(std::string str)
15 {
16     std::stack<char> st;
17     std::string temp;
18     for (int  i = 0; i < str.length(); i++)
19     {
20         if ('+' != str[i] && '-' != str[i] && '*' != str[i] && '/' != str[i])
21             temp.append(1, str[i]);
22         else
23         {
24             while (!st.empty() && CheakMax(str[i], st.top()))
25             {
26                 temp.append(1, st.top());
27                 st.pop();
28             }
29             st.push(str[i]);
30         }
31     }
32     while (!st.empty())
33     {
34         temp.append(1, st.top());
35         st.pop();
36     }
37     return temp;
38 }
39 
40 int main()
41 {
42     std::string x = GetResule("1+2*3-5*6");
43     std::cout << x << std::endl;
44     std::cin.get();
45     return 0;
46 }

View Code

P22：队列（Queue），队列的用处一般是共享资源的使用。比如服务器的处理。

用数组实现队列：

 1 #include <iostream>
 2 #include <stack>
 3 #include <string>
 4 #define MAX_SIZE 101
 5 using namespace std;
 6 //为什么要使用 【%MAX_SIZE】 操作，主要是为了当 rear+1 = MAX_SIZE 时，且队列没有满的情况下，
 7 //我们的数组大小只有MAX_SIZE大，所有必须把rear+1置为0，所以进行了取余操作
 8 class Queue
 9 {
10 private:
11     int Arr[MAX_SIZE];
12     int front, rear;
13 public:
14     Queue()
15     {
16         front = -1;
17         rear = -1;
18     }
19 
20     bool IsFull()           //判断队列是否是满的
21     {
22         return (rear + 1) % MAX_SIZE == front ? true : false;   
23     }
24 
25     bool IsEmpty()          //判断队列是否是空的
26     {
27         return (-1 == rear && -1 == front) ? true : false;
28     }
29 
30     void Enqueue(int x)     //往对列中增加元素
31     {
32         if (IsFull())
33             return;
34         else if(IsEmpty())
35             front = rear = 0;            
36         else
37             rear = (rear + 1) % MAX_SIZE;
38         Arr[rear] = x;
39     }
40 
41     void Dequeue()         //删除队列中元素
42     {
43         if (IsEmpty())
44             return;
45         else if (front == rear)
46             front = rear = -1;            
47         else
48             front = (front + 1) % MAX_SIZE;
49     }
50 
51     void Print()
52     {//这里的MAX_SIZE和上面的其实是一个道理，写成（（rear-front）+MAX_SIZE） % MAX_SIZE或许更好理解
53      //当我们打印时，是从头到尾，因为是循环队列，所以存在rear在我们数组的[1]这样的位置，所以我们就利用
54      //real和front间隔的距离+我们的元素的数量，因为在括号外，我们会进行取余操作，所以如果距离为正数，那么相当于
55      //MAX_SIZE被除干净了，没有起作用。当距离是负数的时候，我们加上MAX_SIZE就是他们之间的真正的距离。
56         int length = (rear + MAX_SIZE - front) % MAX_SIZE + 1;
57         for (int i = 0; i < length; i++)
58             cout << Arr[i];
59         cout << "" << endl;
60     }
61 };
62 
63 int main()
64 {
65     Queue queue;
66     queue.Enqueue(5); queue.Print();
67     queue.Enqueue(4); queue.Print();
68     queue.Enqueue(3); queue.Print();
69     queue.Enqueue(2); queue.Print();
70     queue.Enqueue(1); queue.Print();
71     std::cin.get();
72     return 0;
73 }

View Code

用链表实现队列：

 1 #include <iostream>
 2 using namespace std;
 3 
 4 struct Node
 5 {
 6     int data;
 7     Node* next;
 8 };
 9 
10 class Queue
11 {
12 private:
13     Node*front, *rear;
14 public:
15     Queue()
16     {
17         front = rear = nullptr;
18     }
19 
20     void Enqueue(int x)     //往对列中增加元素
21     {
22         Node* temp = new Node();
23         temp->data = x;
24         if (nullptr == front && nullptr == rear)
25             front = rear = temp;
26         else
27         {
28             rear->next = temp;
29             rear = temp;
30         }
31     }
32 
33     void Dequeue()         //删除队列中元素
34     {
35         Node* temp = front;
36         if (nullptr == front && nullptr == rear) return;
37         else if (front == rear)  front = rear = nullptr;
38         else front = front->next;            
39         delete temp;
40     }
41 
42     void Print()
43     {
44         Node* temp = front;
45         while (temp != nullptr)
46         {
47             cout << temp->data;
48             temp = temp->next;
49         }
50         cout << "" << endl;
51     }
52 };
53 
54 int main()
55 {
56     Queue queue;
57     queue.Enqueue(5); queue.Print();
58     queue.Enqueue(4); queue.Print();
59     queue.Enqueue(3); queue.Print();
60     queue.Enqueue(2); queue.Print();
61     queue.Enqueue(1); queue.Print();
62     queue.Dequeue(); queue.Print();
63     std::cin.get();
64     return 0;
65 }

View Code

P25：树

树一般的应用：1、自然分层数据 2、组织数据，进行快速的删除，搜索 3、数据字典 4、网络路由算法

二叉树：一个节点最多只有两个分支。

完美二叉树：所有的节点都是二叉结构元素数：2^(h+1) - 1 = h^0 + h^1 + h^2 + h^3..........

完整二叉树：所有的节点尽可能的在左边

BST（Binary Search Tree）（二叉搜素树）：每个节点的值大于其任意左侧子节点的值，小于其任意右节点的值。

 1 #include <iostream>
 2 using namespace std;
 3 
 4 struct BstNode
 5 {
 6     int data;
 7     BstNode* left;
 8     BstNode* right;
 9 };
10 
11 class cBstNode
12 {
13 private:
14     BstNode *left, *right;
15 public:
16     cBstNode()
17     {
18         left = right = nullptr;
19     }
20 
21     BstNode* GetNewNode(int data)
22     {
23         BstNode* newNode = new BstNode();
24         newNode->data = data;
25         newNode->left = newNode->right = nullptr;
26         return newNode;
27     }
28 
29     BstNode* Insert(BstNode* root, int data)
30     {
31         if (nullptr == root)
32             root = GetNewNode(data);
33         else if(data <= root->data)
34             root->left = Insert(root->left, data);
35         else
36             root->right = Insert(root->right, data);
37         return root;
38     }
39 
40     BstNode* Search(BstNode* root, int data)
41     {
42         if (nullptr == root) {}
43         else if (root->data == data) {}
44         else if (data <= root->data)
45             root = Search(root->left, data);
46         else
47             root = Search(root->right, data);
48         return root;
49     }
50 
51 };
52 
53 int main()
54 {
55     cBstNode CBT;
56     BstNode* root = nullptr;
57     root = CBT.Insert(root, 20);
58     root = CBT.Insert(root, 18);
59     root = CBT.Insert(root, 25);
60     root = CBT.Insert(root, 16);
61     root = CBT.Insert(root, 23);
62     if (CBT.Search(root, 28) == nullptr)
63         cout << "不在bst中";
64     else 
65         cout << "在bst中";
66     std::cin.get();
67     return 0;
68 }

View Code

求最大和最小值

 1     void FindMin(BstNode *root)    //使用迭代
 2     {
 3         if (nullptr == root) return ;
 4         while (root->left != nullptr)
 5             root = root->left;
 6         cout << root->data;
 7     }
 8 
 9     void FindMax(BstNode *root)     //使用递归
10     {
11         if (nullptr == root->right) cout << root->data << endl;
12         else FindMax(root->right);
13     }

View Code

对于二叉树的高度和深度是相反的表示，深度是从上到下数的，而高度是从下往上数。

求二叉树的高度

 1     int Max(int a, int b)
 2     {
 3         if (a >= b) return a;
 4         else return b;
 5     }
 6 
 7     int FindHeight(BstNode* root)
 8     {
 9         if (nullptr == root)
10             return -1;
11         else
12             return Max(FindHeight(root->left), FindHeight(root->right)) + 1;
13     }

View Code

总结深度优先和广度优先的区别：

https://www.cnblogs.com/attitudeY/p/6790219.html

以广度优先的搜索方式搜索：时间复杂度：O(n)，空间复杂度：O(n)

 1     void LevelOrder(BstNode* root)
 2     {
 3         if (nullptr == root) return;
 4         queue<BstNode*> que;
 5         que.push(root);
 6         while (!que.empty())
 7         {
 8             BstNode* temp = que.front();
 9             cout << temp->data << " ";
10             if (temp->left != nullptr) que.push(temp->left);
11             if (temp->right != nullptr) que.push(temp->right);
12             que.pop();
13         }
14     }

View Code

对于深度搜素我们三种方式：分别是DLR（先序遍历），LDR（中序遍历）、LRD（后续遍历），不同的只是根（root）的位置，左右的顺序不会变，都是从左到右。其中D代表的是root，L代表left，R代表right。

 1     void PrevOrder(BstNode* root)    //先序搜索
 2     {
 3         if (nullptr == root) return;
 4         cout << root->data << " ";
 5         PrevOrder(root->left);
 6         PrevOrder(root->right);
 7     }
 8 
 9     void InOrder(BstNode* root)    //中序搜索
10     {
11         if (nullptr == root) return;        
12         InOrder(root->left);
13         cout << root->data << " ";
14         InOrder(root->right);
15     }
16 
17     void PostOrder(BstNode* root)    //后序搜索
18     {
19         if (nullptr == root) return;        
20         PostOrder(root->left);
21         PostOrder(root->right);
22         cout << root->data << " ";
23     }

View Code

删除二进制搜索树中的节点：

（1）、如果删除的是叶节点，则直接删除

（2）、如果是单子节点，只有左或者右节点，则删除节点，链接下一个节点

（3）、如果删除的节点左右子节点都有，则可以把左子节点中的最大值的节点（或者右节点中最小值的节点）替换此节点，然后删除此节点

 1     BstNode* Delete(BstNode* root , int data)
 2     {
 3         if (nullptr == root) return nullptr;
 4         else if (data < root->data) root->left = Delete(root->left, data);
 5         else if (data > root->data) root->right = Delete(root->right, data);
 6         else
 7         {    //当双子节点都是空的时候
 8             if (nullptr == root->left && nullptr == root->right)
 9             {
10                 delete root;
11                 root = nullptr;                
12             } //当左子节点为空时
13             else if(nullptr == root->left)
14             {
15                 BstNode *temp = root;
16                 root = root->right;
17                 delete temp;
18             } //当右子节点为空时
19             else if (nullptr == root->right)
20             {
21                 BstNode *temp = root;
22                 root = root->left;
23                 delete temp;
24             } //字节点都不为空时
25             else 
26             {
27                 BstNode *temp = FindMax(root->right);
28                 root->data = temp->data;
29                 root->right = Delete(root->right, temp->data);   //这里删除跟我们刚开始从root删的想法一样，删掉那个我们用过的数字的值即可。
30             }            
31         }
32         return root;
33     }

View Code

P38：