数据结构之二叉树.docx

/wing011203/archive/2013/04/12/3016409.html数据结构之二叉树　第一篇：/wing011203/archive/2013/04/09/3010985.html数据结构之链表　第二篇：/wing011203/archive/2013/04/11/3014199.html数据结构之栈和队列?　在这篇文章里面，我们主要探讨和树相关的话题。　首先，我们来对树进行定义：树是n（n= 0）个节点的有限集。在任何一个非空树中：（1）有且仅有一个特定的称为“根”的节点；（2）当n1时，其余节点可分为m（m0）个互相相关的有限集T1、T2、T3……，其中每一个集合本身又是一棵树，并且称为根的子树。　对于我们这篇文章里讨论的二叉树，它是一种特殊的树形结构，每个节点至多只有两颗子树，并且子树有左右之分，其次序不能随意颠倒。　接下来，我们使用java代码来定义一棵树： 1 public class BinNode { 2 private int m_Value; 3 private BinNode m_Left; 4 private BinNode m_Right; 5 public void setValue(int m_Value) { 6 this.m_Value = m_Value; 7 } 8 public int getValue() { 9 return m_Value;10 }11 public void setLeft(BinNode m_Left) {12 this.m_Left = m_Left;13 }14 public BinNode getLeft() {15 return m_Left;16 }17 public void setRight(BinNode m_Right) {18 this.m_Right = m_Right;19 }20 public BinNode getRight() {21 return m_Right;22 }23 24 public boolean isLeaf()25 {26 return m_Left == null m_Right == null;27 }28 }　下面，开始讨论和二叉树相关的话题构造二叉树，给出一个已排序的整型数组，如何根据它来构造一个BST（二叉有哪些信誉好的足球投注网站树）。思路：二叉有哪些信誉好的足球投注网站树的特点是左子树的值=父节点的值=右子树的值。我们可以从下标0开始遍历数组，然后依次创建树节点，这样下来，对于树的根节点来说，只有右子树，没有左子树，整个树不是平衡二叉树。为了优化这一点，我们可以将数组的中间元素作为根节点，前半部分的值作为树的左子树，后半部分的值作为树的右子树，然后使用递归依次构建。 1 public static BinNode buildTree(int[] arrValue) 2 { 3 if(arrValue == null) return null; 4 BinNode root = new BinNode(); 5 buildTree(arrValue, 0, arrValue.length - 1, root); 6 return root; 7 } 8 9 private static void buildTree(int[] arrValue, int startPos, int endPos, BinNode tree)10 {11 if (startPos endPos) return;12 13 int midPos = startPos + (endPos - startPos)/2;14 if (tree == null)15 {16 tree = new BinNode();17 }18 tree.setValue(arrValue[midPos]);19 20 if (midPos - 1 = startPos)21 {22 BinNode left = new BinNode();23 tree.setLeft(left);24 buildTree(arrValue, startPos, midPos - 1, left);25 }26 if (endPos = midPos + 1)27 {28 BinNode right = new BinNode();29 tree.setRight(right);30 buildTree(arrValue, midPos + 1, endPos, right);31 }32 }树的遍历（前序遍历、中序遍历、后序遍历、层次遍历）思路：可以采用递归或者非递归的方式进行遍历前序遍历 1 public static void preOrder(BinNode tree)