//******************************************************************************************************//
//*****本程序包括简单的二叉树类的实现和前序,中序,后序,层次遍历二叉树算法,*******//
//******以及确定二叉树的高度,制定对象在树中的所处层次以及将树中的左右***********//
//******孩子节点对换位置,返回叶子节点个数删除叶子节点,并输出所删除的叶子节点**//
//*******************************CopyRight By phoenix*******************************************//
//****************************************************************************************************//
public class BinTree {
private Object data; //数据元数
private BinTree left,right; //指向左,右孩子结点的链
BinTree []elements = new BinTree[MAX];//层次遍历时保存各个节点
int front;//层次遍历时队首
int rear;//层次遍历时队尾
public BinTree()
{
}
public BinTree(Object data)
{ //构造有值结点
this.data = data;
left = right = null;
public BinTree(Object data,BinTree left,BinTree right)
this.left = left;
this.right = right;
public String toString()
return data.toString();
}//前序遍历二叉树
public static void preOrder(BinTree parent){
if(parent == null)
return;
System.out.print(parent.data+" ");
preOrder(parent.left);
preOrder(parent.right);
}//中序遍历二叉树
public void inOrder(BinTree parent){
inOrder(parent.left);
inOrder(parent.right);
}//后序遍历二叉树
public void postOrder(BinTree parent){
postOrder(parent.left);
postOrder(parent.right);
}// 层次遍历二叉树
public void LayerOrder(BinTree parent)
elements[0]=parent;
front=0;rear=1;
while(frontrear)
try
if(elements[front].data!=null)
System.out.print(elements[front].data + " ");
if(elements[front].left!=null)
elements[rear++]=elements[front].left;
if(elements[front].right!=null)
elements[rear++]=elements[front].right;
front++;
}catch(Exception e){break;}
}//返回树的叶节点个数
public int leaves()
if(this == null)
return 0;
if(left == nullright == null)
return 1;
return (left == null ? 0 : left.leaves())+(right == null ? 0 : right.leaves());
}//结果返回树的高度
public int height()
int heightOfTree;
return -1;
int leftHeight = (left == null ? 0 : left.height());
int rightHeight = (right == null ? 0 : right.height());
heightOfTree = leftHeightrightHeight?rightHeight:leftHeight;
return 1 + heightOfTree;
//如果对象不在树中,结果返回-1;否则结果返回该对象在树中所处的层次,规定根节点为第一层
public int level(Object object)
int levelInTree;
if(object == data)
return 1;//规定根节点为第一层
int leftLevel = (left == null?-1:left.level(object));
int rightLevel = (right == null?-1:right.level(object));
if(leftLevel0rightLevel0)
levelInTree = leftLevelrightLevel?rightLevel:leftLevel;
return 1+levelInTree;
//将树中的每个节点的孩子对换位置
public void reflect()
if(left != null)
left.reflect();
if(right != null)
right.reflect();
BinTree temp = left;
left = right;
right = temp;
}// 将树中的所有节点移走,并输出移走的节点
public void defoliate()
String innerNode = "";
//若本节点是叶节点,则将其移走
if(left==nullright == null)
System.out.print(this + " ");
data = null;
//移走左子树若其存在
if(left!=null){
left.defoliate();
left = null;
//移走本节点,放在中间表示中跟移走...
innerNode += this + " ";
//移走右子树若其存在
if(right!=null){
right.defoliate();
right = null;
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
BinTree e = new BinTree("E");
BinTree g = new BinTree("G");
BinTree h = new BinTree("H");
BinTree i = new BinTree("I");
BinTree d = new BinTree("D",null,g);
BinTree f = new BinTree("F",h,i);
BinTree b = new BinTree("B",d,e);
BinTree c = new BinTree("C",f,null);
BinTree tree = new BinTree("A",b,c);
System.out.println("前序遍历二叉树结果: ");
tree.preOrder(tree);
System.out.println();
System.out.println("中序遍历二叉树结果: ");
tree.inOrder(tree);
System.out.println("后序遍历二叉树结果: ");
tree.postOrder(tree);
System.out.println("层次遍历二叉树结果: ");
tree.LayerOrder(tree);
System.out.println("F所在的层次: "+tree.level("F"));
System.out.println("这棵二叉树的高度: "+tree.height());
System.out.println("--------------------------------------");
tree.reflect();
System.out.println("交换每个节点的孩子节点后......");
分析二叉树的深度（高度）和它的左、右子树深度之间的关系.从二叉树深度的定义可知,二叉树的深度应为其左、右子树深度的最大值加1.由此,需先分别求得左、右子树的深度,算法中"访问结点"的操作为：求得左、右子树深度的最大值,然后加 1 .
int Depth (BiTree T ){ // 返回二叉树的深度
if ( !T ) depthval = 0;
else {
depthLeft = Depth( T-lchild );
depthRight= Depth( T-rchild );
depthval = 1 + (depthLeft depthRight ?
depthLeft : depthRight);
return depthval;
扩展资料：
二叉树的深度是从根节点开始（其深度为1）自顶向下逐层累加的；而二叉树高度是从叶节点开始（其高度为1）自底向上逐层累加的.虽然树的深度和高度一样,但是具体到树的某个节点,其深度和高度是不一样的.
* @author WangXuanmin
* @version 0.10
private StringBuffer bef=new StringBuffer();
//传入中序遍历和后序遍历,返回前序遍历字串
public String getBef(String mid, String beh) {
//若节点存在则向bef中添加该节点,继续查询该节点的左子树和右子树
if (root(mid, beh) != -1) {
int rootindex=root(mid, beh);
char root=mid.charAt(rootindex);
bef.append(root);
System.out.println(bef.toString());
String mleft, mright;
mleft = mid.substring(0,rootindex);
mright = mid.substring(rootindex+1);
getBef(mleft,beh);
getBef(mright,beh);
//所有节点查询完毕,返回前序遍历值
return bef.toString();
//从中序遍历中根据后序遍历查找节点索引值index
private int root(String mid, String beh) {
char[] midc = mid.toCharArray();
char[] behc = beh.toCharArray();
for (int i = behc.length-1; i -1; i--) {
for (int j = 0; j midc.length; j++) {
if (behc[i] == midc[j])
return j;
System.out.println(tree.getBef(mid,bef));
树结构如图:
|-------|
|---| |---|
|-| |-|
java构造二叉树,可以通过链表来构造,如下代码：
public?class?BinTree?{
BinTree?[]elements?=?new?BinTree[MAX];//层次遍历时保存各个节点
int?front;//层次遍历时队首
int?rear;//层次遍历时队尾
private?Object?data;?//数据元数
private?BinTree?left,right;?//指向左,右孩子结点的链
public?BinTree()
public?BinTree(Object?data)
{?//构造有值结点
this.data?=?data;
left?=?right?=?null;
public?BinTree(Object?data,BinTree?left,BinTree?right)
this.left?=?left;
this.right?=?right;
public?String?toString()
return?data.toString();
//前序遍历二叉树
public?static?void?preOrder(BinTree?parent){?
if(parent?==?null)
System.out.print(parent.data+"?");
//中序遍历二叉树
public?void?inOrder(BinTree?parent){
//后序遍历二叉树
public?void?postOrder(BinTree?parent){
//?层次遍历二叉树?
public?void?LayerOrder(BinTree?parent)
{?
System.out.print(elements[front].data?+?"?");
}catch(Exception?e){break;}
//返回树的叶节点个数
public?int?leaves()
if(this?==?null)
return?0;
if(left?==?nullright?==?null)
return?1;
return?(left?==?null?0?:?left.leaves())+(right?==?null?0?:?right.leaves());
//结果返回树的高度
public?int?height()
int?heightOfTree;
return?-1;
int?leftHeight?=?(left?==?null?0?:?left.height());
int?rightHeight?=?(right?==?null?0?:?right.height());
heightOfTree?=?leftHeightrightHeight?rightHeight:leftHeight;
return?1?+?heightOfTree;
public?int?level(Object?object)
int?levelInTree;
if(object?==?data)
return?1;//规定根节点为第一层
int?leftLevel?=?(left?==?null?-1:left.level(object));
int?rightLevel?=?(right?==?null?-1:right.level(object));
levelInTree?=?leftLevelrightLevel?rightLevel:leftLevel;
return?1+levelInTree;
public?void?reflect()
if(left?!=?null)
if(right?!=?null)
BinTree?temp?=?left;
left?=?right;
right?=?temp;
//?将树中的所有节点移走,并输出移走的节点
public?void?defoliate()
if(left==nullright?==?null)
System.out.print(this?+?"?");
data?=?null;
left?=?null;
String?innerNode?+=?this?+?"?";
right?=?null;
public?static?void?main(String[]?args)?{
//?TODO?Auto-generated?method?stub
BinTree?e?=?new?BinTree("E");
BinTree?g?=?new?BinTree("G");
BinTree?h?=?new?BinTree("H");
BinTree?i?=?new?BinTree("I");
BinTree?d?=?new?BinTree("D",null,g);
BinTree?f?=?new?BinTree("F",h,i);
BinTree?b?=?new?BinTree("B",d,e);
BinTree?c?=?new?BinTree("C",f,null);
BinTree?tree?=?new?BinTree("A",b,c);
System.out.println("前序遍历二叉树结果:?");
System.out.println("中序遍历二叉树结果:?");
System.out.println("后序遍历二叉树结果:?");
System.out.println("层次遍历二叉树结果:?");
System.out.println("F所在的层次:?"+tree.level("F"));
System.out.println("这棵二叉树的高度:?"+tree.height());
import java.util.ArrayList;
// 树的一个节点
class TreeNode {
Object _value = null; // 他的值
TreeNode _parent = null; // 他的父节点,根节点没有PARENT
ArrayList _childList = new ArrayList(); // 他的孩子节点
public TreeNode( Object value, TreeNode parent ){
this._parent = parent;
this._value = value;
public TreeNode getParent(){
return _parent;
public String toString() {
return _value.toString();
public class Tree {
// 给出宽度优先遍历的值数组,构建出一棵多叉树
// null 值表示一个层次的结束
// "|" 表示一个层次中一个父亲节点的孩子输入结束
// 如：给定下面的值数组：
// { "root", null, "left", "right", null }
// 则构建出一个根节点,带有两个孩子("left","right")的树
public Tree( Object[] values ){
// 创建根
_root = new TreeNode( values[0], null );
// 创建下面的子节点
TreeNode currentParent = _root; // 用于待创建节点的父亲
//TreeNode nextParent = null;
int currentChildIndex = 0; // 表示 currentParent 是他的父亲的第几个儿子
//TreeNode lastNode = null; // 最后一个创建出来的TreeNode,用于找到他的父亲
// 如果null ,表示下一个节点的父亲是当前节点的父亲的第一个孩子节点
if ( values[i] == null ){
currentParent = (TreeNode)currentParent._childList.get(0);
currentChildIndex = 0;
continue;
// 表示一个父节点的所有孩子输入完毕
if ( values[i].equals("|") ){
if ( currentChildIndex+1 currentParent._childList.size() ){
currentChildIndex++;
currentParent = (TreeNode)currentParent._parent._childList.get(currentChildIndex);
TreeNode child = createChildNode( currentParent, values[i] );
TreeNode _root = null;
public TreeNode getRoot(){
return _root;
// 按宽度优先遍历,打印出parent子树所有的节点
private void printSteps( TreeNode parent, int currentDepth ){
for ( int i = 0; i parent._childList.size(); i++ ){
TreeNode child = (TreeNode)parent._childList.get(i);
System.out.println(currentDepth+":"+child);
if ( parent._childList.size() != 0 ) System.out.println(""+null);// 为了避免叶子节点也会打印null
//打印 parent 同层的节点的孩子
if ( parent._parent != null ){ // 不是root
int i = 1;
while ( i parent._parent._childList.size() ){// parent 的父亲还有孩子
TreeNode current = (TreeNode)parent._parent._childList.get(i);
printSteps( current, currentDepth );
i++;
// 递归调用,打印所有节点
printSteps( child, currentDepth+1 );
public void printSteps(){
System.out.println(""+_root);
System.out.println(""+null);
printSteps(_root, 1 );
}**/
// 将给定的值做为 parent 的孩子,构建节点
private TreeNode createChildNode( TreeNode parent, Object value ){
TreeNode child = new TreeNode( value , parent );
parent._childList.add( child );
return child;
Tree tree = new Tree( new Object[]{ "root", null,
"left", "right", null,
//tree.printSteps();
System.out.println(""+ ( (TreeNode)tree.getRoot()._childList.get(0) )._childList.get(0) );
System.out.println(""+ ( (TreeNode)tree.getRoot()._childList.get(0) )._childList.get(1) );
System.out.println(""+ ( (TreeNode)tree.getRoot()._childList.get(1) )._childList.get(0) );
System.out.println(""+ ( (TreeNode)tree.getRoot()._childList.get(1) )._childList.get(1) );
java：二叉树添加和查询方法
package arrays.myArray;
public class BinaryTree {
private Node root;
// 添加数据
public void add(int data) {
// 递归调用
if (null == root)
root = new Node(data, null, null);
else
addTree(root, data);
private void addTree(Node rootNode, int data) {
// 添加到左边
if (rootNode.data data) {
if (rootNode.left == null)
rootNode.left = new Node(data, null, null);
addTree(rootNode.left, data);
} else {
// 添加到右边
if (rootNode.right == null)
rootNode.right = new Node(data, null, null);
addTree(rootNode.right, data);
// 查询数据
public void show() {
showTree(root);
private void showTree(Node node) {
if (node.left != null) {
showTree(node.left);
System.out.println(node.data);
if (node.right != null) {
showTree(node.right);
class Node {
int data;
Node left;
Node right;
public Node(int data, Node left, Node right) {
二叉树具有以下重要性质：
证明：用数学归纳法证明：
证明：在具有相同深度的二叉树中,仅当每一层都含有最大结点数时,其树中结点数最多.所以呢利用性质1可得,深度为k的二叉树的结点数至多为：
故命题正确.
树中只有根结点不是任何结点的孩子,故二叉树中的结点总数又可表示为：
满二叉树和完全二叉树是二叉树的两种特殊情形.
①.、满二叉树(FullBinaryTree)
满二叉树的特点：
（1） 每一层上的结点数都达到最大值.即对给定的高度,它是具有最多结点数的二叉树.
特点：
（1） 满二叉树是完全二叉树,完全二叉树不一定是满二叉树.
如图(c)中,结点F没有左孩子而有右孩子L,故它不是一棵完全二叉树.
图(b)是一棵完全二叉树.
证明：设所求完全二叉树的深度为k.由完全二叉树定义可得：
由于完全二叉树深度为k,故第k层上还有若干个结点,所以呢该完全二叉树的结点个数：
k-1≤lgnk
又因k-1和k是相邻的两个整数,故有
,
由此即得：
注意：
的证明
以上就是土嘎嘎小编为大家整理的二叉树的高度java代码相关主题介绍,如果您觉得小编更新的文章只要能对粉丝们有用,就是我们最大的鼓励和动力,不要忘记讲本站分享给您身边的朋友哦！！