《算法导论》学习笔记之Chapter12二叉树基本特点，及二叉搜索树（查找树）_考虑一个二值搜索树 ,它的键是不同的。表明,如果 中的一个节点 的右子树

第12章 二叉搜索树

在学习二叉搜索树之前，我准备先预习一下二叉树的概念和相关算法。

二叉树拥有结合有序数组和链表的优点，查找数据和在数组中查找一样快，插入删除数据则有和链表一样高效的性能，所以是面试中必问的知识点。

二叉树的基本概念：

结点的度-结点所拥有子树的个数称为该结点的度；

叶结点-度为0的结点称为叶结点，或者终端节点；

分枝结点-度不为0的结点称为分枝结点，或者非终端结点。一棵树的结点除叶结点外，其余均为分枝结点；

左孩子、右孩子、双亲-树中一个结点的子树的根节点称为这个结点的孩子。这个结点称为他孩子节点的双亲。具有同一个双亲的孩子结点互称为兄弟；

路径、路径长度-如果一棵树的一串结点n1,n2,...,nk有如下关系：结点ni是ni+n1的父结点（1<=i<=k），就把n1,n2,...,nk称为一条由n1至nk的路径。这条路径的长度是k-1；

祖先、子孙-在树中，如果有一条路径从结点M到结点N，那么结点M就成为N的祖先，而N称为M的子孙；

结点的层数-规定树的根结点的层数为1，其余结点的层数等于他的双亲结点的层数加1；

树的深度-树中所有结点的最大层数就是树的深度；

树的度-树中各结点度的最大值称为该树的度，叶子结点的度为0。

满二叉树-在一棵二叉树中，如果所有分枝结点都存在左子树和右子树，并且所有叶子结点都在同一层上，这样的一棵二叉树称作满二叉树；

完全二叉树-一颗深度为K的有n个结点的二叉树，对树中的结点按从上至下，从左至右的顺序进行编号，如果编号为i（1<=i<=n）的结点与满二叉树中编号为i的结点在二叉树中的位置相同，那么这棵二叉树被称为完全二叉树。完全二叉树的特点是：叶子结点只能出现在最下层和次下层，且最下层的叶子结点集中在树的左部。注意：满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树。

二叉树的基本性质：

一颗非空二叉树的第i层上最多有2.^(i-1)个结点（i>=1）；

一颗深度为k的二叉树中，最多具有2.^k-1个结点，最少有k个结点；

对于一颗非空二叉树，度为0的结点（即叶子结点），总是比度为2的结点多1个，如果叶子结点数为n0,度为2的结点数为n2,则n0=n2+1；

具有n个结点的完全二叉树的深度为[log2n]+1;

对于具有n个结点的完全二叉树，如果按照从上至下，从左至右的顺序对二叉树所有结点从1开始顺序编号，则对于任意的序号为i的结点，有1：如果i>1，那么序号为i的结点的双亲结点的序号为i/2；如果i=1，那么序号为i的结点为根节点。2：如果2i<=n，那么序号为i的结点的左孩子结点为2i，如果2i>n，那么序号为i的结点无左孩子。3：如果2i+1<=n,那么序号为i的结点的右孩子结点为2i+1，如果2i+1>n，那么序号为i的结点无右孩子。

注：如果对二叉树的根结点从0开始编号，那么相应的i号结点的双亲结点的编号为(i-1)/2，左孩子的编号为2i+1，右孩子的结点为2i+2；

二叉排序树：又称二叉查找树，二叉查找树。在不为空的前提下，具有如下性质：1如果左子树不为空，那么左子树上所有结点的值均小于它的根结点的值；2如果右子树不为空，那么右子树上所有结点的值均大于根结点的值；3左右子树也分别为二叉排序树。

下面用代码实现如何构建二叉排序树，以及对构建的二叉树进行多种方式的遍历（中序遍历，先序遍历，后序遍历和层序遍历）：

import java.util.LinkedList;
import java.util.Queue;;
 
public class BinaryTree {
 
	private Node root;
 
	public BinaryTree() {
		root = null;
	}
 
	// 将数据data插入到排序二叉树中
	public void insert(int data) {
		Node newNode = new Node(data);
		if (root == null) {
			root = newNode;
		} else {
			Node cur = root;
			Node parent;
			while (true) {
				parent = cur;
				if (data < cur.data) {
					cur = cur.left;
					if (cur == null) {
						parent.left = newNode;
						return;
					}
				} else {
					cur = cur.right;
					if (cur == null) {
						parent.right = newNode;
						return;
					}
				}
			}
		}
	}
 
	// 将数值输入构建二叉树
	public void buildBinaryTree(int[] data) {
		for (int i = 0; i < data.length; i++) {
			insert(data[i]);
		}
	}
 
	/**
	 * 构建二叉树之后，下一个知识点就是对二叉树进行遍历，遍历输出二叉树中的数据 分为中序遍历:顺序为左结点-中间结点-右结点
	 * 先序遍历顺序：中间结点-左结点-右结点 后序遍历顺序为：左结点-右结点-中间结点 其实可以看出，遍历顺序是按照中间结点被遍历的顺序来划分的
	 * 最后还有一种：层序遍历，一层一层的遍历二叉树中的结点数据
	 * 
	 * @param args
	 */
	// 中序遍历，中序遍历的二叉搜索树输出是单调的，即已经排好序的序列
	public void inOrder(Node localRoot) {
		if (localRoot != null) {
			inOrder(localRoot.left);
			System.out.println(localRoot.data + " ");
			inOrder(localRoot.right);
		}
	}
 
	public void inOrder() {
		this.inOrder(this.root);
	}
 
	// 先序遍历
	public void preOrder(Node localRoot) {
		if (localRoot != null) {
			System.out.println(localRoot.data + " ");
			preOrder(localRoot.left);
			preOrder(localRoot.right);
		}
	}
 
	public void preOrder() {
		this.preOrder(this.root);
	}
 
	// 后序遍历
	public void postOrder(Node localRoot) {
		if (localRoot != null) {
			postOrder(localRoot.left);
			postOrder(localRoot.right);
			System.out.println(localRoot.data + " ");
		}
	}
 
	public void postOrder() {
		this.postOrder(this.root);
	}
 
	/**
	 * 二叉树的层序遍历：思想-借助队列的先入先出属性，将根结点放入队列 检查是否有子结点，将子结点依次也放入队列，逐步从队列中取出元素进行打印
	 * 
	 * @param args
	 */
	public void layerOrder() {
		if (this.root == null) {
			return;
		}
		Queue<Node> q = new LinkedList<Node>();
		q.add(this.root);
		while (!q.isEmpty()) {
			Node n = q.poll();
			System.out.println(n.data + " ");
			if (n.left != null) {
				q.add(n.left);
			}
			if (n.right != null) {
				q.add(n.right);
			}
		}
	}
 
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		BinaryTree bTree = new BinaryTree();
		int[] data = { 2, 8, 7, 4, 6, 2, 9, 1, 5 };
		bTree.buildBinaryTree(data);
		System.out.println("中序遍历：");
		bTree.inOrder();
		System.out.println("先序遍历：");
		bTree.preOrder();
		System.out.println("后序遍历：");
		bTree.postOrder();
	}
 
}
 
class Node {
	public int data;
	public Node left;
	public Node right;
 
	public Node(int data) {
		this.data = data;
		this.left = null;
		this.right = null;
	}
}

上面是遍历的递归实现，这里给出一个参考链接，给出的有非递归遍历的实现，使用栈来保存结点。http://blog.csdn.net/lr131425/article/details/60755706

下面再介绍一个二叉树的应用：如何求二叉树中结点的最大距离，思想：首先求左子树距离根结点的最大距离leftMaxDis，之后求右子树距离根结点的最大距离rightMaxDis，二叉树中结点间的最大距离为：leftMaxDis+rightMaxDis。代码实现如下：

private int max(int a, int b) {
		return a > b ? a : b;
	}
 
	public int findMaxDis(Node root) {
		if (root == null) {
			return 0;
		}
		if (root.left == null) {
			root.leftMaxDis = 0;
		}
		if (root.right == null) {
			root.rightMaxDis = 0;
		}
		if (root.left != null) {
			findMaxDis(root.left);
		}
		if (root.right != null) {
			findMaxDis(root.right);
		}
		// 计算左子树距离根结点的距离
		if (root.left != null) {
			root.leftMaxDis = max(root.left.leftMaxDis, root.left.rightMaxDis) + 1;
		}
		// 计算左子树距离根结点的距离
		if (root.right != null) {
			root.rightMaxDis = max(root.right.leftMaxDis, root.right.rightMaxDis) + 1;
		}
		// 获取二叉树所有结点最大距离
		if (root.leftMaxDis + root.rightMaxDis > MaxLen) {
			MaxLen = root.leftMaxDis + root.rightMaxDis;
		}
		return MaxLen;
	}

中序遍历：
1 
2 
2 
4 
5 
6 
7 
8 
9 
先序遍历：
2 
1 
8 
7 
4 
2 
6 
5 
9 
后序遍历：
1 
2 
5 
6 
4 
7 
9 
8 
2 

//最大结点距离
6

// 针对二叉搜索树的查找操作,通过递归实现查找，时间复杂度为O(logn)=O(h)，h为树的高度
	public Node search(Node root, int k) {
		if (root.data == k || root == null) {
			return root;
		}
		if (root.data > k) {
			return search(root.left, k);
		} else {
			return search(root.right, k);
		}
	}
 
	// 下面是使用迭代版本的搜索操作
	public Node searchOfIterative(Node root, int k) {
		while (root != null && k != root.data) {
			if (k < root.data) {
				root = root.left;
			} else {
				root = root.right;
			}
		}
		return root;
	}

// 搜索最大关键字元素和最小关键字元素
	public int MinOfTree(Node root) {
		while (root.left != null) {
			root = root.left;
		}
		return root.data;
	}
 
	public int MaxOfTree(Node root) {
		while (root.right != null) {
			root = root.right;
		}
		return root.data;
	}

public int successor(Node x) {
		// 如果结点x有右子树，则右子树的最小值就是节点x的后继
		if (x.right != null) {
			return MinOfTree(x.right);
		}
		// 如果x没有右子树。则x有以下两种可能：
		// (01) x是"一个左子树"，则"x的后继结点"为 "它的父结点"。
		// (02) x是"一个右子树"，则查找"x的最低的父结点，并且该父结点要具有左孩子"，找到的这个"最低的父结点"就是"x的后继结点"。
		Node y = x.parent;
		while (y != null && x == y.right) {
			x = y;
			y = y.parent;
		}
		return y.data;
	}

// 删除树中的结点z
	public void delete(BinaryTree T, Node z) {
		if (z.left == null) {
			transplant(T, z, z.right);
		} else if (z.right == null) {
			transplant(T, z, z.left);
		} else {
			Node y = MinOfTree(z.right);
			if (y.parent != z) {
				transplant(T, y, y.right);
				y.right = z.right;
				y.right.parent = y;
			}
			transplant(T, z, y);
			y.left = z.left;
			y.left.parent = y;
		}
	}
	//重新布局二叉树
	public void transplant(BinaryTree T, Node u, Node v) {
		if (u.parent == null) {
			T.root = v;
		} else if (u == u.parent.left) {
			u.parent.left = v;
		} else {
			u.parent.right = v;
		}
		if (v != null) {
			v.parent = u.parent;
		}
	}