package cn.csu.trees;
public class BinaryTreeNode {
/*
* 一个二叉树包括 数据、左右孩子 三部分
*/
private int data;
private BinaryTreeNode leftChild;
private BinaryTreeNode rightChild;
public BinaryTreeNode(int data, BinaryTreeNode leftChild,
BinaryTreeNode rightChild) {
super();
this.data = data;
this.leftChild = leftChild;
this.rightChild = rightChild;
}
public int getData() {
return data;
}
public void setData(int data) {
this.data = data;
}
public BinaryTreeNode getLeftChild() {
return leftChild;
}
public void setLeftChild(BinaryTreeNode leftChild) {
this.leftChild = leftChild;
}
public BinaryTreeNode getRightChild() {
return rightChild;
}
public void setRightChild(BinaryTreeNode rightChild) {
this.rightChild = rightChild;
}
}
package cn.csu.trees;
public class BinaryTree {
/*
* 创建一个二叉树很简单，只要有一个二叉根节点，然后提供设置根节点的方法即可
*/
private BinaryTreeNode root;//根节点
public BinaryTree(){
}
public BinaryTree(BinaryTreeNode root) {
super();
this.root = root;
}
public BinaryTreeNode getRoot() {
return root;
}
public void setRoot(BinaryTreeNode root) {
this.root = root;
}
/**
* 添加左子树
* @param child
*/
public void insertAsLeftChild(BinaryTreeNode child){
checkTreeEmpty();
root.setLeftChild(child);
}
/**
* 添加右子树
* @param child
*/
public void insertAsRightChild(BinaryTreeNode child){
checkTreeEmpty();
root.setRightChild(child);
}
/**
* 检查二叉树是否已经创建
* 在每次插入节点前都会检查二叉树是否为空，如果为空就抛出异常
*/
private void checkTreeEmpty() {
if(root == null){
throw new IllegalStateException("Can't insert to a null tree! Did you forget set value fot root?");
}
}
/**
* 删除节点元素，只要把对应的节点设置为空（null）即可
* 但是为了避免浪费不必要的内存，方便GC及时回收，我们还需要删除该节点对应的左右子树
* @param node
*/
public void deleteNode(BinaryTreeNode node){
checkTreeEmpty();
if(node == null){//递归出口
return;
}
deleteNode(node.getLeftChild());
deleteNode(node.getRightChild());
node = null;
}
/**
* 清空二叉树
* 二叉树的清空其实就是删除节点元素的一种特殊情况，即删除根节点元素
*/
public void clearTree(){
if(root!=null){
deleteNode(root);
}
}
/**
* 获得指定节点的高度
* @param node
* @return
*/
public int getHight(BinaryTreeNode node){
if(node == null){//递归出口
return 0;
}
int leftChildHight = getHight(node.getLeftChild());//当前节点的左子树高度
int rightChildHight = getHight(node.getRightChild());//当前节点的右子树高度
int max = (leftChildHight>rightChildHight)?leftChildHight:rightChildHight;
return max + 1;//加上自己本身
}
/**
* 获取树的高度
* 可以看成获取指定节点高度的特殊情况 根节点
* @return
*/
public int getTreeHight(){
return getHight(root);
}
/**
* 获取指定节点对应子树的节点数
* @param node
* @return
*/
public int getSize(BinaryTreeNode node){
if(node == null){
return 0;
}
int leftSize = getSize(node.getLeftChild());//获取左子树节点数
int rightSize = getSize(node.getRightChild());//获取右子树节点数
return leftSize + rightSize + 1;//返回当前节点对应子树节点总数
}
/**
* 获取二叉树的节点数
* 可以看成获取指定节点对应子树的节点数特殊情况 根节点
* @return
*/
public int getTreeSize(){
return getSize(root);
}
/**
* 返回指定节点的直接父节点
* @param node
* @return
*/
public BinaryTreeNode getParent(BinaryTreeNode node){
if(node == root || root == null){//如果这个节点就是根节点或者这棵树为空树返回null
return null;
}
return getParent(root,node);//如果不是根节点并且不为空树，这时就要从根节点开始递归查找父节点
}
/**
* 递归对比节点的孩子节点与指定节点是否一致
* @param subTreeNode 子二叉树根节点
* @param node 指定节点
* @return
*/
private BinaryTreeNode getParent(BinaryTreeNode subTreeNode, BinaryTreeNode node) {
if(subTreeNode == null){//如果子树为空，则没有父节点 递归出口 1
return null;
}
if(subTreeNode.getLeftChild() == node || subTreeNode.getRightChild() == node){
return subTreeNode;//如果左孩子或者右孩子为指定节点则当前判断节点即为父节点 递归出口 2
}
//否则遍历左右子树
BinaryTreeNode parent = getParent(subTreeNode.getLeftChild(), node);//查找左子树
if(parent != null){
return parent;
}
return getParent(subTreeNode.getRightChild(), node);//查找右子树
}
/**
* 二叉树先序遍历
* 根 左 右
* @param node
*/
public void iteratorFirstOrder(BinaryTreeNode node){
if(node == null){
return;
}
operate(node);//操作节点
iteratorFirstOrder(node.getLeftChild());
iteratorFirstOrder(node.getRightChild());
}
public void iteratorFirstOrder(){
this.iteratorFirstOrder(this.root);
}
/**
* 模拟节点操作
* @param node
*/
private void operate(BinaryTreeNode node) {
if(node == null){
return;
}
System.out.println(node.getData());
}
/**
* 二叉树中序遍历
* 左 根 右
* @param node
*/
public void iteratorMediumOrder(BinaryTreeNode node){
if(node == null){
return;
}
iteratorMediumOrder(node.getLeftChild());
operate(node);
iteratorMediumOrder(node.getRightChild());
}
public void iteratorMediumOrder(){
this.iteratorMediumOrder(this.root);
}
/**
* 二叉树后序遍历
* 左 右 根
* @param node
*/
public void iteratorLastOrder(BinaryTreeNode node){
if(node == null){
return;
}
iteratorLastOrder(node.getLeftChild());
iteratorLastOrder(node.getRightChild());
operate(node);
}
public void iteratorLastOrder(){
this.iteratorLastOrder(this.root);
}
/**
* 建立二叉排序树
* @param data
*/
public void insert(int data){
BinaryTreeNode node = new BinaryTreeNode(data, null, null);//待插入排序树的节点
if(root == null){
root = node;
}else{
BinaryTreeNode track = root;//跟踪插入位置
BinaryTreeNode trackParent;
while(true){
trackParent = track;
if(track.getData() > data){//左查找并插入
track = track.getLeftChild();
if(track == null){
trackParent.setLeftChild(node);
return;
}
}else if(track.getData() < data){//右查找并插入
track = track.getRightChild();
if(track == null){
trackParent.setRightChild(node);
return;
}
}
}
}
}
}
package cn.csu.trees;
public class BinaryTreeUtils {
public static void main(String[] args) {
int[] firstOrder = new int[]{1,2,4,7,3,5,8,9,6};//1 2 4 7 3 5 8 9 6
int[] mediumOrder = new int[]{4,7,2,1,8,5,9,3,6};//4 7 2 1 8 5 9 3 6
BinaryTree binaryTree = new BinaryTree();
// binaryTree.iteratorLastOrder(crateBinaryTree(firstOrder,mediumOrder,firstOrder.length));
for (int i = 0; i < mediumOrder.length; i++) {
binaryTree.insert(mediumOrder[i]);
}
binaryTree.iteratorMediumOrder();
}
/**
*
* @param firstOrder 前序遍历数组
* @param mediumOrder 中序遍历数组
* @param length 数组长度
* @return 根节点
*/
private static BinaryTreeNode crateBinaryTree(int[] firstOrder,
int[] mediumOrder, int length) {
if(firstOrder == null || mediumOrder == null || firstOrder.length <= 0){
return null;
}
return createCore(firstOrder,0,firstOrder.length-1,mediumOrder,0,mediumOrder.length-1);
}
private static BinaryTreeNode createCore(int[] firstOrder, int firstStart, int firstEnd,
int[] mediumOrder, int mediumSrart,int mediumEnd) {
int rootValue = firstOrder[firstStart];
BinaryTreeNode root = new BinaryTreeNode(rootValue, null, null);
if(firstStart == firstEnd){//递归出口
if(mediumSrart == mediumEnd && firstOrder[firstStart] == mediumOrder[mediumSrart]){
return root;
}else{
throw new RuntimeException("Order Error!Can't crare Tree on your data!");
}
}
int rootIndex = mediumSrart;
while(rootIndex <= mediumEnd && mediumOrder[rootIndex] != rootValue){
++rootIndex;//在中序遍历中找到根节点的索引
}
if(rootIndex == mediumEnd && mediumOrder[rootIndex] != rootValue){//异常处理
throw new RuntimeException("Can't find rootTndex!");
}
int leftLength = rootIndex - mediumSrart;//左子树数组长度
int leftFirstOrderEndIndex = firstStart + leftLength;//左子树前序遍历下边界
if(leftLength > 0){
//构建左子树
root.setLeftChild(createCore(firstOrder, firstStart+1, leftFirstOrderEndIndex,
mediumOrder, mediumSrart, rootIndex-1));
}
if(leftLength < firstEnd-firstStart){
//右子树有元素，构建右子树
root.setRightChild(createCore(firstOrder, leftFirstOrderEndIndex+1, firstEnd, mediumOrder, rootIndex+1, mediumEnd));
}
return root;
}
}
转载请注明原文地址: https://ju.6miu.com/read-14973.html
