普通二叉树的结构、生成、前序遍历、中序遍历、后序遍历、树深度、输出某点之后的中序遍历节过等
package TestTree;
import java.util.ArrayList;
import java.util.List;
public class Tree {
private Node root;
private List<Node> list=new ArrayList<Node>();
private boolean bool = false;
private boolean bool1 = false;
public Tree(){
init();
}
//树的初始化:先从叶节点开始,由叶到根
public void init(){
Node x=new Node("X",null,null);
Node y=new Node("Y",null,null);
Node z=new Node("Z",null,null);
Node d=new Node("d",x,y);
Node e=new Node("e",null,null);
Node f=new Node("f",null,null);
Node c=new Node("c",e,f);
Node g=new Node("g",z,null);
Node b=new Node("b",d,g);
Node a=new Node("a",b,c);
root =a;
}
//定义节点类：
private class Node{
private String data;
private Node lchid;//定义指向左子树的指针
private Node rchild;//定义指向右子树的指针
public Node(String data,Node lchild,Node rchild){
this.data=data;
this.lchid=lchild;
this.rchild=rchild;
}
}
/**
* 对该二叉树进行前序遍历 结果存储到list中 前序遍历:ABDXYCEF
*/
public void preOrder(Node node)
{
list.add(node); //先将根节点存入list
//如果左子树不为空继续往左找，在递归调用方法的时候一直会将子树的根存入list，这就做到了先遍历根节点
if(node.lchid != null)
{
preOrder(node.lchid);
}
//无论走到哪一层，只要当前节点左子树为空，那么就可以在右子树上遍历，保证了根左右的遍历顺序
if(node.rchild != null)
{
preOrder(node.rchild);
}
}
/**
* 对该二叉树进行中序遍历 结果存储到list中
*/
public void inOrder(Node node)
{
if(node.lchid!=null){
inOrder(node.lchid);
}
list.add(node);
if(node.rchild!=null){
inOrder(node.rchild);
}
}
/**
* 对该二叉树进行中序遍历某个节点之后的所有节点 结果存储到list中
*/
public void inOrderMark(Node node, String mark)
{
if(node.lchid!=null){
inOrderMark(node.lchid, mark);
}
if(bool) list.add(node);
if(node.data.equals(mark)) bool = true;
if(node.rchild!=null){
inOrderMark(node.rchild, mark);
}
}
/**
* 对该二叉树进行后序遍历 结果存储到list中
*/
public void postOrder(Node node)
{
if(node.lchid!=null){
postOrder(node.lchid);
}
if(node.rchild!=null){
postOrder(node.rchild);
}
list.add(node);
}
/**
* 返回当前树的深度
* 说明:
* 1、如果一棵树只有一个结点，它的深度为1。
* 2、如果根结点只有左子树而没有右子树，那么树的深度是其左子树的深度加1；
* 3、如果根结点只有右子树而没有左子树，那么树的深度应该是其右子树的深度加1；
* 4、如果既有右子树又有左子树，那该树的深度就是其左、右子树深度的较大值再加1。
*
* @return
*/
public int getTreeDepth(Node node) {
if(node.lchid == null && node.rchild == null)
{
return 1;
}
int left=0,right = 0;
if(node.lchid!=null)
{
left = getTreeDepth(node.lchid);
}
if(node.rchild!=null)
{
right = getTreeDepth(node.rchild);
}
return left>right?left+1:right+1;
}
//找出一个完全二叉树中最后一层的最后一个节点
public void getLastPoint(Node node){
int deep = getDeep(node);
getLastNode(node, deep, 0);
}
public void getLastNode(Node node, int deep, int height){
if(bool1) return;
height++;
if(node.rchild == null && node.lchid == null && height == deep){
System.out.println(node.data);
bool1 = true;
return;
}
if(node.rchild != null){
getLastNode(node.rchild, deep, height);
}
if(node.lchid != null){
getLastNode(node.lchid, deep, height);
}
}
public int getDeep(Node node){
int height = 1;
while(node.lchid != null){
height++;
node = node.lchid;
}
return height;
}
//得到遍历结果
public List<Node> getResult()
{
return list;
}
public static void main(String[] args) {
Tree tree=new Tree();
System.out.println("根节点是:"+tree.root.data);
//tree.preOrder(tree.root);
// tree.inOrder(tree.root);
// tree.postOrder(tree.root);
tree.inOrderMark(tree.root, "b");
for(Node node:tree.getResult()){
System.out.println(node.data);
}
System.out.println("树的深度是"+tree.getTreeDepth(tree.root));
tree.getLastPoint(tree.root);
}
}
二叉排序树
package TestTree;
//二叉排序树
public class sortTree {
private Node root;
// private List<Node>
//节点类
class Node{
private int val;
private Node left;
private Node right;
public Node(int val){
this.val = val;
}
}
//对应数组生成二叉排序树
public Node getBST(int[] nums){
Node node = new Node(nums[0]);
for(int i = 1; i < nums.length; i++)
bornSortTree(node, nums[i]);
return node;
}
public Node bornSortTree(Node node, int i){
if(node == null){
node = new Node(i);
return node;
}
else{
if(i <= node.val){
node.left = bornSortTree(node.left, i);
}
else{
node.right = bornSortTree(node.right,i);
}
return node;
}
}
//中序遍历二叉排序树
public void inOrder(Node node){
if(node.left != null) inOrder(node.left);
System.out.println(node.val);
if(node.right != null) inOrder(node.right);
}
public static void main(String[] args) {
sortTree tree = new sortTree();
int[] nums = {3,1,2,5,0,7,9,8};
tree.root = tree.getBST(nums);
tree.inOrder(tree.root);
}
}