说明生活中遇到的二叉树，用java实现二叉树
2017-09-29 本文已影响0人
bug_华
这是组合设计模式。
我有很多个(假设10万个)数据要保存起来，以后还需要从保存的这些数据中检索是否存在某个数据，（我想说出二叉树的好处，该怎么说呢？那就是说别人的缺点），假如存在数组中，那么，碰巧要找的数字位于99999那个地方，那查找的速度将很慢，因为要从第1个依次往后取，取出来后进行比较。平衡二叉树（构建平衡二叉树需要先排序，我们这里就不作考虑了）可以很好地解决这个问题，但二叉树的遍历（前序，中序，后序）效率要比数组低很多
public class BinaryTree {
char data; //根节点
BinaryTree leftChild; //左孩子
BinaryTree rightChild; //右孩子
public BinaryTree() {
}
public void visit() {
System.out.println(this.data);
}
public BinaryTree(char data) {
this.data = data;
this.leftChild = null;
this.rightChild = null;
}
public BinaryTree getLeftChild() {
return leftChild;
}
public void setLeftChild(BinaryTree leftChild) {
this.leftChild = leftChild;
}
public BinaryTree getRightChild() {
return rightChild;
}
public void setRightChild(BinaryTree rightChild) {
this.rightChild = rightChild;
}
public char getData() {
return data;
}
public void setData(char data) {
this.data = data;
}
}
先序遍历思想：根左右。首先遍历根节点，然后遍历左子树和右子树。
public class VisitBinaryTree {
//先序遍历非递归算法
private void preOrder(BinaryTree root) {
if(root!=null) {
Stack<BinaryTree> stack = new Stack<BinaryTree>();
for (BinaryTree node = root; !stack.empty() || node != null;) {
//当遍历至节点位空的时候出栈
if(node == null) {
node = stack.pop();
}
node.visit();
//遍历右孩子存入栈内
if(node.getRightChild()!=null) {
stack.push(node.getRightChild());
}
//遍历左子树节点
node = node.getLeftChild();
}
}
}
//先序遍历递归算法
public void preOrderRecursion(BinaryTree root) {
if(root!=null) {
root.visit();
preOrderRecursion(root.getLeftChild());
preOrderRecursion(root.getRightChild());
}
}
}
测试代码：
public static void main(String args[]) {
BinaryTree node = new BinaryTree('A');
<span style="white-space:pre"> </span> BinaryTree root = node;
<span style="white-space:pre"> </span> BinaryTree nodeL1;
<span style="white-space:pre"> </span> BinaryTree nodeL;
<span style="white-space:pre"> </span> BinaryTree nodeR;
<span style="white-space:pre"> </span> node.setLeftChild(new BinaryTree('B'));
<span style="white-space:pre"> </span> node.setRightChild(new BinaryTree('C'));
<span style="white-space:pre"> </span> nodeL1 = node.getLeftChild();
<span style="white-space:pre"> </span> nodeL1.setLeftChild(new BinaryTree('D'));
<span style="white-space:pre"> </span> nodeL1.setRightChild(new BinaryTree('E'));
<span style="white-space:pre"> </span> nodeL = nodeL1.getLeftChild();
<span style="white-space:pre"> </span> nodeL.setLeftChild(new BinaryTree('F'));
<span style="white-space:pre"> </span> node = node.getRightChild();
<span style="white-space:pre"> </span> node.setLeftChild(new BinaryTree('G'));
<span style="white-space:pre"> </span> node.setRightChild(new BinaryTree('H'));
<span style="white-space:pre"> </span> nodeR = node.getLeftChild();
<span style="white-space:pre"> </span> nodeR.setLeftChild(new BinaryTree('I'));
<span style="white-space:pre"> </span> nodeR.setRightChild(new BinaryTree('J'));
<span style="white-space:pre"> </span> VisitBinaryTree vt= new VisitBinaryTree();
//先序遍历递归和非递归测试
vt.preOrder(root);
vt.preOrderRecursion(root);
}
中序遍历算法
public void inOrder(BinaryTree root) {
//中序遍历的非递归算法
if(root!=null) {
Stack<BinaryTree> stack = new Stack<BinaryTree>();
for (BinaryTree node = root; !stack.empty() || node != null; ) {
//寻找最左的左子树节点,并将遍历的左节点进栈
while(node!=null) {
stack.push(node);
node = node.getLeftChild();
}
if(!stack.empty()) {
node = stack.pop(); //出栈
node.visit(); //读取节点值
node = node.getRightChild();
}
}
}
}
//中序遍历的递归算法
public void inOrderRecursion (BinaryTree root) {
if(root!=null) {
inOrderRecursion(root.getLeftChild());
root.visit();
inOrderRecursion(root.getRightChild());
}
}
测试代码：
public static void main(String args[]) {
BinaryTree node = new BinaryTree('A');
BinaryTree root = node;
BinaryTree nodeL1;
BinaryTree nodeL;
BinaryTree nodeR;
node.setLeftChild(new BinaryTree('B'));
node.setRightChild(new BinaryTree('C'));
nodeL1 = node.getLeftChild();
nodeL1.setLeftChild(new BinaryTree('D'));
nodeL1.setRightChild(new BinaryTree('E'));
nodeL = nodeL1.getLeftChild();
nodeL.setLeftChild(new BinaryTree('F'));
node = node.getRightChild();
node.setLeftChild(new BinaryTree('G'));
node.setRightChild(new BinaryTree('H'));
nodeR = node.getLeftChild();
nodeR.setLeftChild(new BinaryTree('I'));
nodeR.setRightChild(new BinaryTree('J'));
VisitBinaryTree vt= new VisitBinaryTree();
//中序遍历递归和非递归测试
vt.inOrder(root);
vt.inOrderRecursion(root);
}
后序遍历：
//后序遍历非递归算法
private void postOrder(BinaryTree root) {
if(root!=null) {
Stack<BinaryTree> stack = new Stack<BinaryTree>();
for (BinaryTree node = root; !stack.empty() || node != null;) {
while(root!=null) {
stack.push(root);
root = root.getLeftChild();
}
while(!stack.empty() && root == stack.peek().getRightChild()) {
root = stack.pop();
root.visit();
}
if (stack.empty()) {
return;
} else {
root = stack.peek().getRightChild();
}
}
}
}
//后序遍历递归算法
private void postOrderRecursion(BinaryTree root) {
if(root!=null) {
postOrderRecursion(root.getLeftChild());
postOrderRecursion(root.getRightChild());
root.visit();
}
}
测试代码
public static void main(String args[]) {
BinaryTree node = new BinaryTree('A');
BinaryTree root = node;
BinaryTree nodeL1;
BinaryTree nodeL;
BinaryTree nodeR;
node.setLeftChild(new BinaryTree('B'));
node.setRightChild(new BinaryTree('C'));
nodeL1 = node.getLeftChild();
nodeL1.setLeftChild(new BinaryTree('D'));
nodeL1.setRightChild(new BinaryTree('E'));
nodeL = nodeL1.getLeftChild();
nodeL.setLeftChild(new BinaryTree('F'));
node = node.getRightChild();
node.setLeftChild(new BinaryTree('G'));
node.setRightChild(new BinaryTree('H'));
nodeR = node.getLeftChild();
nodeR.setLeftChild(new BinaryTree('I'));
nodeR.setRightChild(new BinaryTree('J'));
VisitBinaryTree vt= new VisitBinaryTree();
//后序遍历递归和非递归测试
vt.postOrder(root);
vt.postOrderRecursion(root);
}
