求二叉树的深度，前序遍历，中序遍历，后序遍历，节点个数，是否为空，查找某一个节点，测试方式
package com.bjsxt.tree;
import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.Queue;
/**
*
* @author Administrator
*
*/
public class BinaryTree implements BinaryInterface{
Node root;
public Node getRoot() {
return root;
}
public void setRoot(Node root) {
this.root = root;
}
public BinaryTree(Node root) {
super();
this.root = root;
}
public BinaryTree() {
super();
// TODO Auto-generated constructor stub
}
@Override
public boolean isEmpty() {
return root==null;
}
@Override
public int size() {
if(root==null) {
return 0;
}else if(root.leftChild==null&&root.rightChild==null) {
return 1;
}else {
BinaryTree lefttree=new BinaryTree(root.leftChild);
BinaryTree righttree=new BinaryTree(root.rightChild);
int i=lefttree.size();
int j=righttree.size();
return i+j+1;
}
}
@Override
public int getheight() {
return this.getHeight(root);
}
private int getHeight(Node root) {
if(root==null) {
return 0;
}else if(root.leftChild==null&&root.rightChild==null) {
return 1;
}
else {
int i=this.getHeight(root.leftChild);
int j=this.getHeight(root.rightChild);
return (i<j)?(i+1):(j+1);
}
}
@Override
public Node findKey(int value) {
return findKey(value,root);
}
private Node findKey(int value, Node root2) {
if(root==null) {
return null;
}else if(root!=null&&root.value==value) {
return root;
}else {
Node node1=this.findKey(value, root2.leftChild);
Node node2=this.findKey(value, root2.rightChild);
if(node1!=null&&node1.value==value) {
return node1;
}else if(node2!=null&&node2.value==value) {
return node2;
}else {
return null;
}
}
}
@Override
public void preOrderTraverse() {
// System.out.println("前序遍历");
if(root!=null) {
System.out.println(root.value+"");
if(root.leftChild!=null) {
BinaryTree lefttree=new BinaryTree(root.leftChild);
lefttree.preOrderTraverse();
}
if(root.rightChild!=null) {
BinaryTree righttree=new BinaryTree(root.rightChild);
righttree.preOrderTraverse();
}
}
}
@Override
public void midOrderTraverse() {
System.out.println("中序递归遍历二叉树");
this.MidOrderTraverse(root);
}
private void MidOrderTraverse(Node root2) {
this.MidOrderTraverse(root.leftChild);
System.out.println(root.value);
this.MidOrderTraverse(root2.rightChild);
}
@Override
public void postOrderTraverse() {
System.out.println("后序递归遍历二叉树");
this.postOrderTraverse(root);
System.out.println();
}
private void postOrderTraverse(Node node) {
if(root!=null) {
this.postOrderTraverse(node.leftChild);
this.postOrderTraverse(node.rightChild);
System.out.println(node.value+" ");
}else {
System.out.println("zhiweikong");
}
}
//中序遍历非递归
@Override
public void inOrderByStack() {
System.out.println("中序遍历非递归操作");
//创建栈
Deque<Node> stack=new LinkedList<Node>();
Node current=root;
while(current!=null||!stack.isEmpty()) {
while(current!=null) {
stack.push(current);
current=current.leftChild;
}
if(!stack.isEmpty()) {
current=stack.pop();
System.out.println(current.value+"");
current=current.rightChild;
}
}
System.out.println();
}
//中序遍历二叉树
@Override
public void preOrderByStack() {
System.out.println("中序遍历二叉树非递归操作");
//创建栈
Deque<Node> stack=new LinkedList<Node>();
Node current=root;
while(current!=null||!stack.isEmpty()) {
while(current!=null) {
stack.push(current);
current=current.leftChild;
}
if(!stack.isEmpty()) {
current=stack.pop();
System.out.println(current.value+"");
current=current.rightChild;
}
}
}
@Override
public void levelOrderByStack() {
if(root==null) {
return;
}
//创建队列
Queue<Node> queue=new LinkedList<Node>();
queue.add(root);
while(queue.size()!=0) {
int len=queue.size();
for(int i=0;i<len;i++) {
Node tmp=queue.poll();
System.out.println(tmp.value);
if(tmp.leftChild!=null) {
queue.add(tmp.leftChild);
}
if(tmp.rightChild!=null) {
queue.add(tmp.rightChild);
}
}
}
}
@Override
public void postOrderByStack() {
}
public int getwidth(Node root) {
if(root==null) {
return 0;
}
Queue<Node> queue=new LinkedList<Node>();
int maxWidth=1;
queue.add(root);
while(true) {
int len=queue.size();
if(len==0)
break;
while(len>0) {
Node node=queue.poll();
len--;
if(node.leftChild!=null)
queue.add(node.leftChild);
if(node.rightChild!=null)
queue.add(node.rightChild);
}
maxWidth=Math.max(maxWidth, queue.size());
}
return maxWidth;
}
//获取二叉树中叶子结点的个数：
public int getLeave(Node root) {
int count=0;
if(root==null)
return 0;
if(root.leftChild!=null)
getLeave(root.leftChild);
if(root.rightChild!=null)
getLeave(root.rightChild);
if(root.leftChild==null&&root.rightChild==null)
count++;
return count;
}
//获取二叉树的最大宽度
public int getWidth(Node root) {
int maxWith=1;
if(root==null) {
return 0;
}else if(root.leftChild==null&&root.rightChild==null) {
return 1;
}else {
Queue<Node> queue=new LinkedList<Node>();
maxWith=1;
queue.add(root);
while(true) {
int len=queue.size();
if(len==0) {
break;
}else {
while(len>0) {
Node node=queue.poll();
len--;
if(node.leftChild!=null) {
queue.add(node.leftChild);
}else if(node.rightChild!=null) {
queue.add(node.rightChild);
}
}
}
}
maxWith=Math.max(maxWith, queue.size());
}
return maxWith;
}
}
测试方式：
package com.bjsxt.tree;
public class Test {
public static void main(String[] args) {
Node node5=new Node(5,null,null);
Node node4=new Node(4,null,node5);
Node node7=new Node(7,null,null);
Node node3=new Node(3,null,null);
Node node6=new Node(6,null,node7);
Node node2=new Node(2,node3,node6);
Node node1=new Node(1,node4,node2);
BinaryTree btree=new BinaryTree(node1);
// System.out.println(btree.size());
// System.out.println(btree.isEmpty());
// System.out.println(btree.getheight());
// btree.preOrderTraverse();
// btree.midOrderTraverse();
// btree.postOrderTraverse();
// btree.preOrderByStack();
//// btree.findKey(4);
// btree.inOrderByStack();
// System.out.println(btree.getwidth(node1));
System.out.println(btree.getLeave(node1));
}
}
原图在这里~