722
数据结构之二叉树
一 树、二叉树和二叉查找树
1。树的概念：
递归定义：
1） 一个空结构是一个空树
2）如果t1,...,tk是分离的树，那么以t1,...,tk的根为子节点的根结构也是树
3）只有按照1，2规则产生的结构才是树
树的概念更多用于分层结构，比如数据库管理系统的分层模型。
2。二叉树（binary tree）：所有节点都有两个子节点（可以为空），并且每个子节点都指明为左子节点还是右子节点
1）完全二叉数，满足第i层，有2的i-1次方个子节点此条件的二叉树
2）对于所有非空二叉树，如果它的中间子节点恰好有两个非空子女，那么叶的数目m大于中间节点的数目k，并且m=k+1
3。二叉查找树（binary search tree)
1）概念：对于树中的每个节点n，其左子节点中保存的所有数值都小于n保存的数值，右子节点保存的数值都大于n保存的数值。
2）二叉查找树可以实现更为优越的查找性能，主要实现方式有数组和链表结构，相比较而言，链表实现更为容易，因为数组实现删除和添加功能需要移动数组元素（如填补删除空位等）
二。二叉树的实现
首先设计一个节点（设计一个整型的二叉树，通用型通理）：
此类简单明了，一个信息值，两个引用（左右子树）。
public class IntBSTNode 
{
protected int key; protected IntBSTNode left, right;
public IntBSTNode() { left = right = null ;
} public IntBSTNode( int el) { this (el, null , null ); } public IntBSTNode( int el, IntBSTNode left, IntBSTNode right) { key = el; left = left; right = right; } 
} 
由此类而实现一个完整二叉搜索树：
public class IntBST { protected IntBSTNode root; protected void visit(IntBSTNode p) { System.out.print(p.key + " " ); } public IntBST() { root = null ; }
第一步，实现二叉树的搜索，查找过程简单明了，对每一个节点将要查找的键与当前节点的数值比较，如果键小于该数，就进入节点的左子树继续比较，反之进入右子树继续此比较过程。
public IntBSTNode search( int el) { return search(root, el); } protected IntBSTNode search(IntBSTNode p, int el) { while (p != null ) if (el == p.key) return p; else if (el < p.key) p = p.left; else p = p.right; return null ; }
此查找过程最坏情况，树成为链表O(n)=(n-1)/2，最好情况：O(n)=lg(n+1)-2。经过计算可知，一般树的平均比较次数更接近于最好情况。
第二步，实现二叉树的遍历，树的遍历就是访问树的所有节点，且每个节点被访问一次。N个节点的树有N！种不同的遍历。我们只考虑两种情况的遍历
1）广度优先遍历，是从最底层（或最高层）开始逐层向上（或向下），而在同层自左向右（或者相反）访问每一个子节点，因此共有四种情况。考虑自顶向下，自左向右的情况，利用队列实现如下：
public void breadthFirst() { IntBSTNode p = root; Queue queue = new Queue(); if (p != null ) { queue.enqueue(p); while ( ! queue.isEmpty()) { p = (IntBSTNode) queue.dequeue(); visit(p); if (p.left != null ) queue.enqueue(p.left); if (p.right != null ) queue.enqueue(p.right); } } }
2） 深度优先遍历，此种遍历关心3个任务：
V——访问一个节点
L——遍历左子树
R——遍历右子树
因此有3！=6种此类遍历，我们关心其中3种：
VLR——先序遍历树
LVR——中序遍历树
LRV——后序遍历树
如果用递归来实现这3种遍历非常容易理解，如下：
public void preorder() { preorder(root); } // 先序 protected void preorder(IntBSTNode p) { if (p != null ) { visit(p); preorder(p.left); preorder(p.right); } } public void inorder() { inorder(root); } // 中序 protected void inorder(IntBSTNode p) { if (p != null ) { inorder(p.left); visit(p); inorder(p.right); } } public void postorder() { postorder(root); } // 后序 protected void postorder(IntBSTNode p) { if (p != null ) { postorder(p.left); postorder(p.right); visit(p); } }
同样，我们知道，递归调用总可以被迭代方式取代，只不过不是这么容易理解了，在此不再列出。
public void insert(int el) { IntBSTNode p = root, prev = null; while (p != null) { // find a place for inserting new node; prev = p; if (p.key < el) p = p.right; else p = p.left; } if (root == null) // tree is empty; root = new IntBSTNode(el); else if (prev.key < el) prev.right = new IntBSTNode(el); else prev.left = new IntBSTNode(el); }
第四步。节点的删除。
1）归并删除法，当被删除节点没有或者只有一个子树的时候很简单，当有两个子树存在的时候，情况稍微复杂。归并删除法就是将节点的两棵子树合并成一棵树，然后连接到节点的父节点上。归并子树的原则，寻找左子树中key最大的节点，并将其作为右子树的父节点。相反，也可以寻找右子树的key最小的节点，作为左子树的父节点。我们以第一种情况为例：
public void deleteByMerging(int el) { IntBSTNode tmp, node, p = root, prev = null; while (p != null && p.key != el) { // find the node p prev = p; // with element el; if (p.key < el) p = p.right; else p = p.left; } node = p; if (p != null && p.key == el) { if (node.right == null) // node has no right child: its left node = node.left; // child (if any) is attached to its parent; else if (node.left == null) // node has no left child: its right node = node.right; // child is attached to its parent; else { // be ready for merging subtrees; tmp = node.left; // 1. move left while (tmp.right != null) // 2. and then right as far as tmp = tmp.right; // possible; tmp.right = // 3. establish the link between the node.right; // the rightmost node of the left // subtree and the right subtree; node = node.left; // 4. } if (p == root) root = node; else if (prev.left == p) prev.left = node; else prev.right = node; } else if (root != null) System.out.println("key " + el + " is not in the tree"); else System.out.println("the tree is empty"); }
2）复制删除法：归并删除法带来的问题是可能改变树的高度。另一种删除法也就是复制删除法，将待删除节点的key用它的前驱节点的key来代替，某一节点的前驱节点就是该节点左子树中key最大的节点。如下实现：
public void deleteByCopying(int el) { IntBSTNode node, p = root, prev = null; while (p != null && p.key != el) { // find the node p prev = p; // with element el; if (p.key < el) p = p.right; else p = p.left; } node = p; if (p != null && p.key == el) { if (node.right == null) // node has no right child; node = node.left; else if (node.left == null) // no left child for node; node = node.right; else { IntBSTNode tmp = node.left; // node has both children; IntBSTNode previous = node; // 1. while (tmp.right != null) { // 2. find the rightmost previous = tmp; // position in the tmp = tmp.right; // left subtree of node; } node.key = tmp.key; // 3. overwrite the reference if (previous == node) // of the key being deleted; previous.left = tmp.left; // 4. else previous.right = tmp.left; // 5. } if (p == root) root = node; else if (prev.left == p) prev.left = node; else prev.right = node; } else if (root != null) System.out.println("key " + el + " is not in the tree"); else System.out.println("the tree is empty"); }
4。树的平衡：如果树中任何节点的两个子树的高度差或者是0或者为1，那么这样的二叉树就是高度平衡的。如何平衡一棵树？
1）简单算法：将树中的所有数据中序遍历，放进一个数组，此数组已经排序，然后折半插入
public void balance(int data[], int first, int last) { if (first <= last) { int middle = (first + last) / 2; System.out.print(data[middle] + " "); insert(data[middle]); balance(data, first, middle - 1); balance(data, middle + 1, last); } }
文章转自庄周梦蝶 ，原文发布时间5.17
2）DSW算法：
基本原理是通过树的右旋转得到树的主干，然后再进行左旋转得到平衡树
最后更新：2017-05-17 11:35:36