Java二叉树的构建与遍历

逃离我推掉我的手 2022-06-11 08:36 171阅读 0赞

一、二叉排序树定义

1.二叉排序树的定义

二叉排序树(Binary Sort Tree)又称二叉查找(搜索)树(Binary Search Tree)。其定义为：二叉排序树或者是空树，或者是满足如下性质的二叉树：  
①若它的左子树非空，则左子树上所有结点的值均小于根结点的值；  
②若它的右子树非空，则右子树上所有结点的值均大于根结点的值；  
③左、右子树本身又各是一棵二叉排序树。

上述性质简称二叉排序树性质(BST性质)，故二叉排序树实际上是满足BST性质的二叉树。

![20150829161932865][]

2.二叉排序树的性质  
按中序遍历二叉排序树，所得到的中序遍历序列是一个递增有序序列。  
  
3.二叉排序树的插入  
在二叉排序树中插入新结点，要保证插入后的二叉树仍符合二叉排序树的定义。 　　  
插入过程：  
若二叉排序树为空，则待插入结点\*S作为根结点插入到空树中； 　　  
当非空时，将待插结点关键字S->key和树根关键字t->key进行比较，若s->key = t->key,则无须插入，若s->key< t->key,则插入到根的左子树中，若s->key> t->key,则插入到根的右子树中。而子树中的插入过程和在树中的插入过程相同，如此进行下去，直到把结点\*s作为一个新的树叶插入到二叉排序树中，或者直到发现树已有相同关键字的结点为止。  
  
4.二叉排序树的查找  
假定二叉排序树的根结点指针为 root ，给定的关键字值为 K ，则查找算法可描述为：  
　　① 置初值： q ＝ root ；  
　　② 如果 K ＝ q －＞ key ，则查找成功，算法结束；  
　　③ 否则，如果 K ＜ q －＞ key ，而且 q 的左子树非空，则将 q 的左子树根送 q ，转步骤②；否则，查找失败，结束算法；  
　　④ 否则，如果 K ＞ q －＞ key ，而且 q 的右子树非空，则将 q 的右子树根送 q ，转步骤②；否则，查找失败，算法结束。  
  
5.二叉排序树的删除  
假设被删结点是\*p，其双亲是\*f，不失一般性，设\*p是\*f的左孩子，下面分三种情况讨论： 　　  
⑴ 若结点\*p是叶子结点，则只需修改其双亲结点\*f的指针即可。 　　  
⑵ 若结点\*p只有左子树PL或者只有右子树PR，则只要使PL或PR 成为其双亲结点的左子树即可。 　　  
⑶ 若结点\*p的左、右子树均非空，先找到\*p的中序前趋(或后继)结点\*s（注意\*s是\*p的左子树中的最右下的结点，它的右链域为空），然后有两种做法：① 令\*p的左子树直接链到\*p的双亲结点\*f的左链上,而\*p的右子树链到\*p的中序前趋结点\*s的右链上。② 以\*p的中序前趋结点\*s代替\*p（即把\*s的数据复制到\*p中），将\*s的左子树链到\*s的双亲结点\*q的左（或右）链上。

6、二叉树的遍历

二叉树的遍历有三种方式，如下：  
（1）前序遍历（DLR），首先访问根结点，然后遍历左子树，最后遍历右子树。简记根-左-右。  
（2）中序遍历（LDR），首先遍历左子树，然后访问根结点，最后遍历右子树。简记左-根-右。  
（3）后序遍历（LRD），首先遍历左子树，然后遍历右子树，最后访问根结点。简记左-右-根。

二、代码编写

1、树节点类的定义

**\[java\]** [view plain][] [copy][view plain]

1.  **package** com.lin; 
2.  /\*\*
3.   \* 功能概要：
4.   \* 
5.   \* @author linbingwen
6.   \* @since 2015年8月29日 
7.   \*/
8.  **public****class** TreeNode \{ 
9.  
10. **public** Integer data; 
11. 
12. /\*该节点的父节点\*/
13. **public** TreeNode parent; 
14. 
15. /\*该节点的左子节点\*/
16. **public** TreeNode left; 
17. 
18. /\*该节点的右子节点\*/
19. **public** TreeNode right; 
20. 
21. **public** TreeNode(Integer data) \{ 
22. **this**.data = data; 
23. 
24.  \} 
25. 
26. @Override
27. **public** String toString() \{ 
28. **return**"TreeNode \[data=" \+ data + "\]"; 
29.  \} 
30. 
31. \}

2、二叉排序树的定义

**\[java\]** [view plain][] [copy][view plain]

1.  **package** com.lin; 
2.  
3.  /\*\*
4.   \* 功能概要：排序/平衡二叉树
5.   \* 
6.   \* @author linbingwen
7.   \* @since 2015年8月29日 
8.   \*/
9.  **public****class** SearchTree \{ 
10. 
11. **public** TreeNode root; 
12. 
13. **public****long** size; 
14. 
15. /\*\*
16.  \* 往树中加节点
17.  \* @author linbingwen
18.  \* @since 2015年8月29日 
19.  \* @param data
20.  \* @return Boolean 插入成功返回true
21.  \*/
22. **public** Boolean addTreeNode(Integer data) \{ 
23. 
24. **if** (**null** == root) \{ 
25.  root = **new** TreeNode(data); 
26.  System.out.println("数据成功插入到平衡二叉树中"); 
27. **return****true**; 
28.  \} 
29. 
30.  TreeNode treeNode = **new** TreeNode(data);// 即将被插入的数据
31.  TreeNode currentNode = root; 
32.  TreeNode parentNode; 
33. 
34. **while** (**true**) \{ 
35.  parentNode = currentNode;// 保存父节点
36. // 插入的数据比父节点小
37. **if** (currentNode.data > data) \{ 
38.  currentNode = currentNode.left; 
39. // 当前父节点的左子节点为空
40. **if** (**null** == currentNode) \{ 
41.  parentNode.left = treeNode; 
42.  treeNode.parent = parentNode; 
43.  System.out.println("数据成功插入到二叉查找树中"); 
44.  size++; 
45. **return****true**; 
46.  \} 
47. // 插入的数据比父节点大
48.  \} **else****if** (currentNode.data < data) \{ 
49.  currentNode = currentNode.right; 
50. // 当前父节点的右子节点为空
51. **if** (**null** == currentNode) \{ 
52.  parentNode.right = treeNode; 
53.  treeNode.parent = parentNode; 
54.  System.out.println("数据成功插入到二叉查找树中"); 
55.  size++; 
56. **return****true**; 
57.  \} 
58.  \} **else** \{ 
59.  System.out.println("输入数据与节点的数据相同"); 
60. **return****false**; 
61.  \} 
62.  \} 
63.  \} 
64. 
65. /\*\*
66.  \* 查找数据
67.  \* @author linbingwen
68.  \* @since 2015年8月29日 
69.  \* @param data
70.  \* @return TreeNode
71.  \*/
72. **public** TreeNode findTreeNode(Integer data)\{ 
73. **if**(**null** == root)\{ 
74. **return****null**; 
75.  \} 
76.  TreeNode current = root; 
77. **while**(current != **null**)\{ 
78. **if**(current.data > data)\{ 
79.  current = current.left; 
80.  \}**else****if**(current.data < data)\{ 
81.  current = current.right; 
82.  \}**else** \{ 
83. **return** current; 
84.  \} 
85. 
86.  \} 
87. **return****null**; 
88.  \} 
89. 
90. \}

这里暂时只放了一个增加和查找的方法

3、前、中、后遍历

**\[java\]** [view plain][] [copy][view plain]

1.  **package** com.lin; 
2.  
3.  **import** java.util.Stack; 
4.  
5.  /\*\*
6.   \* 功能概要：
7.   \* 
8.   \* @author linbingwen
9.   \* @since 2015年8月29日 
10.  \*/
11. **public****class** TreeOrder \{ 
12. 
13. /\*\*
14.  \* 递归实现前序遍历
15.  \* @author linbingwen
16.  \* @since 2015年8月29日 
17.  \* @param treeNode
18.  \*/
19. **public****static****void** preOrderMethodOne(TreeNode treeNode) \{ 
20. **if** (**null** != treeNode) \{ 
21.  System.out.print(treeNode.data + " "); 
22. **if** (**null** != treeNode.left) \{ 
23.  preOrderMethodOne(treeNode.left); 
24.  \} 
25. **if** (**null** != treeNode.right) \{ 
26.  preOrderMethodOne(treeNode.right); 
27. 
28.  \} 
29.  \} 
30.  \} 
31. 
32. /\*\*
33.  \* 循环实现前序遍历
34.  \* @author linbingwen
35.  \* @since 2015年8月29日 
36.  \* @param treeNode
37.  \*/
38. **public****static****void** preOrderMethodTwo(TreeNode treeNode) \{ 
39. **if** (**null** != treeNode) \{ 
40.  Stack<TreeNode> stack = **new** Stack<TreeNode>(); 
41.  stack.push(treeNode); 
42. **while** (!stack.isEmpty()) \{ 
43.  TreeNode tempNode = stack.pop(); 
44.  System.out.print(tempNode.data + " "); 
45. // 右子节点不为null,先把右子节点放进去
46. **if** (**null** != tempNode.right) \{ 
47.  stack.push(tempNode.right); 
48.  \} 
49. // 放完右子节点放左子节点，下次先取
50. **if** (**null** != tempNode.left) \{ 
51.  stack.push(tempNode.left); 
52.  \} 
53.  \} 
54.  \} 
55.  \} 
56. 
57. /\*\*
58.  \* 递归实现中序遍历
59.  \* @author linbingwen
60.  \* @since 2015年8月29日 
61.  \* @param treeNode
62.  \*/
63. **public****static****void** medOrderMethodOne(TreeNode treeNode)\{ 
64. **if** (**null** != treeNode) \{ 
65. **if** (**null** != treeNode.left) \{ 
66.  medOrderMethodOne(treeNode.left); 
67.  \} 
68.  System.out.print(treeNode.data + " "); 
69. **if** (**null** != treeNode.right) \{ 
70.  medOrderMethodOne(treeNode.right); 
71.  \} 
72.  \} 
73. 
74.  \} 
75. 
76. /\*\*
77.  \* 循环实现中序遍历
78.  \* @author linbingwen
79.  \* @since 2015年8月29日 
80.  \* @param treeNode
81.  \*/
82. **public****static****void** medOrderMethodTwo(TreeNode treeNode)\{ 
83.  Stack<TreeNode> stack = **new** Stack<TreeNode>(); 
84.  TreeNode current = treeNode; 
85. **while** (current != **null** || !stack.isEmpty()) \{ 
86. **while**(current != **null**) \{ 
87.  stack.push(current); 
88.  current = current.left; 
89.  \} 
90. **if** (!stack.isEmpty()) \{ 
91.  current = stack.pop(); 
92.  System.out.print(current.data+" "); 
93.  current = current.right; 
94.  \} 
95.  \} 
96.  \} 
97. 
98. /\*\*
99.  \* 递归实现后序遍历
100.  \* @author linbingwen
101.  \* @since 2015年8月29日 
102.  \* @param treeNode
103.  \*/
104. **public****static****void** postOrderMethodOne(TreeNode treeNode)\{ 
105. **if** (**null** != treeNode) \{ 
106. **if** (**null** != treeNode.left) \{ 
107.  postOrderMethodOne(treeNode.left); 
108.  \} 
109. **if** (**null** != treeNode.right) \{ 
110.  postOrderMethodOne(treeNode.right); 
111.  \} 
112.  System.out.print(treeNode.data + " "); 
113.  \} 
114. 
115.  \} 
116. 
117. /\*\*
118.  \* 循环实现后序遍历
119.  \* @author linbingwen
120.  \* @since 2015年8月29日 
121.  \* @param treeNode
122.  \*/
123. **public****static****void** postOrderMethodTwo(TreeNode treeNode)\{ 
124. **if** (**null** != treeNode) \{ 
125.  Stack<TreeNode> stack = **new** Stack<TreeNode>(); 
126.  TreeNode current = treeNode; 
127.  TreeNode rightNode = **null**; 
128. **while**(current != **null** || !stack.isEmpty()) \{ 
129. **while**(current != **null**) \{ 
130.  stack.push(current); 
131.  current = current.left; 
132.  \} 
133.  current = stack.pop(); 
134. **while** (current != **null** && (current.right == **null** ||current.right == rightNode)) \{ 
135.  System.out.print(current.data + " "); 
136.  rightNode = current; 
137. **if** (stack.isEmpty())\{ 
138.  System.out.println(); 
139. **return**; 
140.  \} 
141.  current = stack.pop(); 
142.  \} 
143.  stack.push(current); 
144.  current = current.right; 
145.  \} 
146. 
147. 
148. 
149.  \} 
150.  \} 
151. 
152. \}

4、使用方法

**\[java\]** [view plain][] [copy][view plain]

1.  **package** com.lin; 
2.  
3.  /\*\*
4.   \* 功能概要：
5.   \* 
6.   \* @author linbingwen
7.   \* @since 2015年8月29日 
8.   \*/
9.  **public****class** SearchTreeTest \{ 
10. 
11. /\*\*
12.  \* @author linbingwen
13.  \* @since 2015年8月29日 
14.  \* @param args 
15.  \*/
16. **public****static****void** main(String\[\] args) \{ 
17.  SearchTree tree = **new** SearchTree(); 
18.  tree.addTreeNode(50); 
19.  tree.addTreeNode(80); 
20.  tree.addTreeNode(20); 
21.  tree.addTreeNode(60); 
22.  tree.addTreeNode(10); 
23.  tree.addTreeNode(30); 
24.  tree.addTreeNode(70); 
25.  tree.addTreeNode(90); 
26.  tree.addTreeNode(100); 
27.  tree.addTreeNode(40); 
28.  System.out.println("=============================="\+"采用递归的前序遍历开始"\+"=============================="); 
29.  TreeOrder.preOrderMethodOne(tree.root); 
30.  System.out.println(); 
31.  System.out.println("=============================="\+"采用循环的前序遍历开始"\+"=============================="); 
32.  TreeOrder.preOrderMethodTwo(tree.root); 
33.  System.out.println(); 
34.  System.out.println("=============================="\+"采用递归的后序遍历开始"\+"=============================="); 
35.  TreeOrder.postOrderMethodOne(tree.root); 
36.  System.out.println(); 
37.  System.out.println("=============================="\+"采用循环的后序遍历开始"\+"=============================="); 
38.  TreeOrder.postOrderMethodTwo(tree.root); 
39.  System.out.println(); 
40.  System.out.println("=============================="\+"采用递归的中序遍历开始"\+"=============================="); 
41.  TreeOrder.medOrderMethodOne(tree.root); 
42.  System.out.println(); 
43.  System.out.println("=============================="\+"采用循环的中序遍历开始"\+"=============================="); 
44.  TreeOrder.medOrderMethodTwo(tree.root); 
45. 
46.  \} 
47. 
48. \}

输出结果：

![20150829162559484][]

同样，进行查找过程如下：

**\[java\]** [view plain][] [copy][view plain]

1.  TreeNode node = tree.findTreeNode(100); 
2.  System.out.println(node);

![20150829164135636][]

结果是正确的

原文链接：[http://blog.csdn.net/evankaka/article/details/48088241][http_blog.csdn.net_evankaka_article_details_48088241]

[20150829161932865]: /images/20220611/80430f2095cc44b982e105f9cdd13ea7.png
[view plain]: http://blog.csdn.net/evankaka/article/details/48088241#
[20150829162559484]: /images/20220611/b210fd244b084740b0a0efc5e9ff08c0.png
[20150829164135636]: /images/20220611/825b2a1340444d2c9a8f0685248fc066.png
[http_blog.csdn.net_evankaka_article_details_48088241]: http://blog.csdn.net/evankaka/article/details/48088241