顺序二叉树

不多说，直接上代码。

class ArrayBinaryTree {
	private int[] arr;

	public ArrayBinaryTree(int[] arr) {
		this.arr = arr;
	}

	public void preOrder() {
		this.preOrder(0);
	}

	public void infixOrder() {
		this.infixOrder(0);
	}
        //前序遍历
	public void preOrder(int index) {
		if (arr == null || arr.length == 0) {
			System.out.println("数组为空");
		}
		System.out.println(arr[index]);

		if (index * 2 + 1 < arr.length) {
			preOrder(index * 2 + 1);
		}
		if (index * 2 + 2 < arr.length) {
			preOrder(index * 2 + 2);
		}
	}
        //中序遍历
	public void infixOrder(int index) {
		if (arr == null || arr.length == 0) {
			System.out.println("数组为空");
		}
		if (index * 2 + 1 < arr.length) {
			infixOrder(index * 2 + 1);
		}
		System.out.println(arr[index]);
		if (index * 2 + 2 < arr.length) {
			infixOrder(index * 2 + 2);
		}
	}

        //后续遍历
}

线索二叉树

~线索化之前的二叉树，以下步骤我用中序的方法对二叉树进行线索化。

中序遍历（表格）：

寻找叶子节点（4），叶子节点在中序遍历表格中前驱节点为null，后继节点为2。因此在二叉树中4的左节点指向null，右节点指向2。如下图》》》

~在上图的基础上在对4的兄弟节点5进行线索化。步骤如上，先在中序表格中寻找5节点的前驱和后继，之后再连接（因为5的前驱为2，后继为1，按如下图进行连接）。

~按上述步骤继续进行。直到不能再线索化，上述例子中node到3位置就不能再进行线索化。

~遍历的方法根据线索化的方式不同，遍历的方式也不同，根据中序遍历，照葫芦画瓢，可以自己写出。

//线索化二叉树
//0表示指向左子树,右子树，1只想前驱节点,后继节点
class BinaryTree {
	private HeroNode root;
	private HeroNode pre = null;

	public void setRoot(HeroNode root) {
		this.root = root;
	}

	// 中序线索化
	public void threadedNodesInfix() {
		this.threadedNodesInfix(root);
	}

	// 前序线索化
	public void threadedNodePre() {
		this.threadedNodePre(root);
	}

	// 遍历中序线索二叉树
	public void threadListInfix() {
		HeroNode node = root;
		while (node != null) {
			while (node.getLeftType() == 0) {    
				node = node.getLeft();
			}
			System.out.println(node);
			while (node.getRightType() == 1) {
				node = node.getRight();
				System.out.println(node);
			}
			node = node.getRight();
		}
	}

	// 遍历前序线索二叉树
	public void threadListPre() {
		HeroNode node = root;
		while (node != null) {
			System.out.println(node);
			
			while (node.getLeftType() == 0) {
				node = node.getLeft();
				System.out.println(node);
			}
			while (node.getRightType() == 1) {
				node = node.getRight();
				System.out.println(node);
			}
			node = node.getRight();
		}
	}

	// 对二叉树进行中序线索化
	public void threadedNodesInfix(HeroNode node) {
		if (node == null) {
			System.out.println("不能线索化");
			return;
		}
		// 线索化左子树
		threadedNodesInfix(node.getLeft());

		// 线索化当前节点
		if (node.getLeft() == null) {
			node.setLeft(pre);
			node.setLeftType(1);
		}
		if (pre != null && pre.getRight() == null) {
			pre.setRight(node);
			pre.setRightType(1);
		}
		pre = node;

		// 线索化右子树
		threadedNodesInfix(node.getRight());
	}

	// 对二叉树进行前序线索化
	public void threadedNodePre(HeroNode node) {
		if (node == null) {
			System.out.println("不能线索化");
			return;
		}

		// 线索化当前节点
		if (node.getLeft() == null) {
			node.setLeft(pre);
			node.setLeftType(1);
		}
		if (pre != null && pre.getRight() == null) {
			pre.setRight(node);
			pre.setRightType(1);
		}
		pre = node;

		// 线索化左子树
		if (node.getLeftType() != 1)
			threadedNodePre(node.getLeft());

		// 线索化右子树
		if (node.getRightType() != 1)
			threadedNodePre(node.getRight());
	}

}

class HeroNode {
	private int no;
	private String name;
	private HeroNode left;
	private HeroNode right;
	Queue<HeroNode> q = new LinkedList<HeroNode>();

	// 0表示指向左子树,右子树，1只想前驱节点,后继节点
	private int leftType = 0;
	private int rightType = 0;

	HeroNode(int no, String name) {
		this.no = no;
		this.name = name;
	}

	public int getNo() {
		return no;
	}

	public void setNo(int no) {
		this.no = no;
	}

	public String getName() {
		return name;
	}

	public void setName(String name) {
		this.name = name;
	}

	public HeroNode getLeft() {
		return left;
	}

	public void setLeft(HeroNode left) {
		this.left = left;
	}

	public HeroNode getRight() {
		return right;
	}

	public void setRight(HeroNode right) {
		this.right = right;
	}

	public int getLeftType() {
		return leftType;
	}

	public void setLeftType(int leftType) {
		this.leftType = leftType;
	}

	public int getRightType() {
		return rightType;
	}

	public void setRightType(int rightType) {
		this.rightType = rightType;
	}

	@Override
	public String toString() {
		return "HeroNode [no=" + no + ", name=" + name + "]";
	}

}

二叉排序树

图解：

初始数组：

根据初始数组建立二叉排序树:

是根据上述步骤建立排序二叉树。直接上代码。二叉排序树的中序遍历是数组的递增遍历。下述代码进行对二叉排序树的删除，当要删除的节点为叶子节点，非叶子节点（只有一个子节点，有两个子节点）时分情况删除。

class BinarySortTree {
	private Node root;

	// 返回以node为节点的二叉排序树的最小节点的值
	public int delRightTreeMin(Node node) {
		Node temp = node;
		while (temp.left != null) {
			temp = temp.left;
		}
		delNode(temp.value);
		return temp.value;
	}

	// 查找要删除的节点
	public Node search(int value) {
		if (root == null)
			return null;
		else
			return root.search(value);
	}

	// 查找要删除节点的父节点
	public Node searchParent(int value) {
		if (root == null)
			return null;
		else
			return root.searchParent(value);
	}
        
        /******************************************删除开始**************************************************/
	public void delNode(int value) {
		if (root == null) {
			return;
		} else {
			Node target = search(value);
			if (target == null) {
				return;
			}
			if (root.left == null && root.right == null) {
				root = null;
			}
			Node parent = searchParent(value);
			if (target.left == null && target.right == null) { // 当目标节点为叶子节点时
				// if(target.value < parent.value)
				if (parent.left != null && parent.left.value == value)
					parent.left = null;
				else if (parent.right != null && parent.right.value == value)
					parent.right = null;
			} else if (target.left != null && target.right != null) { // 删除有两个节点的节点
				int min = delRightTreeMin(target.right);
				target.value = min;
			} else { // 删除只有一颗子树的节点
				if (target.left != null) {
					if (parent.left.value == value) {
						parent.left = target.left;
					} else {
						parent.right = target.left;
					}
				} else {
					if (parent.left.value == value) {
						parent.left = target.right;
					} else {
						parent.right = target.right;
					}
				}
			}
		}
	}
        /******************************************删除结束**************************************************/

	public void add(Node node) {
		if (root == null) {
			root = node;
		} else {
			root.add(node);
		}
	}

	public void infixOrder() {
		root.infixOrder();
	}
}

class Node {
	int value;
	Node left;
	Node right;

	public Node(int value) {
		this.value = value;
	}

	// 查找要删除的节点
	public Node search(int value) {
		if (value == this.value) {
			return this;
		} else if (value < this.value) {
			if (this.left == null)
				return null;
			return this.left.search(value);
		} else {
			if (this.right == null)
				return null;
			return this.right.search(value);
		}
	}

	// 查找要删除节点的父节点
	public Node searchParent(int value) {
		if ((this.left != null && this.left.value == value) || (this.right != null && this.right.value == value)) {
			return this;
		} else {
			if (value < this.value && this.left != null) {
				return this.left.searchParent(value);
			} else if (value >= this.value && this.right != null) {
				return this.right.searchParent(value);
			} else {
				return null;
			}
		}
	}

	// 递归的形式添加，二叉排序树
	public void add(Node node) {
		if (node == null)
			return;

		if (node.value < this.value) {
			if (this.left == null) {
				this.left = node;
			} else {
				this.left.add(node);
			}
		} else {
			if (this.right == null) {
				this.right = node;
			} else {
				this.right.add(node);
			}
		}
	}

	public void infixOrder() {
		if (this.left != null)
			this.left.infixOrder();

		System.out.println(this);

		if (this.right != null) {
			this.right.infixOrder();
		}
	}

	@Override
	public String toString() {
		return "Node [value=" + value + "]";
	}

}

AVL树

如{3，6，5，4，7}这样的数组实现二叉排序树

如上述图，二叉排序树变成了单链表，二叉树的层数变得特别深，这样对我们的查询不利，所以我们要减少二叉排序树的层数。

所以我们需要根据情况进行二叉排序树的左旋转，右旋转和双旋转。

1，下种情况我们需要左旋转。当右子树的深度比左子树的深度大于1层时进行左旋转。

左旋转的步骤：

1,创建新节点newNode，值为当前节点的值
2,newNode的左子树 =》当前节点的左子树
3,newNode的右子树 =》当前节点的右子树的左子树
4,把当前节点的值换成右子树的值
5,把当前节点的右子树 =》右子树的右子树
6,把当前节点的左子树 =》 newNode

可以根据上述步骤自己画图领会。右旋转的情况和方法也跟左旋转差不多。当左子树的深度比右子树的深度大于1的时候进行右旋转。步骤跟左旋转差不多，所以不多些。

2，当如下图情况只进行左旋转发现，现在左子树比右子树深，这时候（当需要进行左旋转时，如果当前节点{3}的右子树的左子树的深度比以{3}为节点右子树的右子树的深度大的话）以{7}节点为当前节点进行右旋转，之后在以{3}节点作为当前节点进行左旋转。

因为这个条件是当进行节点添加的时候进行的所以只展现上述代码的改进的部分。

===================================》

// 左旋转
	private void leftRotate() {
		// 创建新节点，值为当前节点的值
		Node newNode = new Node(this.value);
		// newNode的左子树 =》当前节点的左子树
		newNode.left = this.left;
		// newNode的右子树 =》 当前节点的右子树的左子树
		newNode.right = this.right.left;
		// 把当前节点的值换成右子树的值
		this.value = this.right.value;
		// 把当前节点的右子树 =》 右子树的右子树
		this.right = this.right.right;
		// 把当前节点的左子树 =》 newNode
		this.left = newNode;
	}

// 右旋转
	private void rightRotate() {
		Node newNode = new Node(this.value);
		newNode.right = this.right;
		newNode.left = this.left.right;
		this.value = this.left.value;
		this.left = this.left.left;
		this.right = newNode;
	}

// 递归的形式添加，二叉排序树(这是二叉排序树的添加函数，在这里进行判断是否要进行双旋转还是要进行左右旋转)
	public void add(Node node) {
		if (node == null)
			return;

		if (node.value < this.value) {
			if (this.left == null) {
				this.left = node;
			} else {
				this.left.add(node);
			}
		} else {
			if (this.right == null) {
				this.right = node;
			} else {
				this.right.add(node);
			}
		}
		// 当添加完节点后，如果右子树的高度比左子树的高度大于1
		if (this.rightHeight() - this.leftHeight() > 1) {
			if (this.right != null && this.right.leftHeight() > this.right.rightHeight()) {
				this.left.rightRotate();
				leftRotate();
			} else {
				leftRotate();
			}
			return;
		}

		if (this.leftHeight() - this.rightHeight() > 1) {
			if (this.left != null && this.left.rightHeight() > this.left.leftHeight()) {
				left.leftRotate();
				rightRotate();
			} else {
				rightRotate();
			}
		}
	}

关于顺序二叉树,线索二叉树,二叉排序树,AVL树的浅谈

顺序二叉树

线索二叉树

二叉排序树

图解：

AVL树