二叉树
定义
二叉树（binary tree）是指树中节点的度不大于2的有序树，它是一种最简单且最重要的树。
二叉树的递归定义为：
二叉树是一棵空树，或者是一棵由一个根节点和两棵互不相交的，分别称作根的左子树和右子树组成的非空树；左子树和右子树又同样都是二叉树 。
二叉树性质
性质1：二叉树的第i层上至多有2i-1（i≥1）个节点 。
性质2：深度为h的二叉树中至多含有2h-1个节点 。
性质3：若在任意一棵二叉树中，有n0个叶子节点，有n2个度为2的节点，则必有n0=n2+1。
性质4：具有n个节点的满二叉树深为log2n+1。
性质5：若对一棵有n个节点的完全二叉树进行顺序编号（1≤i≤n），那么，对于编号为i（i≥1）的节点：
当i=1时，该节点为根，它无双亲节点。
当i>1时，该节点的双亲节点的编号为i/2 。
若2i≤n，则有编号为2i的左节点，否则没有左节点。
若2i+1≤n，则有编号为2i+1的右节点，否则没有右节点 。
实现
顺序存储
public class ArrayBinaryTree<T> {
private Object[] arr; // 用数组来存储树的所有节点
private int deep; // 保存该树的深度
private int size; // 数组大小
private static final int DEFAULT_DEEP = 5; // 树的默认深度
/**
* 以默认的深度来创建二叉树
*/
public ArrayBinaryTree() {
this.deep = DEFAULT_DEEP;
this.size = (int) Math.pow(2, deep) - 1; // Math.pow(2,deep)返回第一个参数的第二个参数次幂的值
arr = new Object[size];
}
/**
* 以指定深度来创建二叉树
* @param deep
*/
public ArrayBinaryTree(int deep) {
this.deep = deep;
this.size = (int) Math.pow(2, deep) - 1;
arr = new Object[size];
}
/**
* 以指定深度,指定根节点创建二叉树
*
* @param deep 树的深度
* @param data 数据
*/
public ArrayBinaryTree(int deep, T data) {
this.deep = deep;
this.size = (int) Math.pow(2, deep) - 1;
arr = new Object[size];
arr[0] = data; // 根节点
}
/**
* 为指定节点添加子节点。
*
* @param index 需要添加子节点的父节点的索引
* @param data 新子节点的数据
* @param left 是否为左节点
*/
public void add(int index, T data, boolean left) {
if (arr[index] == null) {
throw new RuntimeException(index + "处节点为空，无法添加子节点");
}
if (2 * index + 1 >= size) {
throw new IndexOutOfBoundsException();
}
if (left) {
arr[2 * index + 1] = data; // 添加左子节点
} else {
arr[2 * index + 2] = data; // 添加右子结点
}
}
/**
* 判断二叉树是否为空
* @return
*/
public boolean isEmpty() {
return arr[0] == null; // 根据根元素来判断二叉树是否为空
}
/**
* 返回根节点
* @return
*/
@SuppressWarnings("unchecked")
public T getRoot() {
return (T) arr[0];
}
/**
* 返回指定节点（非根节点）的父节点
* @param index
* @return
*/
@SuppressWarnings("unchecked")
public T getParent(int index) {
return (T) arr[(index - 1) / 2];
}
/**
* 返回指定节点（非叶子）的左子节点，当左子节点不存在时返回null
* @param index
* @return
*/
@SuppressWarnings("unchecked")
public T getLeft(int index) {
if (2 * index + 1 >= size) {
throw new RuntimeException("该节点为叶子节点，无子节点");
}
return (T) arr[index * 2 + 1];
}
/**
* 返回指定节点（非叶子）的右子节点，当右子节点不存在时返回null
* @param index
* @return
*/
@SuppressWarnings("unchecked")
public T getRight(int index) {
if (2 * index + 1 >= size) {
throw new RuntimeException("该节点为叶子节点，无子节点");
}
return (T) arr[index * 2 + 2];
}
/**
* 返回该二叉树的深度。
* @param index
* @return
*/
public int getDeep(int index) {
return deep;
}
/**
* 返回指定节点的位置。
* @param data
* @return
*/
public int index(T data) {
for (int i = 0; i < size; i++) { // 该循环实际上就是按广度遍历来搜索每个节点
if (arr[i].equals(data)) {
return i;
}
}
return -1;
}
/**
* 打印数组
*/
public String toString() {
return Arrays.toString(arr);
}
/**
* 测试方法
* @param args
*/
public static void main(String[] args) {
ArrayBinaryTree<String> binTree = new ArrayBinaryTree<String>(4, "根结点");
binTree.add(0, "第二层右子节点", false); // 第一个参数为需要添加子节点的父节点的索引： 即根节点
binTree.add(2, "第三层右子节点", false);
binTree.add(6, "第四层右子节点", false);
System.out.println(binTree);
}
}链式存储
class TreeNode {
private int key = 0;
private String data = null;
private boolean isVisted = false;
private TreeNode leftChild = null;
private TreeNode rightChild = null;
public TreeNode() {
}
public TreeNode(int key, String data) {
this.key = key;
this.data = data;
this.leftChild = null;
this.rightChild = null;
}
public int getKey() {
return key;
}
public void setKey(int key) {
this.key = key;
}
public String getData() {
return data;
}
public void setData(String data) {
this.data = data;
}
public TreeNode getLeftChild() {
return leftChild;
}
public void setLeftChild(TreeNode leftChild) {
this.leftChild = leftChild;
}
public TreeNode getRightChild() {
return rightChild;
}
public void setRightChild(TreeNode rightChild) {
this.rightChild = rightChild;
}
public boolean isVisted() {
return isVisted;
}
public void setVisted(boolean isVisted) {
this.isVisted = isVisted;
}
}
public class BinaryTree {
private TreeNode root = null;
public BinaryTree() {
root = new TreeNode(1, "rootNode(A)");
}
public void createBinTree(TreeNode root) {
// 手动的创建(结构如图所示)
TreeNode newNodeB = new TreeNode(2, "B");
TreeNode newNodeC = new TreeNode(3, "C");
TreeNode newNodeD = new TreeNode(4, "D");
TreeNode newNodeE = new TreeNode(5, "E");
TreeNode newNodeF = new TreeNode(6, "F");
root.setLeftChild(newNodeB);
root.setRightChild(newNodeC);
root.getLeftChild().setLeftChild(newNodeD);
root.getLeftChild().setRightChild(newNodeE);
root.getRightChild().setRightChild(newNodeF);
}
public boolean IsEmpty() {
// 判二叉树空否
return root == null;
}
public int Height() {
// 求树高度
return Height(root);
}
public int Height(TreeNode subTree) {
if (subTree == null)
return 0; // 递归结束：空树高度为0
else {
int i = Height(subTree.getLeftChild());
int j = Height(subTree.getRightChild());
return (i < j) ? j + 1 : i + 1;
}
}
public int Size() {
// 求结点数
return Size(root);
}
public int Size(TreeNode subTree) {
if (subTree == null)
return 0;
else {
return 1 + Size(subTree.getLeftChild())
+ Size(subTree.getRightChild());
}
}
public TreeNode Parent(TreeNode element) {
// 返回双亲结点
return (root == null || root == element) ? null : Parent(root, element);
}
public TreeNode Parent(TreeNode subTree, TreeNode element) {
if (subTree == null)
return null;
if (subTree.getLeftChild() == element
|| subTree.getRightChild() == element)
// 找到, 返回父结点地址
return subTree;
TreeNode p;
// 先在左子树中找，如果左子树中没有找到，才到右子树去找
if ((p = Parent(subTree.getLeftChild(), element)) != null)
// 递归在左子树中搜索
return p;
else
// 递归在左子树中搜索
return Parent(subTree.getRightChild(), element);
}
public TreeNode LeftChild(TreeNode element) {
// 返回左子树
return (element != null) ? element.getLeftChild() : null;
}
public TreeNode RightChild(TreeNode element) {
// 返回右子树
return (element != null) ? element.getRightChild() : null;
}
public TreeNode getRoot() {
// 取得根结点
return root;
}
public void destroy(TreeNode subTree) {
// 私有函数: 删除根为subTree的子树
if (subTree != null) {
destroy(subTree.getLeftChild()); // 删除左子树
destroy(subTree.getRightChild()); // 删除右子树
// delete subTree; //删除根结点
subTree = null;
}
}
public void Traverse(TreeNode subTree) {
System.out.println("key:" + subTree.getKey() + "--name:"
+ subTree.getData());
Traverse(subTree.getLeftChild());
Traverse(subTree.getRightChild());
}
public void PreOrder(TreeNode subTree) {
// 先根
if (subTree != null) {
visted(subTree);
PreOrder(subTree.getLeftChild());
PreOrder(subTree.getRightChild());
}
}
public void InOrder(TreeNode subTree) {
// 中根
if (subTree != null) {
InOrder(subTree.getLeftChild());
visted(subTree);
InOrder(subTree.getRightChild());
}
}
public void PostOrder(TreeNode subTree) {
// 后根
if (subTree != null) {
PostOrder(subTree.getLeftChild());
PostOrder(subTree.getRightChild());
visted(subTree);
}
}
public void LevelOrder(TreeNode subTree) {
// 水平遍边
}
public boolean Insert(TreeNode element) {
// 插入
return true;
}
public boolean Find(TreeNode element) {
// 查找
return true;
}
public void visted(TreeNode subTree) {
subTree.setVisted(true);
System.out.println("key:" + subTree.getKey() + "--name:"
+ subTree.getData());
}
public static void main(String[] args) {
BinaryTree bt = new BinaryTree();
bt.createBinTree(bt.root);
System.out.println("the size of the tree is " + bt.Size());
System.out.println("the height of the tree is " + bt.Height());
System.out.println("*******先根(前序)[ABDECF]遍历*****************");
bt.PreOrder(bt.root);
System.out.println("*******中根(中序)[DBEACF]遍历*****************");
bt.InOrder(bt.root);
System.out.println("*******后根(后序)[DEBFCA]遍历*****************");
bt.PostOrder(bt.root);
}
}Last updated