个人中心
文章发布
退出
作者热门文章
- ubuntu12.04环境下使用kvm ioctl接口实现最简单的虚拟机
- Ubuntu 通过无线网络安装Ubuntu Server启动系统后连接无线网络的方法
- 在Ubuntu上搭建网桥的方法
- ubuntu 虚拟机上网方式及相关配置详解
24
4
CFSDN坚持开源创造价值，我们致力于搭建一个资源共享平台，让每一个IT人在这里找到属于你的精彩世界.
这篇CFSDN的博客文章二叉排序树的实现与基本操作由作者收集整理，如果你对这篇文章有兴趣，记得点赞哟.
二叉排序树又称二叉查找树。它或者是一颗空树，或者是具有以下性质的二叉树:
①如果左子树不空，那么左子树上所有结点的值均小于它的根结点的值； 。
②如果右子树不空，那么右子树上所有结点的值均大于它的根结点的值； 。
③左右子树也分别为二叉排序树.
以下代码实现了:
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
|
import
java.util.LinkedList;
import
java.util.Queue;
class
Node{
public
int
data;
public
Node left;
public
Node right;
public
int
leftMaxDistance;
public
int
rightMaxDistance;
public
Node(
int
data){
this
.data=data;
this
.left=
null
;
this
.right=
null
;
}
}
/**
* @author TY
* 实现二叉排序树，包括插入、中序遍历、先序遍历、后序遍历、计算所有节点的最大距离的功能
*/
public
class
BinaryTree {
private
Node root;
public
BinaryTree(){
root=
null
;
}
public
void
insert(
int
data){
Node newNode=
new
Node(data);
if
(root==
null
)
root=newNode;
else
{
Node current=root;
Node parent;
while
(
true
) {
//寻找插入位置
parent=current;
if
(data<current.data){
current=current.left;
if
(current==
null
){
parent.left=newNode;
return
;
}
}
else
{
current=current.right;
if
(current==
null
) {
parent.right=newNode;
return
;
}
}
}
}
}
//将数值输入构建二叉树
public
void
buildTree(
int
[] data){
for
(
int
i =
0
; i < data.length; i++) {
insert(data[i]);
}
}
//中序遍历方法递归实现
public
void
inOrder(Node localRoot){
if
(localRoot!=
null
){
inOrder(localRoot.left);
System.out.print(localRoot.data+
" "
);
inOrder(localRoot.right);
}
}
public
void
inOrder(){
this
.inOrder(
this
.root);
}
//先序遍历方法递归实现
public
void
preOrder(Node localRoot){
if
(localRoot!=
null
){
System.out.print(localRoot.data+
" "
);
preOrder(localRoot.left);
preOrder(localRoot.right);
}
}
public
void
preOrder(){
this
.preOrder(
this
.root);
}
//后序遍历方法递归实现
public
void
postOrder(Node localRoot){
if
(localRoot!=
null
){
postOrder(localRoot.left);
postOrder(localRoot.right);
System.out.print(localRoot.data+
" "
);
}
}
public
void
postOrder(){
this
.postOrder(
this
.root);
}
/**
* 层序遍历二叉树：现将根结点放入队列中，然后每次都从队列中取一个结点打印该结点的值，
* 若这个结点有子结点，则将它的子结点放入队列尾，直到队列为空
*/
public
void
layerTranverse(){
if
(
this
.root==
null
)
return
;
Queue<Node> q=
new
LinkedList<Node>();
q.add(
this
.root);
while
(!q.isEmpty()){
Node n=q.poll();
System.out.print(n.data+
" "
);
if
(n.left!=
null
)
q.add(n.left);
if
(n.right!=
null
)
q.add(n.right);
}
}
private
int
maxLen=
0
;
private
int
max(
int
a,
int
b){
return
a>b?a:b;
}
public
void
findMaxDistance(Node root){
if
(root==
null
)
return
;
if
(root.left==
null
)
root.leftMaxDistance=
0
;
if
(root.right==
null
)
root.rightMaxDistance=
0
;
if
(root.left!=
null
)
findMaxDistance(root.left);
if
(root.right!=
null
)
findMaxDistance(root.right);
//计算左字树中距离根结点的最大距离
if
(root.left!=
null
)
root.leftMaxDistance=max(root.left.leftMaxDistance, root.left.rightMaxDistance)+
1
;
//计算右字树中距离根结点的最大距离
if
(root.right!=
null
)
root.rightMaxDistance=max(root.right.leftMaxDistance, root.right.rightMaxDistance)+
1
;
//获取二叉树所有结点的最大距离
if
(root.leftMaxDistance+root.rightMaxDistance>maxLen){
maxLen=root.leftMaxDistance+root.rightMaxDistance;
}
}
public
static
void
main(String[] args) {
BinaryTree biTree=
new
BinaryTree();
int
[] data={
2
,
8
,
7
,
4
,
9
,
3
,
1
,
6
,
7
,
5
};
biTree.buildTree(data);
System.out.print(
"二叉树的中序遍历："
);
biTree.inOrder();
System.out.println();
System.out.print(
"二叉树的先序遍历："
);
biTree.preOrder();
System.out.println();
System.out.print(
"二叉树的后序遍历："
);
biTree.postOrder();
System.out.println();
System.out.print(
"二叉树的层序遍历："
);
biTree.layerTranverse();
System.out.println();
biTree.findMaxDistance(biTree.root);
System.out.println(
"二叉树中结点的最大距离："
+biTree.maxLen);
}
}
|
以上就是本文的全部内容，希望本文的内容对大家的学习或者工作能带来一定的帮助，同时也希望多多支持我！ 。
原文链接：http://www.cnblogs.com/winorgohome/p/6044627.html 。
最后此篇关于二叉排序树的实现与基本操作的文章就讲到这里了,如果你想了解更多关于二叉排序树的实现与基本操作的内容请搜索CFSDN的文章或继续浏览相关文章，希望大家以后支持我的博客！ 。
24
4
0
关闭。此题需要details or clarity 。目前不接受答案。 想要改进这个问题吗？通过 editing this post 添加详细信息并澄清问题. 已关闭 7 年前。 Improve th
我在使用 fork 和 pipes 制作一个用于学习目的的简单程序时遇到了问题。我想要一个 child 向 parent 发送一些数据，然后这个( parent )再次将它发送给 child 。 结果
我正在制作一个需要同时做 3 件事的 python 脚本。什么是实现此目的的好方法，就像我听说的关于 GIL 的方法一样，我不再那么倾向于使用线程了。 脚本需要做的两件事将非常活跃，他们将有很多工作要
有没有办法运行sshd以便它可以(至少对于有限数量的登录)成功返回提示(可能是 busybox)，即使 fork 不可用(例如，PID 不足)？ 在我看来，这应该是可能的，例如，sshd 预 fork
我意识到 Bootstrap 将使用 v4 切换到 rem。但是，我使用的是当前版本 (v3)，我想使用 rem。 原因？我希望网站上有可以为最终用户缩放字体大小的按钮。我相信最好的实现方式是使用 r
我试图在这个程序中将信息从子进程传递到父进程。这是到目前为止的代码，仍在清理它: #include #include #include #include main() { char *
我试图理解 fork 在 C 中是如何工作的，但我在某个地方误解了一些东西。 我去年遇到了一位教授给我的测试，但我无法回复它:我们有 3 个任务(进程或线程)，伪代码如下: Th1 { display
我在使用 fork() 之类的东西时遇到了一些麻烦。 我正在开发一个 shell，用户可以在其中编写将像在普通普通 shell 中一样执行的命令。 我有一个像这样的主要功能: void Shell::
我有一个 Python 主进程，以及由主进程使用 os.fork() 创建的一组或多个 worker . 我需要将大型且相当复杂的数据结构从工作程序传递回主进程。您会为此推荐哪些现有库？ 数据结构是列
我对这个 fork 语句很陌生，我不知道 C 程序上的 fork 方法。你能告诉我这段代码的三个可能的输出是什么吗？ #include #include int main(void) {
for(i=0;i #include int main() { for(int i=0;i<2;i++) { if(fork()==0) { printf("Hi %d %d
背景 我正在用 C 语言编写一个共享库，与 LD_PRELOAD 动态链接，这意味着拦截和覆盖预加载它的应用程序的网络调用，例如 socket()、connect()、recv()、send()等 在
我是一名优秀的程序员,十分优秀！