二叉树遍历、高度与节点数
package com.kkk.ssm.user.test;
import java.util.ArrayDeque;
import java.util.Queue;
/**
* @author kkk
* */
class TreeNode
{
TreeNode leftNode;
TreeNode rightNode;
int data=0;
public TreeNode(int data)
{
this.data=data;
}
}
public class TreeHeightTest
{
/**
* 创建树
* @return TreeNode
* */
public static TreeNode createTreeNode()
{
//二叉树中心
TreeNode tree=new TreeNode(11);
TreeNode[] node=new TreeNode[9];
for(int i=0;i<9;i++)
{
node[i]=new TreeNode(i);
}
//左子树的节点
tree.leftNode=node[0];
tree.leftNode.leftNode=node[1];
tree.leftNode.rightNode=node[2];
tree.leftNode.leftNode.leftNode=node[3];
tree.leftNode.leftNode.rightNode=node[4];
//右子树的节点
tree.rightNode=node[5];
tree.rightNode.leftNode=node[6];
tree.rightNode.rightNode=node[7];
tree.rightNode.leftNode.leftNode=node[8];
return tree;
}
/**
* 求树的高度
* @param tree
* @return height
* */
public static int TreeMaxHeight(TreeNode tree)
{
int leftHeight=0,rightHeight=0;
//树不为空，递归时会进行左子树和右子树进行遍历
if(tree!=null)
{
leftHeight=TreeMaxHeight(tree.leftNode);
rightHeight=TreeMaxHeight(tree.rightNode);
//对左右子树遍历完后,求最大的高度
return leftHeight>rightHeight?leftHeight+1:rightHeight+1;
}
return 0;
}
/**
* 求二叉树的叶子节点
* @param tree
* @return height
* */
public static int leafNodeNum(TreeNode tree)
{
//树不为空
if(tree!=null)
{
//左右节点均为空，因此只有根节点
if(tree.leftNode==null && tree.rightNode==null)
{
return 1;
}else
{
//递归查找左右节点
return leafNodeNum(tree.leftNode)+leafNodeNum(tree.rightNode);
}
}
return 0;
}
/**
* 对树的层次遍历
* 一、队列
队列是一种特殊的线性表，它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作。
进行插入操作的端称为队尾，进行删除操作的端称为队头。队列中没有元素时，称为空队列。
二、双端队列 ArrayDeque
双端队列是只既可以在表的前端进行插入和删除操作，又可以在表的后端进行插入和删除操作。
* @param tree
* @return
* */
public static void levelOrder(TreeNode tree)
{
if(tree!=null)
{
//ArrayDeque->Deque->Queue;ArrayDeque包含指定 collection 的元素的双端队列
Queue queue=new ArrayDeque();
queue.add(tree);
while(!queue.isEmpty())
{
TreeNode tempNode=queue.poll();
System.out.println("--层次遍历节点:--"+tempNode.data);
if(tempNode.leftNode!=null)
{
queue.add(tempNode.leftNode);
}
if(tempNode.rightNode!=null)
{
queue.add(tempNode.rightNode);
}
}
}
}
/**
* 先序遍历
* @param tree
* */
public static void preOrderTree(TreeNode tree)
{
if(tree!=null)
{
System.out.println("--先序root开始:--"+tree.data);
preOrderTree(tree.leftNode);
preOrderTree(tree.rightNode);
}
}
/**
* 中序遍历
* @param tree
* */
public static void inOrderTree(TreeNode tree)
{
if(tree!=null)
{
inOrderTree(tree.leftNode);
System.out.println("--中序遍历root: data--"+tree.data);
inOrderTree(tree.rightNode);
}
}
/**
* 后序遍历
* @param tree
* */
public static void afterOrderTree(TreeNode tree)
{
if(tree!=null)
{
afterOrderTree(tree.leftNode);
afterOrderTree(tree.rightNode);
System.out.println("--后序遍历 root:data--"+tree.data);
}
}
public static void main(String[] args)
{
int height=0;
int leafNum=0;
TreeNode tree=null;
height=TreeMaxHeight(tree);
System.out.println("--空树的高度--"+height);
System.out.println("******************************************************");
tree=createTreeNode();
height=TreeMaxHeight(tree);
System.out.println("--非空树的高度--"+height);
System.out.println("******************************************************");
leafNum=leafNodeNum(tree);
System.out.println("--叶子节点数--"+leafNum);
System.out.println("******************************************************");
//层次遍历
levelOrder(tree);
System.out.println("******************************************************");
//先序遍历
preOrderTree(tree);
System.out.println("******************************************************");
//中序遍历
inOrderTree(tree);
System.out.println("******************************************************");
//后续遍历
afterOrderTree(tree);
System.out.println("******************************************************");
}
}
