=======================树========================
特点： 1.由n个节点组成的有限集合。每个节点的前驱节点和后继节点都可能不止一个。 2.非空的树有且只有一个根节点。 3.除根节点外，其余节点可分为若干个互不相交的子集。每个子集本身又构成一棵树，称为根的子树。 4.一个节点拥有的子树的数量称为该节点的度。所有节点的最大度数称为树的度。节点总数 = 度的总数 + 1。 5.度数为0的节点称为叶节点。 6.节点处于树当中的位置，称为层。根节点的层数为0，其他节点的层数在父节点的层数上加1。 7.同一节点的孩子，称为兄弟节点。同一层次的，不同父节点的节点，称为堂兄弟。 8.从根到任意节点存在唯一的路径，路径的长度描述了树节点层数。 9.树的根节点到树的叶节点的最长路径的长度，称树的高或树的深。 10.如果树的各节点的子树从左到右是有序的，称为有序树。度数为m的有序树。称为m叉树。 =======================二叉树=====================特点： 1.每个节点的度数均不超过2 2.有序树 3.节点的子树有左右之分 4.在第i层上，最多有2的i次方个节点。 5.叶节点数n0,度数为2的节点数n2，则n0=n2+1 6.高度为h的二叉树最多有2的(h+1)次方减1个节点 满二叉树：每层的节点都达到了最大值完全二叉树：满二叉树的最下层从右到左连续删除若干个子节点形成的二叉树存储结构：顺序存储和链式存储1.顺序存储： 1.只适合满二叉树和完全二叉树 2.用序号随机访问二叉树中的节点 3.存储位置： 如果把完全二叉树的第i个节点存储在数组的第i个元素中。那么，它的父节点存储在i/2个位置，左子节点存储在2i个位置，右子节点存储在2i+1个位置。 如果i是奇数，i/2取整，这里不能四舍五入。 2.链式存储（二叉链表）： 1.非满二叉树，也不是完全二叉树。描述数据元素之间关系不是存储地址的相对位置而是指针 2.数据域（数据元素）、左孩子域（左指针）、右孩子域（右指针） 范例：1.节点类 - TreeNode1 /** 2 * @Description: 树的节点 3 * @author Ivy 4 */ 5 public class TreeNode { 6 7 private Object nodeValue; 8 private TreeNode left, right; 9 10 public TreeNode() {11 this(null, null, null);12 }13 14 public TreeNode(Object item, TreeNode left, TreeNode right) {15 this.nodeValue = item;16 this.left = left;17 this.right = right;18 }19 20 public TreeNode(Object item) {21 this(item,null,null);22 }23 24 /**25 * @Description: 判断当前节点是否是叶节点26 * @return27 */28 public boolean isLeaf(){29 if (this.left == null && this.right == null) {30 return true;31 } else {32 return false;33 }34 }35 36 public String toString(){37 if (nodeValue == null) {38 return null;39 }40 String result = "(节点" + nodeValue.toString();41 if (left != null) {42 result += "左子树：" + left.toString();43 }44 if (right != null) {45 result += "右子树：" + right.toString();46 }47 result += ")";48 return result;49 }50 51 } 1 /** 2 * @Description: 实现二叉树 3 * @author Ivy 4 */ 5 public class BinaryTree { 6 7 protected TreeNode root; 8 9 public BinaryTree() {10 root = null;11 }12 13 public BinaryTree(TreeNode root) {14 this.root = root;15 }16 17 public boolean isEmpty() {18 return this.root == null;19 }20 21 public TreeNode getRoot() {22 return this.root;23 }24 25 public String toString() {26 return this.root.toString();27 }28 } 1 /** 2 * @Description: 构造二叉树 3 * @author Ivy 4 */ 5 public class BuildTree { 6 7 /** 8 * a 9 * / \10 * b c11 * / \12 * d e13 * / \14 * f g 15 */16 17 public static BinaryTree create() {18 TreeNode a,b,c,d,e,f,g;19 f = new TreeNode("F");20 g = new TreeNode("G");21 d = new TreeNode("D");22 e = new TreeNode("E",f,g);23 b = new TreeNode("B",d,e);24 c = new TreeNode("C");25 a = new TreeNode("A",b,c);26 return new BinaryTree(a);27 28 }29 }