# 二叉树

### 定义

二叉树（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的右节点，否则没有右节点 。

### 实现

#### 顺序存储

```java
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);
	}
}
```

#### 链式存储

```java
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);

	}
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://kakapreter.gitbook.io/structure/nonlinear_structure/tree/ordered_tree/binary_tree.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.