Java实现二叉树的相关操作

// 求二叉树的深度
public static int BiTreeDepth(BitNode T) {
int depthval, depthLeft, depthRight;
if (T == null)
            depthval = 0;
else if (T.lchild == null && T.rchild == null)
            depthval = 1;
else {
            depthLeft = BiTreeDepth(T.lchild);
            depthRight = BiTreeDepth(T.rchild);
            depthval = 1 + (depthLeft > depthRight ? depthLeft : depthRight);
        }
return depthval;
    }


// 求data所对应结点的层数，如果对象不在树中,结果返回-1;否则结果返回该对象在树中所处的层次,规定根节点为第一层
public static int level(BitNode bitNode, int data) {
int leftLevel, rightLevel;
if (bitNode == null)
return -1;
if (data == bitNode.data)
return 1;
        leftLevel = bitNode.lchild == null ? -1 : level(bitNode.lchild, data);
        rightLevel = bitNode.rchild == null ? -1 : level(bitNode.rchild, data);
if (leftLevel < 0 && rightLevel < 0)
return -1;
return leftLevel > rightLevel ? leftLevel + 1 : rightLevel + 1;
    }

// 求二叉树叶子节点的总数
public static int leafNum(BitNode tree) {
if (tree == null)
return 0;
else {
int left = leafNum(tree.lchild);
int right = leafNum(tree.rchild);
if (tree.lchild == null && tree.rchild == null)
return left + right + 1;
else
return left + right;
        }
    }

// 求二叉树父节点个数
public static int fatherNodes(BitNode tree) {
if (tree == null || (tree.lchild == null && tree.rchild == null))
return 0;
else {
int left = fatherNodes(tree.lchild);
int right = fatherNodes(tree.rchild);
return left + right + 1;
        }
    }

// 求只有一个孩子结点的父节点个数
public static int oneChildFather(BitNode tree) {
int left, right;
if (tree == null || (tree.rchild == null && tree.lchild == null))
return 0;
else {
            left = oneChildFather(tree.lchild);
            right = oneChildFather(tree.rchild);
if ((tree.lchild != null && tree.rchild == null)
                    || (tree.lchild == null && tree.rchild != null))
return left + right + 1;
else
return left + right;/* 加1是因为要算上根节点 */
        }
    }

// 求二叉树只拥有左孩子的父节点总数
public static int leftChildFather(BitNode tree) {
if (tree == null)
return 0;
else {
int left = leftChildFather(tree.lchild);
int right = leftChildFather(tree.rchild);
if ((tree.lchild != null && tree.rchild == null))
return left + right + 1;
else
return left + right;
        }
    }

// 求二叉树只拥有左孩子的父节点总数
public static int rightChildFather(BitNode tree) {
if (tree == null)
return 0;
else {
int left = leftChildFather(tree.lchild);
int right = leftChildFather(tree.rchild);
if ((tree.lchild == null && tree.rchild != null))
return left + right + 1;
else
return left + right;
        }
    }

// 计算有两个节点的父节点的个数
public static int doubleChildFather(BitNode tree) {
int left, right;
if (tree == null)
return 0;
else {
            left = doubleChildFather(tree.lchild);
            right = doubleChildFather(tree.rchild);
if (tree.lchild != null && tree.rchild != null)
return (left + right + 1);/* 加1是因为要算上根节点 */
else
return (left + right);
        }
    }

// 将树中的每个节点的孩子对换位置
public static void exChange(BitNode tree) {
if (tree == null)
return;
if (tree.lchild != null)
            exChange(tree.lchild);
if (tree.rchild != null)
            exChange(tree.rchild);
        BitNode temp = tree.lchild;
        tree.lchild = tree.rchild;
        tree.rchild = temp;
    }

// 递归求所有结点的和
public static int getSumByRecursion(BitNode tree) {
if (tree == null) {
return 0;
        } else {
int left = getSumByRecursion(tree.lchild);
int right = getSumByRecursion(tree.rchild);
return tree.data + left + right;
        }
    }