package com.hisen.interview.tiger20171110.btree;

/**
 * @author : yhx
 * @date : 2017/11/10 18:42
 * @descriptor : 二叉树的 - 二叉链表实现
 */
public class LinkBTree implements BTree {

  private Object data;
  private BTree lChild;
  private BTree rChild;

  public LinkBTree() {
    this.clearTree();
  }

  public LinkBTree(Object data) {
    this.data = data;
    this.rChild = null;
    this.lChild = null;
  }

  @Override
  public void addLfetTree(BTree lChild) {
    this.lChild = lChild;
  }

  @Override
  public BTree getLfetTree() {
    return lChild;
  }

  @Override
  public void addRightTree(BTree rChild) {
    this.rChild = rChild;
  }

  @Override
  public BTree getRightTree() {
    return rChild;
  }

  @Override
  public void clearTree() {
    this.data = null;
    this.rChild = null;
    this.lChild = null;
  }

  @Override
  public int getDeep() {
    return deep(this);
  }


  @Override
  public Object getRootData() {
    return data;
  }

  @Override
  public boolean hasLeftTree() {
    if (lChild != null) {
      return true;
    }
    return false;
  }

  @Override
  public boolean hasRightTree() {
    if (rChild != null) {
      return true;
    }
    return false;
  }

  @Override
  public boolean isEmptyTree() {
    if ((lChild == null && rChild == null && data == null) || this == null) {
      return true;
    }
    return false;
  }

  @Override
  public boolean isLeaf() {
    if (lChild == null && rChild == null) {
      return true;
    }
    return false;
  }

  @Override
  public void removeLeftTree() {
    lChild = null;
  }

  @Override
  public void removeRightTree() {
    rChild = null;
  }

  @Override
  public BTree getRoot() {
    return this;
  }

  @Override
  public void setRootData() {
    this.data = data;
  }

  @Override
  public int size() {
    return size(this);
  }

  private int size(BTree bTree) {
    if (bTree == null) {
      return 0;
    } else if (bTree.isLeaf()) {
      return 1;
    } else {
      if (bTree.getLfetTree() == null) {
        return size(bTree.getRightTree()) + 1;
      } else if (bTree.getRightTree() == null) {
        return size(bTree.getLfetTree()) + 1;
      } else {
        return size(bTree.getLfetTree()) + size(bTree.getRightTree()) + 1;
      }
    }
  }

  /**
   * 计算二叉树的高度
   */
  private int deep(BTree bTree) {
    if (bTree.isEmptyTree()) {
      return 0;
    } else if (bTree.isLeaf()) {
      return 1;
    } else {
      if (bTree.getLfetTree() == null) {
        return deep(bTree.getRightTree()) + 1;
      } else if (bTree.getRightTree() == null) {
        return deep(bTree.getLfetTree()) + 1;
      } else {
        return Math.max(deep(bTree.getLfetTree()), deep(bTree.getRightTree())) + 1;
      }
    }
  }
}

/**
 * 最大公约数
 */
public int getGCD(int m, int n) {
  if (n == 0) {
    return m;
  }
  return getGCD(n, m % n);
}

/**
 * 最小公倍数
 * @param m
 * @param n
 * @return
 */
public int getLCM(int m, int n) {
  int mn = m * n;
  return mn / getGCD(m, n);
}

/**
   * 辗转相除求最大公约数
   * 有两整数a和b：
   * ① a%b得余数c
   * ② 若c=0，则b即为两数的最大公约数
   * ③ 若c≠0，则a=b，b=c，再回去执行①
   */
  public int divisionGCD(int m, int n) {
    int a;
    while (n != 0) {
      a = m % n;
      m = n;
      n = a;
    }
    return m;
  }
  /**
   * 相减法求最大公约数
   * 有两整数a和b：
   * ① 若a>b，则a=a-b
   * ② 若a<b，则b=b-a
   * ③ 若a=b，则a（或b）即为两数的最大公约数
   * ④ 若a≠b，则再回去执行①
   */
  public int subtractionGCD(int m,int n){
    while(m != n){
      if (m>n){
        m = m-n;
      }else {
        n = n - m;
      }
    }
    return m;
  }