資料結構與算法---樹結構(Tree structure)
為什麼需要樹這種資料結構
數組存儲方式的分析
- 優點：通過下标方式通路元素，速度快。對于有序數組，還可使用二分查找提高檢索速度。
- 缺點：如果要檢索具體某個值，或者插入值(按一定順序)會整體移動，效率較低。
鍊式存儲方式的分析
- 優點：在一定程度上對數組存儲方式有優化(比如：插入一個數值節點，隻需要将插入節點，連結到連結清單中即可， 删除效率也很好)。
- 缺點：在進行檢索時，效率仍然較低，比如(檢索某個值，需要從頭節點開始周遊)
樹存儲方式的分析
能提高資料存儲，讀取的效率, 比如利用 二叉排序樹(Binary Sort Tree)，既可以保證資料的檢索速度，同時也可以保證資料的插入，删除，修改的速度。
樹結構示意圖
二叉樹的概念
- 樹有很多種，每個節點最多隻能有兩個子節點的一種形式稱為二叉樹。
- 二叉樹的子節點分為左節點和右節點。
- 如果該二叉樹的所有葉子節點都在最後一層，并且結點總數= 2^n -1 , n 為層數，則我們稱為滿二叉樹。
- 如果該二叉樹的所有葉子節點都在最後一層或者倒數第二層，而且最後一層的葉子節點在左邊連續，倒數第二層的葉子節點在右邊連續，我們稱為完全二叉樹。
二叉樹周遊的說明
前序周遊: 先輸出父節點，再周遊左子樹和右子樹
中序周遊: 先周遊左子樹，再輸出父節點，再周遊右子樹
後序周遊: 先周遊左子樹，再周遊右子樹，最後輸出父節點
小結: 看輸出父節點的順序，就确定是前序，中序還是後序
示例：
将下列二叉樹 前序、中序、後序輸出
1 package com.tree;
2
3 /**
4 * Created by wanbf on 2019/7/9.
5 */
6
7 public class BinaryTreeDemo {
8
9 public static void main(String[] args) {
10 //先需要建立一顆二叉樹
11 BinaryTree binaryTree = new BinaryTree();
12 //建立需要的結點
13 HeroNode root = new HeroNode(1, "宋江");
14 HeroNode node2 = new HeroNode(2, "吳用");
15 HeroNode node3 = new HeroNode(3, "盧俊義");
16 HeroNode node4 = new HeroNode(4, "林沖");
17 //HeroNode node5 = new HeroNode(5, "關勝");
18
19 //說明，我們先手動建立該二叉樹，後面我們學習遞歸的方式建立二叉樹
20 root.setLeft(node2);
21 root.setRight(node3);
22 node3.setRight(node4);
23 //node3.setLeft(node5);
24 binaryTree.setRoot(root);
25
26 //測試
27 System.out.println("前序周遊"); // 1,2,3,4
28 binaryTree.preOrder();
29
30 //測試
31 System.out.println("中序周遊");
32 binaryTree.infixOrder(); // 2,1,3,4
33
34 System.out.println("後序周遊");
35 binaryTree.postOrder(); // 2,4,3,1
36
37 }
38
39 }
40
41
42
43
44 //定義BinaryTree 二叉樹
45 class BinaryTree {
46 private HeroNode root;
47
48 public void setRoot(HeroNode root) {
49 this.root = root;
50 }
51 //前序周遊
52 public void preOrder() {
53 if(this.root != null) {
54 this.root.preOrder();
55 }else {
56 System.out.println("二叉樹為空，無法周遊");
57 }
58 }
59
60 //中序周遊
61 public void infixOrder() {
62 if(this.root != null) {
63 this.root.infixOrder();
64 }else {
65 System.out.println("二叉樹為空，無法周遊");
66 }
67 }
68 //後序周遊
69 public void postOrder() {
70 if(this.root != null) {
71 this.root.postOrder();
72 }else {
73 System.out.println("二叉樹為空，無法周遊");
74 }
75 }
76 }
77
78
79 //先建立HeroNode 結點
80 class HeroNode {
81 private int no;
82 private String name;
83 private HeroNode left; //預設null
84 private HeroNode right; //預設null
85 public HeroNode(int no, String name) {
86 this.no = no;
87 this.name = name;
88 }
89 public int getNo() {
90 return no;
91 }
92 public void setNo(int no) {
93 this.no = no;
94 }
95 public String getName() {
96 return name;
97 }
98 public void setName(String name) {
99 this.name = name;
100 }
101 public HeroNode getLeft() {
102 return left;
103 }
104 public void setLeft(HeroNode left) {
105 this.left = left;
106 }
107 public HeroNode getRight() {
108 return right;
109 }
110 public void setRight(HeroNode right) {
111 this.right = right;
112 }
113 @Override
114 public String toString() {
115 return "HeroNode [no=" + no + ", name=" + name + "]";
116 }
117
118 //編寫前序周遊的方法
119 public void preOrder() {
120 System.out.println(this); //先輸出父結點
121 //遞歸向左子樹前序周遊
122 if(this.left != null) {
123 this.left.preOrder();
124 }
125 //遞歸向右子樹前序周遊
126 if(this.right != null) {
127 this.right.preOrder();
128 }
129 }
130 //中序周遊
131 public void infixOrder() {
132
133 //遞歸向左子樹中序周遊
134 if(this.left != null) {
135 this.left.infixOrder();
136 }
137 //輸出父結點
138 System.out.println(this);
139 //遞歸向右子樹中序周遊
140 if(this.right != null) {
141 this.right.infixOrder();
142 }
143 }
144 //後序周遊
145 public void postOrder() {
146 if(this.left != null) {
147 this.left.postOrder();
148 }
149 if(this.right != null) {
150 this.right.postOrder();
151 }
152 System.out.println(this);
153 }
154 } 代碼
1 前序周遊
2 HeroNode [no=1, name=宋江]
3 HeroNode [no=2, name=吳用]
4 HeroNode [no=3, name=盧俊義]
5 HeroNode [no=4, name=林沖]
6 中序周遊
7 HeroNode [no=2, name=吳用]
8 HeroNode [no=1, name=宋江]
9 HeroNode [no=3, name=盧俊義]
10 HeroNode [no=4, name=林沖]
11 後序周遊
12 HeroNode [no=2, name=吳用]
13 HeroNode [no=4, name=林沖]
14 HeroNode [no=3, name=盧俊義]
15 HeroNode [no=1, name=宋江] 輸出
前上圖的 3号節點 "盧俊" , 增加一個左子節點 [5, 關勝]
使用前序，中序，後序周遊，請寫出各自輸出的順序是什麼?
1 public static void main(String[] args) {
2 //先需要建立一顆二叉樹
3 BinaryTree binaryTree = new BinaryTree();
4 //建立需要的結點
5 HeroNode root = new HeroNode(1, "宋江");
6 HeroNode node2 = new HeroNode(2, "吳用");
7 HeroNode node3 = new HeroNode(3, "盧俊義");
8 HeroNode node4 = new HeroNode(4, "林沖");
9 HeroNode node5 = new HeroNode(5, "關勝");
10
11 //說明，我們先手動建立該二叉樹，後面我們學習遞歸的方式建立二叉樹
12 root.setLeft(node2);
13 root.setRight(node3);
14 node3.setRight(node4);
15 node3.setLeft(node5);
16 binaryTree.setRoot(root);
17
18 //測試
19 System.out.println("前序周遊"); // 1,2,3,5,4
20 binaryTree.preOrder();
21
22 //測試
23 System.out.println("中序周遊");
24 binaryTree.infixOrder(); // 2,1,5,3,4
25
26 System.out.println("後序周遊");
27 binaryTree.postOrder(); // 2,5,4,3,1
28
29 } 代碼
1 前序周遊
2 HeroNode [no=1, name=宋江]
3 HeroNode [no=2, name=吳用]
4 HeroNode [no=3, name=盧俊義]
5 HeroNode [no=5, name=關勝]
6 HeroNode [no=4, name=林沖]
7 中序周遊
8 HeroNode [no=2, name=吳用]
9 HeroNode [no=1, name=宋江]
10 HeroNode [no=5, name=關勝]
11 HeroNode [no=3, name=盧俊義]
12 HeroNode [no=4, name=林沖]
13 後序周遊
14 HeroNode [no=2, name=吳用]
15 HeroNode [no=5, name=關勝]
16 HeroNode [no=4, name=林沖]
17 HeroNode [no=3, name=盧俊義]
18 HeroNode [no=1, name=宋江] 輸出
二叉樹-查找指定節點
1.編寫前序查找，中序查找和後序查找的方法。
2.并分别使用三種查找方式，查找 heroNO = 5 的節點
3.并分析各種查找方式，分别比較了多少次
思路分析
1 /**
2 * Created by wanbf on 2019/7/9.
3 */
4 public class BinaryTreeDemo {
5
6 public static void main(String[] args) {
7 //先需要建立一顆二叉樹
8 BinaryTree binaryTree = new BinaryTree();
9 //建立需要的結點
10 HeroNode root = new HeroNode(1, "宋江");
11 HeroNode node2 = new HeroNode(2, "吳用");
12 HeroNode node3 = new HeroNode(3, "盧俊義");
13 HeroNode node4 = new HeroNode(4, "林沖");
14 HeroNode node5 = new HeroNode(5, "關勝");
15
16 //說明，我們先手動建立該二叉樹，後面我們學習遞歸的方式建立二叉樹
17 root.setLeft(node2);
18 root.setRight(node3);
19 node3.setRight(node4);
20 node3.setLeft(node5);
21 binaryTree.setRoot(root);
22
23 //前序周遊
24 //前序周遊的次數 ：4
25 System.out.println("前序周遊方式~~~");
26 HeroNode resNode = binaryTree.preOrderSearch(5);
27 if (resNode != null) {
28 System.out.printf("找到了，資訊為 no=%d name=%s", resNode.getNo(), resNode.getName());
29 } else {
30 System.out.printf("沒有找到 no = %d 的英雄", 5);
31 }
32
33 //中序周遊查找
34 //中序周遊3次
35 System.out.println("中序周遊方式~~~");
36 HeroNode resNode = binaryTree.infixOrderSearch(5);
37 if (resNode != null) {
38 System.out.printf("找到了，資訊為 no=%d name=%s", resNode.getNo(), resNode.getName());
39 } else {
40 System.out.printf("沒有找到 no = %d 的英雄", 5);
41 }
42
43 //後序周遊查找
44 //後序周遊查找的次數 2次
45 System.out.println("後序周遊方式~~~");
46 HeroNode resNode = binaryTree.postOrderSearch(5);
47 if (resNode != null) {
48 System.out.printf("找到了，資訊為 no=%d name=%s", resNode.getNo(), resNode.getName());
49 } else {
50 System.out.printf("沒有找到 no = %d 的英雄", 5);
51 }
52 }
53
54 }
55
56 //定義BinaryTree 二叉樹
57 class BinaryTree {
58 private HeroNode root;
59
60 public void setRoot(HeroNode root) {
61 this.root = root;
62 }
63 //前序周遊查找
64 public HeroNode preOrderSearch(int no) {
65 if(root != null) {
66 return root.preOrderSearch(no);
67 } else {
68 return null;
69 }
70 }
71 //中序周遊查找
72 public HeroNode infixOrderSearch(int no) {
73 if(root != null) {
74 return root.infixOrderSearch(no);
75 }else {
76 return null;
77 }
78 }
79 //後序周遊查找
80 public HeroNode postOrderSearch(int no) {
81 if(root != null) {
82 return this.root.postOrderSearch(no);
83 }else {
84 return null;
85 }
86 }
87 }
88
89 //先建立HeroNode 結點
90 class HeroNode {
91 private int no;
92 private String name;
93 private HeroNode left; //預設null
94 private HeroNode right; //預設null
95 public HeroNode(int no, String name) {
96 this.no = no;
97 this.name = name;
98 }
99 public int getNo() {
100 return no;
101 }
102 public void setNo(int no) {
103 this.no = no;
104 }
105 public String getName() {
106 return name;
107 }
108 public void setName(String name) {
109 this.name = name;
110 }
111 public HeroNode getLeft() {
112 return left;
113 }
114 public void setLeft(HeroNode left) {
115 this.left = left;
116 }
117 public HeroNode getRight() {
118 return right;
119 }
120 public void setRight(HeroNode right) {
121 this.right = right;
122 }
123 @Override
124 public String toString() {
125 return "HeroNode [no=" + no + ", name=" + name + "]";
126 }
127 //前序周遊查找
128 /**
129 *
130 * @param no 查找no
131 * @return 如果找到就傳回該Node ,如果沒有找到傳回 null
132 */
133 public HeroNode preOrderSearch(int no) {
134 System.out.println("進入前序周遊");
135 //比較目前結點是不是
136 if(this.no == no) {
137 return this;
138 }
139 //1.則判斷目前結點的左子節點是否為空，如果不為空，則遞歸前序查找
140 //2.如果左遞歸前序查找，找到結點，則傳回
141 HeroNode resNode = null;
142 if(this.left != null) {
143 resNode = this.left.preOrderSearch(no);
144 }
145 if(resNode != null) {//說明我們左子樹找到
146 return resNode;
147 }
148 //1.左遞歸前序查找，找到結點，則傳回，否繼續判斷，
149 //2.目前的結點的右子節點是否為空，如果不空，則繼續向右遞歸前序查找
150 if(this.right != null) {
151 resNode = this.right.preOrderSearch(no);
152 }
153 return resNode;
154 }
155
156 //中序周遊查找
157 public HeroNode infixOrderSearch(int no) {
158 //判斷目前結點的左子節點是否為空，如果不為空，則遞歸中序查找
159 HeroNode resNode = null;
160 if(this.left != null) {
161 resNode = this.left.infixOrderSearch(no);
162 }
163 if(resNode != null) {
164 return resNode;
165 }
166 System.out.println("進入中序查找");
167 //如果找到，則傳回，如果沒有找到，就和目前結點比較，如果是則傳回目前結點
168 if(this.no == no) {
169 return this;
170 }
171 //否則繼續進行右遞歸的中序查找
172 if(this.right != null) {
173 resNode = this.right.infixOrderSearch(no);
174 }
175 return resNode;
176
177 }
178
179 //後序周遊查找
180 public HeroNode postOrderSearch(int no) {
181
182 //判斷目前結點的左子節點是否為空，如果不為空，則遞歸後序查找
183 HeroNode resNode = null;
184 if(this.left != null) {
185 resNode = this.left.postOrderSearch(no);
186 }
187 if(resNode != null) {//說明在左子樹找到
188 return resNode;
189 }
190
191 //如果左子樹沒有找到，則向右子樹遞歸進行後序周遊查找
192 if(this.right != null) {
193 resNode = this.right.postOrderSearch(no);
194 }
195 if(resNode != null) {
196 return resNode;
197 }
198 System.out.println("進入後序查找");
199 //如果左右子樹都沒有找到，就比較目前結點是不是
200 if(this.no == no) {
201 return this;
202 }
203 return resNode;
204 }
205
206 } 代碼
1 前序周遊方式~~~
2 進入前序周遊
3 進入前序周遊
4 進入前序周遊
5 進入前序周遊
6 找到了，資訊為 no=5 name=關勝中序周遊方式~~~
7 進入中序查找
8 進入中序查找
9 進入中序查找
10 找到了，資訊為 no=5 name=關勝後序周遊方式~~~
11 進入後序查找
12 進入後序查找
13 找到了，資訊為 no=5 name=關勝 輸出
二叉樹-删除節點
定義：
- 如果删除的節點是葉子節點，則删除該節點
- 如果删除的節點是非葉子節點，則删除該子樹.
思路分析：
實作删除代碼：
1 //定義BinaryTree 二叉樹
2 class BinaryTree {
3 private HeroNode root;
4
5 public void setRoot(HeroNode root) {
6 this.root = root;
7 }
8
9 //删除結點
10 public void delNode(int no) {
11 if(root != null) {
12 //如果隻有一個root結點, 這裡立即判斷root是不是就是要删除結點
13 if(root.getNo() == no) {
14 root = null;
15 } else {
16 //遞歸删除
17 root.delNode(no);
18 }
19 }else{
20 System.out.println("空樹，不能删除~");
21 }
22 }
23 }
24 class HeroNode {
25 private int no;
26 private String name;
27 private HeroNode left; //預設null
28 private HeroNode right; //預設null
29 public HeroNode(int no, String name) {
30 this.no = no;
31 this.name = name;
32 }
33 public int getNo() {
34 return no;
35 }
36 public void setNo(int no) {
37 this.no = no;
38 }
39 public String getName() {
40 return name;
41 }
42 public void setName(String name) {
43 this.name = name;
44 }
45 public HeroNode getLeft() {
46 return left;
47 }
48 public void setLeft(HeroNode left) {
49 this.left = left;
50 }
51 public HeroNode getRight() {
52 return right;
53 }
54 public void setRight(HeroNode right) {
55 this.right = right;
56 }
57 @Override
58 public String toString() {
59 return "HeroNode [no=" + no + ", name=" + name + "]";
60 }
61 //遞歸删除結點
62 //1.如果删除的節點是葉子節點，則删除該節點
63 //2.如果删除的節點是非葉子節點，則删除該子樹
64 public void delNode(int no) {
65
66 //思路
67 /*
68 * 1. 因為我們的二叉樹是單向的，是以我們是判斷目前結點的子結點是否需要删除結點，而不能去判斷目前這個結點是不是需要删除結點.
69 2. 如果目前結點的左子結點不為空，并且左子結點 就是要删除結點，就将this.left = null; 并且就傳回(結束遞歸删除)
70 3. 如果目前結點的右子結點不為空，并且右子結點 就是要删除結點，就将this.right= null ;并且就傳回(結束遞歸删除)
71 4. 如果第2和第3步沒有删除結點，那麼我們就需要向左子樹進行遞歸删除
72 5. 如果第4步也沒有删除結點，則應當向右子樹進行遞歸删除.
73
74 */
75 //2. 如果目前結點的左子結點不為空，并且左子結點 就是要删除結點，就将this.left = null; 并且就傳回(結束遞歸删除)
76 if(this.left != null && this.left.no == no) {
77 this.left = null;
78 return;
79 }
80 //3.如果目前結點的右子結點不為空，并且右子結點 就是要删除結點，就将this.right= null ;并且就傳回(結束遞歸删除)
81 if(this.right != null && this.right.no == no) {
82 this.right = null;
83 return;
84 }
85 //4.我們就需要向左子樹進行遞歸删除
86 if(this.left != null) {
87 this.left.delNode(no);
88 }
89 //5.則應當向右子樹進行遞歸删除
90 if(this.right != null) {
91 this.right.delNode(no);
92 }
93 }
94 } 代碼
測試：
1 public static void main(String[] args) {
2 //先需要建立一顆二叉樹
3 BinaryTree binaryTree = new BinaryTree();
4 //建立需要的結點
5 HeroNode root = new HeroNode(1, "宋江");
6 HeroNode node2 = new HeroNode(2, "吳用");
7 HeroNode node3 = new HeroNode(3, "盧俊義");
8 HeroNode node4 = new HeroNode(4, "林沖");
9 HeroNode node5 = new HeroNode(5, "關勝");
10
11 //說明，我們先手動建立該二叉樹，後面我們學習遞歸的方式建立二叉樹
12 root.setLeft(node2);
13 root.setRight(node3);
14 node3.setRight(node4);
15 node3.setLeft(node5);
16 binaryTree.setRoot(root);
17 System.out.println("删除前,前序周遊");
18 binaryTree.preOrder(); // 1,2,3,5,4
19 binaryTree.delNode(5);
20 //binaryTree.delNode(3);
21 System.out.println("删除後，前序周遊");
22 binaryTree.preOrder(); // 1,2,3,4
23 }
24 輸出：
25 删除前,前序周遊
26 HeroNode [no=1, name=宋江]
27 HeroNode [no=2, name=吳用]
28 HeroNode [no=3, name=盧俊義]
29 HeroNode [no=5, name=關勝]
30 HeroNode [no=4, name=林沖]
31 删除後，前序周遊
32 HeroNode [no=1, name=宋江]
33 HeroNode [no=2, name=吳用]
34 HeroNode [no=3, name=盧俊義]
35 HeroNode [no=4, name=林沖]
36 如果是删除binaryTree.delNode(3);
37 則輸出：
38 删除前,前序周遊
39 HeroNode [no=1, name=宋江]
40 HeroNode [no=2, name=吳用]
41 HeroNode [no=3, name=盧俊義]
42 HeroNode [no=5, name=關勝]
43 HeroNode [no=4, name=林沖]
44 删除後，前序周遊
45 HeroNode [no=1, name=宋江]
46 HeroNode [no=2, name=吳用] 代碼
拓展：
上面我們定義了兩個删除規則，那麼我們考慮另外删除規則又怎麼實作。‘
如果要删除的節點是非葉子節點，現在我們不希望将該非葉子節點為根節點的子樹删除，需要指定規則, 假如規定如下:
- 如果該非葉子節點A隻有一個子節點B，則子節點B替代節點A
- 如果該非葉子節點A有左子節點B和右子節點C，則讓左子節點B替代節點A。
這個代碼實作在後序講二叉排序樹時，在講解具體的删除方法。
順序存儲二叉樹
順序存儲二叉樹的概念
基本說明
從資料存儲來看，數組存儲方式和樹 的存儲方式可以互相轉換，即數組可 以轉換成樹，樹也可以轉換成數組， 看示意圖。
要求:
- 上圖的二叉樹的結點，要求以數組的方式來存放 arr : [1, 2, 3, 4, 5, 6, 7]
- 要求在周遊數組 arr時，仍然可以以前序周遊，中序周遊和後序周遊的方式完成結點的周遊
順序存儲二叉樹的特點:
- 順序二叉樹通常隻考慮完全二叉樹
- 第n個元素的左子節點為 2 * n + 1
- 第n個元素的右子節點為 2 * n + 2
- 第n個元素的父節點為 (n-1) / 2
- n : 表示二叉樹中的第幾個元素
需求: 給你一個數組 {1,2,3,4,5,6,7}，要求以二叉樹前序周遊的方式進行周遊。 前序周遊的結果應當為 1,2,4,5,3,6,7
1 public class ArrBinaryTreeDemo {
2
3 public static void main(String[] args) {
4 int[] arr = { 1, 2, 3, 4, 5, 6, 7 };
5 //建立一個 ArrBinaryTree
6 ArrBinaryTree arrBinaryTree = new ArrBinaryTree(arr);
7 arrBinaryTree.preOrder(); // 1,2,4,5,3,6,7
8 }
9
10 }
11
12 //編寫一個ArrayBinaryTree, 實作順序存儲二叉樹周遊
13
14 class ArrBinaryTree {
15 private int[] arr;//存儲資料結點的數組
16
17 public ArrBinaryTree(int[] arr) {
18 this.arr = arr;
19 }
20
21 //重載preOrder
22 public void preOrder() {
23 this.preOrder(0);
24 }
25
26 //編寫一個方法，完成順序存儲二叉樹的前序周遊
27 /**
28 *
29 * @param index 數組的下标
30 */
31 public void preOrder(int index) {
32 //如果數組為空，或者 arr.length = 0
33 if(arr == null || arr.length == 0) {
34 System.out.println("數組為空，不能按照二叉樹的前序周遊");
35 }
36 //輸出目前這個元素
37 System.out.println(arr[index]);
38 //向左遞歸周遊
39 if((index * 2 + 1) < arr.length) {
40 preOrder(2 * index + 1 );
41 }
42 //向右遞歸周遊
43 if((index * 2 + 2) < arr.length) {
44 preOrder(2 * index + 2);
45 }
46 }
47
48 } 代碼
順序存儲二叉樹應用執行個體
八大排序算法中的堆排序，就會使用到順序存儲二叉樹， 關于堆排序後序在講。
posted on 2019-07-10 23:37 wanbf 閱讀(...) 評論(...) 編輯 收藏