Ruby/Java - 两种语言的二叉排序树的实现和遍历

2016-12-03 14:06:48来源:网络收集作者:Alex人点击

Ruby
class BinaryTree
include Enumerabledef initialize
@root=TreeNode.new
@array=[]
end
def << (data)
@root.push(data)
end
def empty?
if @root.content
return false
else
return true
end
end
class TreeNode
attr_accessor :content
attr_accessor :right
attr_accessor :left
def push(value)
if self.content==nil
self.left =TreeNode.new
self.right =TreeNode.new
self.content =value
print "#{value} is set /n"
else
if self.content>=value
puts "#{value} is compared with #{self.content} /n"
self.left.push(value) else
puts "#{value} is compared with #{self.content} /n"
self.left.push(value)
end
end
end
enddef tranversal(node)
if node.content==nil
return
else
@array<< node.content
tranversal(node.left)
tranversal(node.right)
end
end
def each
tranversal(@root)
@array.each do |value|
yield value
end
end
end
Tree=BinaryTree.new
Tree<<(5)
Tree<<(4)
Tree<<(9)
Tree<<(8)
Tree<<(1)
Tree<<(2)
puts Tree.empty?
Tree.each do |value|
print "#{value},"
end

#=> 4 is compared with 5
#=> 4 is set
#=> 9 is compared with 5
#=> 9 is compared with 4
#=> 9 is set
#=> 8 is compared with 5
#=> 8 is compared with 4
#=> 8 is compared with 9
#=> 8 is set
#=> 1 is compared with 5
#=> 1 is compared with 4
#=> 1 is compared with 9
#=> 1 is compared with 8
#=> 1 is set
#=> 2 is compared with 5
#=> 2 is compared with 4
#=> 2 is compared with 9
#=> 2 is compared with 8
#=> 2 is compared with 1
#=> 2 is set
#=> false
#=> 5,4,9,8,1,2,

BinaryTree中还定义了其他实例方法：<<：添加新节点empty?：判断树是否为空tranversal: 对树进行前序遍历each：为了继承Enumerable模块而覆写的方法，用来返回遍历的结果
Java
package SortBinaryTree;
import java.util.ArrayList;
class BinaryTree {
private TreeNode root;
private ArrayList element;
public BinaryTree() {
root = new TreeNode();
element = new ArrayList();
}
public void add(int i) {
root.push(i);
}
public boolean empty() {
if (root == null) {
return true;
} else {
return false;
}
}
public void tranversal(TreeNode node) {
if (node.getKey() == 0) {
return;
} else {
tranversal(node.getLeft());
tranversal(node.getRight());
}
}
public ArrayList getElement() {
tranversal(root);
return element;
}
class TreeNode {
private int key;
private TreeNode left;
private TreeNode right;
public int getKey() {
return key;
}
public void setKey(int key) {
this.key = key;
}
public TreeNode getLeft() {
return left;
}
public void setLeft(TreeNode left) {
this.left = left;
}
public TreeNode getRight() {
return right;
}
public void setRight(TreeNode right) {
this.right = right;
}
public void push(int k) {
if (this.key == 0) {
setRight(new TreeNode());
setLeft(new TreeNode());
setKey(k);
System.out.println(k + " is set");
} else {
if (k >= this.key) {
System.out.println(k + " is compared with " + this.key);
this.right.push(k);
} else {
System.out.println(k + " is compared with " + this.key);
this.left.push(k);
}
}
}
}
}
public class Test {
public static void main(String args[]) {
BinaryTree tree = new BinaryTree();
System.out.println(tree.empty());
ArrayList list = tree.getElement();
for (int i = 0; i < list.size(); i++) {
System.out.print(list.get(i) + ",");
}
}
}输出结果：5 is set
4 is compared with 5
4 is set
9 is compared with 5
9 is set
8 is compared with 5
8 is compared with 9
8 is set
1 is compared with 5
1 is compared with 4
1 is set
2 is compared with 5
2 is compared with 4
2 is compared with 1
2 is set
false
5,4,1,2,9,8,