二叉树概念总结
1、二叉树的递归定义
二叉树(Binary Tree)是个有限元素的集合，该集合或者为空、或者由一个称为根(root)的元素及两个不相交的、被分别称为左子树和右子树的二叉树组成。
当集合为空时，称该二叉树为空二叉树。在二叉树中，一个元素也称作一个结点。二叉树是有序的，即若将其左、右子树颠倒，就成为另一棵不同的二叉树。即使树中结点只有一棵子树，也要区分它是左子树还是右子树。(二叉树有五种形态)
2、二叉树的相关概念
(1)结点的度。结点所拥有的子树的个数称为该结点的度。
(2)叶结点。度为0 的结点称为叶结点，或者称为终端结点。
(3)分枝结点。度不为0 的结点称为分支结点，或者称为非终端结点。
(4)左孩子、右孩子、双亲。树中一个结点的子树的根结点称为这个结点的孩子。这个结点称为它孩子结点的双亲。具有同一个双亲的孩子结点互称为兄弟。
(5)路径、路径长度。如果一棵树的一串结点n1,n2,…,nk有如下关系：结点ni是ni+1的父结点(1≤i<k),就把n1,n2,…,nk称为一条由n1至nk的路径。这条路径的长度是k-1。
(6)祖先、子孙。在树中，如果有一条路径从结点M 到结点N，那么M 就称为N的祖先，而N 称为M 的孙。
(7)结点的层数。规定树的根结点的层数为1，其余结点的层数等于它的双亲结点的层数加1。
(8)树的深度。树中所有结点的最大层数称为树的深度。
(9)树的度。树中各结点度的最大值称为该树的度。
3、二叉树的主要性质
性质1： 在二叉树的第i层上至多有2的i-1次方个结点(i>=1)。
性质2： 深度为k的二叉树至多有2的k次方减1个结点(k>=1)。
性质3： 对任何一棵二叉树T，如果其终端结点数为n0,度为2的结点数为n2,则n0=n2+1。
性质4： 具有n个结点的完全二叉树的深度为|log2n|+1
性质5： 如果对一棵有n个结点的完全二叉树的结点按层序编号，则对任一结点i(1≤i≤n)有：
(1) 如果i=1,则结点i是二叉树的根,无双亲;如果i>1,则双亲PARENT(i)是结点i/2
(2) 如果2i>n,则结点i无左孩子(结点i为叶子结点);否则其左孩子LCHILD(i)是结点2i
(3) 如果2i+1>n,则结点i无右孩子;否则其右孩子RCHILD(i)是结点2i+1
图片来源： http://sunlei.blog.51cto.com/525111/111063
二叉树实现
import java.util.Queue;
import java.util.Vector;
import java.util.concurrent.ConcurrentLinkedQueue;
class BinaryTreeNode {
int data;
BinaryTreeNode leftchild;
BinaryTreeNode rightchild;
BinaryTreeNode(int t) {
this.data = t;
this.leftchild = null;
this.rightchild = null;
}
BinaryTreeNode(int t, BinaryTreeNode leftchild, BinaryTreeNode rightchild) {
this.data = t;
this.leftchild = leftchild;
this.rightchild = rightchild;
}
}
public class BinaryTree {
BinaryTreeNode root = null;
public BinaryTree(int[] t) {
creatBinaryTree(t);
}
/* 拷贝构造函数 */
public BinaryTree(BinaryTree otherTree) {
if (otherTree.root == null)
this.root = null;
else{
this.root=copy(otherTree.root);
//this.root=otherTree.root;
}
}
private BinaryTreeNode creatBinaryTree(int[] t) {
int length = t.length;
if (root == null) {
root = new BinaryTreeNode(t[0]);
}
for (int i = 1; i < length; i++) {
creat(root, t[i]);
}
return root;
}
// 构造二叉树
private void creat(BinaryTreeNode root, int t) {
if (t >= root.data) {
if (root.rightchild == null) {
root.rightchild = new BinaryTreeNode(t);
} else {
creat(root.rightchild, t);
}
} else {
if (root.leftchild == null) {
root.leftchild = new BinaryTreeNode(t);
} else {
creat(root.leftchild, t);
}
}
}
/* 遍历二叉树 前中后*/
public void inIterator(BinaryTreeNode b) {
if (b != null) {
inIterator(b.leftchild);
System.out.print(b.data + ",");
inIterator(b.rightchild);
}
}
public void levelOrderDisplay(BinaryTreeNode b){
ConcurrentLinkedQueue<BinaryTreeNode> q = new ConcurrentLinkedQueue<BinaryTreeNode>();//创建链式队列对象
if(b == null)return;
BinaryTreeNode curr;
q.add(b); //根结点入队列
while(!q.isEmpty()){ //当队列非空时循环
curr = (BinaryTreeNode)q.remove(); //出队列
System.out.println(curr.data); //访问该结点
if(curr.leftchild != null)
q.add(curr.leftchild); //左孩子结点入队列
if(curr.rightchild != null)
q.add(curr.rightchild);//右孩子结点入队列
}
}
/* 树的高度 */
public int treeHeight(BinaryTreeNode b) {
if (b == null)
return -1;
else
return (treeHeight(b.leftchild) >= treeHeight(b.rightchild) ? treeHeight(b.leftchild)
: treeHeight(b.rightchild)) + 1;
}
/* 求总节点数 */
public int treeNodes(BinaryTreeNode b) {
if (b == null)
return 0;
else if (b.leftchild == null && b.rightchild == null)
return 1;
else
return 1 + treeNodes(b.rightchild) + treeNodes(b.leftchild);
}
/* 求叶节点数 */
public int treeLeavesNode(BinaryTreeNode b) {
if (b == null)
return 0;
else if (b.leftchild == null && b.rightchild == null)
return 1;
else
return treeLeavesNode(b.rightchild) + treeLeavesNode(b.leftchild);
}
/* 复制树 */
public BinaryTreeNode copy(BinaryTreeNode b) {
BinaryTreeNode newNode;
if (b == null)
return null;
newNode=new BinaryTreeNode(b.data);
newNode.leftchild = copy(b.leftchild);
newNode.rightchild = copy(b.rightchild);
//newNode = new BinaryTreeNode(b.data, newLeftChild, newRightChild);
return newNode;
}
/*删除树*/
public void delete(){
deleteTree(this.root);
System.out.println(this.root.rightchild.rightchild.rightchild==null);
}
public void deleteTree(BinaryTreeNode b){
if(b!=null){
deleteTree(b.leftchild);
deleteTree(b.rightchild);
b=null;
}
}
/* 查找一个节点 */
public boolean findNode(BinaryTreeNode b,int key){
if(b==null)return false;
if(b.data==key)return true;
if(key>b.data)return findNode(b.rightchild,key);
return findNode(b.leftchild,key);
}
public void insertNode(BinaryTreeNode b,int t){
creat(b,t);
}
public static void main(String[] args) {
int[] data = { 12, 11, 34, 45, 67, 38, 56, 43, 22, 8};
System.out.println(data.length);
BinaryTree btree = new BinaryTree(data);
BinaryTreeNode r = btree.root;
btree.inIterator(r);
System.out.println();
System.out.println("Height:" + btree.treeHeight(r));
System.out.println("Nodes:" + btree.treeNodes(r));
System.out.println("Leaves:" + btree.treeLeavesNode(r));
BinaryTree copyTree=new BinaryTree(btree);
System.out.println("copyTree:");
copyTree.insertNode(copyTree.root, 57);
System.out.println("Height:" + copyTree.treeHeight(copyTree.root));
System.out.println("Nodes:" + copyTree.treeNodes(copyTree.root));
System.out.println("Leaves:" + copyTree.treeLeavesNode(copyTree.root));
System.out.println("Btree Height:" + btree.treeHeight(r));
System.out.println("Nodes:" + btree.treeNodes(r));
System.out.println("Leaves:" + btree.treeLeavesNode(r));
System.out.println(copyTree.findNode(copyTree.root, 8));
copyTree.inIterator(copyTree.root);
/* copyTree.delete();
System.out.println(copyTree.root==null);
System.out.println("deleteTree:");
System.out.println("Height:" + copyTree.treeHeight(copyTree.root));
System.out.println("Nodes:" + copyTree.treeNodes(copyTree.root));*/
System.out.println("LevelOrder:");
copyTree.levelOrderDisplay(copyTree.root);
}
}
