java实现二叉树及遍历、删除

标签：retthis个人网站分享依次ted中序avl创建

java实现二叉树及遍历、删除

个人网站：多猫影视【可以看各大网站的VIP视频】www.duomao.xyz

二叉树是递归定义的，其结点有左右子树之分，逻辑上二叉树有五种基本形态：
(1)空二叉树——如图(a)；

(2)只有一个根结点的二叉树——如图(b)；
(3)只有左子树——如图(c)；
(4)只有右子树——如图(d)；
(5)完全二叉树——如图(e)。
注意：尽管二叉树与树有许多相似之处，但二叉树不是树的特殊情形。[1]

类型

(1)完全二叉树——若设二叉树的高度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第h层有叶子结点，并且叶子结点都是从左到右依次排布，这就是完全二叉树。
(2)满二叉树——除了叶结点外每一个结点都有左右子叶且叶子结点都处在最底层的二叉树。
(3)平衡二叉树——平衡二叉树又被称为AVL树（区别于AVL算法），它是一棵二叉排序树，且具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

代码注释的比较详细，就不用再说明了。

package com.niu.test;

/**
* Created by Administrator>*/
public class AlvinTree {

private Node root;

//1、创建二叉树的结点（三个要素：结点数据，左结点，右结点）
private class Node {
//层序
private int key;
//结点中存储的数据
private Object data;
//左右子树
private Node leftNode;
private Node rightNode;
private boolean isVisted = false;

//空的构造方法
public Node() {
}

public Node(int key, Object data) {
this.data =http://www.mamicode.com/ data;
this.key = key;
this.leftNode = null;
this.rightNode = null;
}
}

//2、创建根节点(构造函数)
public AlvinTree() {
root = new Node(1, \”A\”);
}

//3、创建一棵树
public void