java实现二叉树的遍历

sara596286 贡献于2011-08-13

作者 ddht123  创建于2010-11-20 09:23:00   修改者ddht123  修改于2010-11-20 09:28:00字数30329

文档摘要:
关键词:

一、数据结构分类 (一)按逻辑结构 1. 集合(无辑关系) 2. 线性结构(线性表):数组、链表、栈、队列 3. 非线性结构:树、图、多维数组 (二)按存储结构 顺序(数组)储结构、链式储结构、索引储结构、散列储结构 二、二叉树相关性质 · 结点的度:一个结点的子树的个数记为该结点的度. · 树的度:所有节点中度数最大的结节的度数,叶子节点的度为零。 · 树的高度:一棵树的最大层次数记为树的高度(或深度)。 · 有序(无序)树:若将树中结点的各子树看成是从左到右具有次序的,即不能交换,则称该树为有序树。否则称为无序树。 · 二叉树第i层(i≥1)上至多有2^(i-1)个节点。 · 深度为k的二叉树至多有2^k-1个节点(k≥1)。 · 对任何一棵二叉,若叶子节点数为n0,度为2的节点数为n2,则n0=n2+1。 · 具有n个节点的完全二叉树的深度为 (㏒2^n)(向下取整)+1。 · 对一棵有n个节点的完全二叉树的节点按层次从上到下,自左至右进行编号,则对任一节点i(1≤i≤n)有:若 i=1,则节点i是二叉树的根,无双亲;若 i>1,则其双亲为 i/2(向下取整)。若2i>n,则节点i没有孩子节点,否则其左孩子为2i。若2i+1>n,则节点i没有右孩子,否则其右孩子为2i+1。 · 若深度为k的二叉树有2^k-1个节点,则称其为满二叉树。满二叉树是一棵完全二叉树。 · 对于完全二叉树中,度为1的节点个数只可能为1个或0个。 · 对于二叉树,如果叶子节点数为n0,度为1的节点数为n1,度为2的节点数为n2,则节点总数n = n0 + n1 + n2。 · 对于任意树,总节点数 = 每个节点度数和 + 1 · 二叉树的高度等于根与最远叶节点(具有最多祖先的节点)之间分支数目。空树的高度是-1。只有单个元素的二叉树,其高度为0。 . 三、二叉树的遍历 遍历是按某种策略访问树中的每个节点,且仅访问一次。 (一) 二叉树结构实现 Java代码    1. package tree.bintree; 2. /**   3.  * 创建 非完全二叉树、完全二叉树、满二叉树   4.  *   5.  * 由于二叉树的节点增加没有什么规则,所以这里只是简单的使用了递一   6.  * 次性把整棵树创建出来,而没有设计出一个一个添加节点的方法与删除   7.  *    8.  * @author jzj   9.  * @date 2009-12-23   10.  */   11. public class BinTree {// Bin=Binary(二进位的, 二元的)    12.    13.     protected Entry root;//根    14.     private int size;//树的节点数    15.    16.     /**   17.      * 树的节点结构   18.      * @author jzj   19.      * @date 2009-12-23   20.      */   21.     protected static class Entry {    22.         int elem;//数据域,这里我们作为编号    23.         Entry left;//左子树    24.         Entry right;//右子树    25.    26.         public Entry(int elem) {    27.             this.elem = elem;    28.         }    29.    30.         public String toString() {    31.             return " number=" + elem;    32.         }    33.     }    34.    35.     /**   36.      * 根据给定的节点数创建一个完全二叉树或是满二叉树   37.      * @param nodeCount 要创建节点总数   38.      */   39.     public void createFullBiTree(int nodeCount) {    40.         root = recurCreateFullBiTree(1, nodeCount);    41.     }    42.    43.     /**   44.      * 递归创建完全二叉树   45.      * @param num 节点编号   46.      * @param nodeCount 节点总数   47.      * @return TreeNode 返回创建的节点   48.      */   49.     private Entry recurCreateFullBiTree(int num, int nodeCount) {    50.         size++;    51.         Entry rootNode = new Entry(num);//根节点    52.         //如果有左子树则创建左子树    53.         if (num * 2 <= nodeCount) {    54.             rootNode.left = recurCreateFullBiTree(num * 2, nodeCount);    55.             //如果还可以创建右子树,则创建    56.             if (num * 2 + 1 <= nodeCount) {    57.                 rootNode.right = recurCreateFullBiTree(num * 2 + 1, nodeCount);    58.             }    59.         }    60.         return (Entry) rootNode;    61.     }    62.    63.     /**   64.      * 根据给定的数组创建一棵树,这个棵树可以是完全二叉树也可是普通二叉树   65.      * 数组中为0的表示不创建该位置上的节点   66.      * @param nums 数组中指定了要创建的节点的编号,如果为0,表示不创建   67.      */   68.     public void createBinTree(int[] nums) {    69.         root = recurCreateBinTree(nums, 0);    70.     }    71.    72.     /**   73.      * 递归创建二叉树   74.      * @param nums 数组中指定了要创建的节点的编号,如果为0,表示不创建   75.      * @param index 需要使用数组中的哪个元素创建节点,如果为元素为0,则不创建   76.      * @return TreeNode 返回创建的节点,最终会返回树的根节点   77.      */   78.     private Entry recurCreateBinTree(int[] nums, int index) {    79.         //指定索引上的编号不为零上才需创建节点    80.         if (nums[index] != 0) {    81.             size++;    82.             Entry rootNode = new Entry(nums[index]);//根节点    83.             //如果有左子树则创建左子树    84.             if ((index + 1) * 2 <= nums.length) {    85.                 rootNode.left = (Entry) recurCreateBinTree(nums, (index + 1) * 2 - 1);    86.                 //如果还可以创建右子树,则创建    87.                 if ((index + 1) * 2 + 1 <= nums.length) {    88.                     rootNode.right = (Entry) recurCreateBinTree(nums, (index + 1) * 2);    89.                 }    90.             }    91.             return (Entry) rootNode;    92.         }    93.         return null;    94.    95.     }    96.    97.     public int size() {    98.         return size;    99.     }    100.    101.     //取树的最左边的节点    102.     public int getLast() {    103.         Entry e = root;    104.         while (e.right != null) {    105.             e = e.right;    106.         }    107.         return e.elem;    108.     }    109.    110.     //测试    111.     public static void main(String[] args) {    112.    113.         //创建一个满二叉树    114.         BinTree binTree = new BinTree();    115.         binTree.createFullBiTree(15);    116.         System.out.println(binTree.size());//15    117.         System.out.println(binTree.getLast());//15    118.    119.         //创建一个完全二叉树    120.         binTree = new BinTree();    121.         binTree.createFullBiTree(14);    122.         System.out.println(binTree.size());//14    123.         System.out.println(binTree.getLast());//7    124.    125.         //创建一棵非完全二叉树    126.         binTree = new BinTree();    127.         int[] nums = new int[] { 1, 2, 3, 4, 0, 0, 5, 0, 6, 0, 0, 0, 0, 7, 8 };    128.         binTree.createBinTree(nums);    129.         System.out.println(binTree.size());//8    130.         System.out.println(binTree.getLast());//8    131.    132.     }    133. }    package tree.bintree; /** * 创建 非完全二叉树、完全二叉树、满二叉树 * * 由于二叉树的节点增加没有什么规则,所以这里只是简单的使用了递一 * 次性把整棵树创建出来,而没有设计出一个一个添加节点的方法与删除 * * @author jzj * @date 2009-12-23 */ public class BinTree {// Bin=Binary(二进位的, 二元的) protected Entry root;//根 private int size;//树的节点数 /** * 树的节点结构 * @author jzj * @date 2009-12-23 */ protected static class Entry { int elem;//数据域,这里我们作为编号 Entry left;//左子树 Entry right;//右子树 public Entry(int elem) { this.elem = elem; } public String toString() { return " number=" + elem; } } /** * 根据给定的节点数创建一个完全二叉树或是满二叉树 * @param nodeCount 要创建节点总数 */ public void createFullBiTree(int nodeCount) { root = recurCreateFullBiTree(1, nodeCount); } /** * 递归创建完全二叉树 * @param num 节点编号 * @param nodeCount 节点总数 * @return TreeNode 返回创建的节点 */ private Entry recurCreateFullBiTree(int num, int nodeCount) { size++; Entry rootNode = new Entry(num);//根节点 //如果有左子树则创建左子树 if (num * 2 <= nodeCount) { rootNode.left = recurCreateFullBiTree(num * 2, nodeCount); //如果还可以创建右子树,则创建 if (num * 2 + 1 <= nodeCount) { rootNode.right = recurCreateFullBiTree(num * 2 + 1, nodeCount); } } return (Entry) rootNode; } /** * 根据给定的数组创建一棵树,这个棵树可以是完全二叉树也可是普通二叉树 * 数组中为0的表示不创建该位置上的节点 * @param nums 数组中指定了要创建的节点的编号,如果为0,表示不创建 */ public void createBinTree(int[] nums) { root = recurCreateBinTree(nums, 0); } /** * 递归创建二叉树 * @param nums 数组中指定了要创建的节点的编号,如果为0,表示不创建 * @param index 需要使用数组中的哪个元素创建节点,如果为元素为0,则不创建 * @return TreeNode 返回创建的节点,最终会返回树的根节点 */ private Entry recurCreateBinTree(int[] nums, int index) { //指定索引上的编号不为零上才需创建节点 if (nums[index] != 0) { size++; Entry rootNode = new Entry(nums[index]);//根节点 //如果有左子树则创建左子树 if ((index + 1) * 2 <= nums.length) { rootNode.left = (Entry) recurCreateBinTree(nums, (index + 1) * 2 - 1); //如果还可以创建右子树,则创建 if ((index + 1) * 2 + 1 <= nums.length) { rootNode.right = (Entry) recurCreateBinTree(nums, (index + 1) * 2); } } return (Entry) rootNode; } return null; } public int size() { return size; } //取树的最左边的节点 public int getLast() { Entry e = root; while (e.right != null) { e = e.right; } return e.elem; } //测试 public static void main(String[] args) { //创建一个满二叉树 BinTree binTree = new BinTree(); binTree.createFullBiTree(15); System.out.println(binTree.size());//15 System.out.println(binTree.getLast());//15 //创建一个完全二叉树 binTree = new BinTree(); binTree.createFullBiTree(14); System.out.println(binTree.size());//14 System.out.println(binTree.getLast());//7 //创建一棵非完全二叉树 binTree = new BinTree(); int[] nums = new int[] { 1, 2, 3, 4, 0, 0, 5, 0, 6, 0, 0, 0, 0, 7, 8 }; binTree.createBinTree(nums); System.out.println(binTree.size());//8 System.out.println(binTree.getLast());//8 } }  (二)利用二叉树本身特点进行递归遍历(属内部遍历) 由于二叉树所具有的递归性质,一棵非空的二叉树可以看作是由根节点、左子树和右子树3部分构成,因为若能依次遍历这3部分的信息,也就遍历了整个二叉树。按照左子树的遍历在右子树的遍历之前进行的约定,根据访问根节点位置的不同,可以得到二叉的前序、中序、后序3种遍历方法。 Java代码 1. package tree.bintree;    2.    3. /**   4.  * 二叉树的三种 内部 遍历:前序、中序、后序   5.  * 但不管是哪种方式,左子树的遍历在右子树的遍历之前遍历是这有三种遍历方式都   6.  * 必须遵循的约定   7.  * @author jzj   8.  * @date 2009-12-23   9.  */   10. public class BinTreeInOrder extends BinTree {    11.    12.     /**   13.      * 节点访问者,可根据需要重写visit方法   14.      */   15.     static abstract class Visitor {    16.         void visit(Object ele) {    17.             System.out.print(ele + " ");    18.         }    19.     }    20.    21.     public void preOrder(Visitor v) {    22.         preOrder(v, root);    23.     }    24.    25.     /**   26.      * 树的前序递归遍历 pre=prefix(前缀)   27.      * @param node 要遍历的节点   28.      */   29.     private void preOrder(Visitor v, Entry node) {    30.         //如果传进来的节点不为空,则遍历,注,叶子节点的子节点为null    31.         if (node != null) {    32.             v.visit(node.elem);//先遍历父节点    33.             preOrder(v, node.left);//再遍历左节点    34.             preOrder(v, node.right);//最后遍历右节点    35.         }    36.     }    37.    38.     public void inOrder(Visitor v) {    39.         inOrder(v, root);    40.     }    41.    42.     /**   43.      * 树的中序递归遍历 in=infix(中缀)   44.      * @param node 要遍历的节点   45.      */   46.     private void inOrder(Visitor v, Entry node) {    47.         //如果传进来的节点不为空,则遍历,注,叶子节点的子节点为null    48.         if (node != null) {    49.             inOrder(v, node.left);//先遍历左节点    50.             v.visit(node.elem);//再遍历父节点    51.             inOrder(v, node.right);//最后遍历右节点    52.         }    53.     }    54.    55.     public void postOrder(Visitor v) {    56.         postOrder(v, root);    57.     }    58.    59.     /**   60.      * 树的后序递归遍历 post=postfix(后缀)   61.      * @param node 要遍历的节点   62.      */   63.     private void postOrder(Visitor v, Entry node) {    64.         //如果传进来的节点不为空,则遍历,注,叶子节点的子节点为null    65.         if (node != null) {    66.             postOrder(v, node.left);//先遍历左节点    67.             postOrder(v, node.right);//再遍历右节点    68.             v.visit(node.elem);//最后遍历父节点    69.         }    70.     }    71.    72.     //测试    73.     public static void main(String[] args) {    74.    75.         //创建二叉树    76.         int[] nums = new int[] { 1, 2, 3, 4, 0, 0, 5, 0, 6, 0, 0, 0, 0, 7, 8 };    77.         BinTreeInOrder treeOrder = new BinTreeInOrder();    78.         treeOrder.createBinTree(nums);    79.         System.out.print("前序遍历 - ");    80.         treeOrder.preOrder(new Visitor() {    81.         });    82.         System.out.println();    83.         System.out.print("中序遍历 - ");    84.         treeOrder.inOrder(new Visitor() {    85.         });    86.         System.out.println();    87.         System.out.print("后序遍历 - ");    88.         treeOrder.postOrder(new Visitor() {    89.         });    90.         /*   91.          * output:   92.          * 前序遍历 - 1 2 4 6 3 5 7 8    93.          * 中序遍历 - 4 6 2 1 3 7 5 8    94.          * 后序遍历 - 6 4 2 7 8 5 3 1    95.          */   96.     }    97. }    package tree.bintree; /** * 二叉树的三种 内部 遍历:前序、中序、后序 * 但不管是哪种方式,左子树的遍历在右子树的遍历之前遍历是这有三种遍历方式都 * 必须遵循的约定 * @author jzj * @date 2009-12-23 */ public class BinTreeInOrder extends BinTree { /** * 节点访问者,可根据需要重写visit方法 */ static abstract class Visitor { void visit(Object ele) { System.out.print(ele + " "); } } public void preOrder(Visitor v) { preOrder(v, root); } /** * 树的前序递归遍历 pre=prefix(前缀) * @param node 要遍历的节点 */ private void preOrder(Visitor v, Entry node) { //如果传进来的节点不为空,则遍历,注,叶子节点的子节点为null if (node != null) { v.visit(node.elem);//先遍历父节点 preOrder(v, node.left);//再遍历左节点 preOrder(v, node.right);//最后遍历右节点 } } public void inOrder(Visitor v) { inOrder(v, root); } /** * 树的中序递归遍历 in=infix(中缀) * @param node 要遍历的节点 */ private void inOrder(Visitor v, Entry node) { //如果传进来的节点不为空,则遍历,注,叶子节点的子节点为null if (node != null) { inOrder(v, node.left);//先遍历左节点 v.visit(node.elem);//再遍历父节点 inOrder(v, node.right);//最后遍历右节点 } } public void postOrder(Visitor v) { postOrder(v, root); } /** * 树的后序递归遍历 post=postfix(后缀) * @param node 要遍历的节点 */ private void postOrder(Visitor v, Entry node) { //如果传进来的节点不为空,则遍历,注,叶子节点的子节点为null if (node != null) { postOrder(v, node.left);//先遍历左节点 postOrder(v, node.right);//再遍历右节点 v.visit(node.elem);//最后遍历父节点 } } //测试 public static void main(String[] args) { //创建二叉树 int[] nums = new int[] { 1, 2, 3, 4, 0, 0, 5, 0, 6, 0, 0, 0, 0, 7, 8 }; BinTreeInOrder treeOrder = new BinTreeInOrder(); treeOrder.createBinTree(nums); System.out.print("前序遍历 - "); treeOrder.preOrder(new Visitor() { }); System.out.println(); System.out.print("中序遍历 - "); treeOrder.inOrder(new Visitor() { }); System.out.println(); System.out.print("后序遍历 - "); treeOrder.postOrder(new Visitor() { }); /* * output: * 前序遍历 - 1 2 4 6 3 5 7 8 * 中序遍历 - 4 6 2 1 3 7 5 8 * 后序遍历 - 6 4 2 7 8 5 3 1 */ } }  (三)二叉树的非递归遍历(属外部遍历) 1、利用栈与队列对二叉树进行非递归遍历 Java代码 1. package tree.bintree;    2.    3. import java.util.Iterator;    4. import java.util.LinkedList;    5. import java.util.Stack;    6.    7. /**   8.  * 二叉树的外部遍历:深度优先(先根)、广度(层次)优先遍历   9.  *    10.  * @author jzj   11.  * @date 2009-12-23   12.  */   13. public class BinTreeOutOrder extends BinTree {    14.    15.     /**   16.      * 二叉树深序优先遍历(即二叉树的先根遍历)迭代器,外部可以使用该迭代器   17.      * 进行非递归的遍历,这是一种在二叉树结构外部的一种遍历算法,它没有使用   18.      * 二叉树本身的结构特点(左右子树递归)进行递归遍历   19.      * @author jzj   20.      */   21.     private class DepthOrderIterator implements Iterator {    22.         //栈里存放的是每个节点    23.         private Stack stack = new Stack();    24.    25.         public DepthOrderIterator(Entry node) {    26.    27.             //根入栈,但在放入左右子节点前会马上出栈,即根先优于左右子节点访问    28.             stack.push(node);    29.    30.         }    31.    32.         //是否还有下一个元素    33.         public boolean hasNext() {    34.             if (stack.isEmpty()) {    35.                 return false;    36.             }    37.             return true;    38.         }    39.    40.         //取下一个元素    41.         public Entry next() {    42.             if (hasNext()) {    43.                 //取栈顶元素    44.                 Entry treeNode = (Entry) stack.pop();//先访问根    45.    46.                 if (treeNode.right != null) {    47.                     stack.push(treeNode.right);//再放入右子节点    48.                 }    49.    50.                 if (treeNode.left != null) {    51.                     stack.push(treeNode.left);//最后放入左子节点,但访问先于右节点    52.                 }    53.    54.                 // 返回遍历得到的节点    55.                 return treeNode;    56.    57.             } else {    58.                 // 如果栈为空    59.                 return null;    60.             }    61.         }    62.    63.         public void remove() {    64.             throw new UnsupportedOperationException();    65.         }    66.    67.     }    68.    69.     /**   70.      * 向外界提供先根遍历迭代器   71.      * @return Iterator 返回先根遍历迭代器   72.      */   73.     public Iterator createPreOrderItr() {    74.         return new DepthOrderIterator(root);    75.     }    76.    77.     /**   78.      * 二叉树广度优先遍历迭代器,外部可以使用该迭代器   79.      * 进行非递归的遍历,这是一种在二叉树结构外部的一种遍历算法,它没有使用   80.      * 二叉树本身的结构特点(左右子树递归)进行递归遍历   81.      * @author jzj   82.      */   83.     private class LevelOrderIterator implements Iterator {    84.         //使用队列结构实现层次遍历,队列里存储的为节点    85.         private LinkedList queue = new LinkedList();    86.    87.         public LevelOrderIterator(Entry node) {    88.    89.             if (node != null) {    90.                 //将根入队    91.                 queue.addLast(node);    92.             }    93.         }    94.    95.         //是否还有下一个元素    96.         public boolean hasNext() {    97.             if (queue.isEmpty()) {    98.                 return false;    99.             }    100.             return true;    101.         }    102.    103.         //取下一个元素    104.         public Entry next() {    105.             if (hasNext()) {    106.                 //取栈顶迭元素    107.                 Entry treeNode = (Entry) queue.removeFirst();    108.    109.                 if (treeNode.left != null) {//如果有左子树,加入有序列表中    110.                     queue.addLast(treeNode.left);    111.                 }    112.                 if (treeNode.right != null) {//如果有右子树,加入有序列表中    113.                     queue.addLast(treeNode.right);    114.                 }    115.    116.                 // 返回遍历得到的节点    117.                 return treeNode;    118.    119.             } else {    120.                 // 如果队列为空    121.                 return null;    122.             }    123.         }    124.    125.         public void remove() {    126.             throw new UnsupportedOperationException();    127.         }    128.    129.     }    130.    131.     /**   132.      * 向外界提供广度优先迭代器   133.      * @return Iterator 返回遍历迭代器   134.      */   135.     public Iterator createLayerOrderItr() {    136.         return new LevelOrderIterator(root);    137.     }    138.    139.     public static void main(String[] args) {    140.         //创建一棵满二叉树    141.         BinTreeOutOrder treeOrder = new BinTreeOutOrder();    142.         treeOrder.createFullBiTree(15);    143.         Iterator preOrderItr = treeOrder.createPreOrderItr();    144.         System.out.print("深度优先(先根)遍历 - ");    145.         while (preOrderItr.hasNext()) {    146.             System.out.print(((Entry) preOrderItr.next()).elem + " ");    147.         }    148.         System.out.println();    149.         System.out.print("广度优先(层次)遍历 - ");    150.         Iterator layerOrderItr = treeOrder.createLayerOrderItr();    151.         while (layerOrderItr.hasNext()) {    152.             System.out.print(((Entry) layerOrderItr.next()).elem + " ");    153.         }    154.         /*   155.          * output:   156.          * 深度优先(先根)遍历 - 1 2 4 8 9 5 10 11 3 6 12 13 7 14 15   157.          * 广度优先(层次)遍历 - 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15     158.          */   159.     }    160. }    package tree.bintree; import java.util.Iterator; import java.util.LinkedList; import java.util.Stack; /** * 二叉树的外部遍历:深度优先(先根)、广度(层次)优先遍历 * * @author jzj * @date 2009-12-23 */ public class BinTreeOutOrder extends BinTree { /** * 二叉树深序优先遍历(即二叉树的先根遍历)迭代器,外部可以使用该迭代器 * 进行非递归的遍历,这是一种在二叉树结构外部的一种遍历算法,它没有使用 * 二叉树本身的结构特点(左右子树递归)进行递归遍历 * @author jzj */ private class DepthOrderIterator implements Iterator { //栈里存放的是每个节点 private Stack stack = new Stack(); public DepthOrderIterator(Entry node) { //根入栈,但在放入左右子节点前会马上出栈,即根先优于左右子节点访问 stack.push(node); } //是否还有下一个元素 public boolean hasNext() { if (stack.isEmpty()) { return false; } return true; } //取下一个元素 public Entry next() { if (hasNext()) { //取栈顶元素 Entry treeNode = (Entry) stack.pop();//先访问根 if (treeNode.right != null) { stack.push(treeNode.right);//再放入右子节点 } if (treeNode.left != null) { stack.push(treeNode.left);//最后放入左子节点,但访问先于右节点 } // 返回遍历得到的节点 return treeNode; } else { // 如果栈为空 return null; } } public void remove() { throw new UnsupportedOperationException(); } } /** * 向外界提供先根遍历迭代器 * @return Iterator 返回先根遍历迭代器 */ public Iterator createPreOrderItr() { return new DepthOrderIterator(root); } /** * 二叉树广度优先遍历迭代器,外部可以使用该迭代器 * 进行非递归的遍历,这是一种在二叉树结构外部的一种遍历算法,它没有使用 * 二叉树本身的结构特点(左右子树递归)进行递归遍历 * @author jzj */ private class LevelOrderIterator implements Iterator { //使用队列结构实现层次遍历,队列里存储的为节点 private LinkedList queue = new LinkedList(); public LevelOrderIterator(Entry node) { if (node != null) { //将根入队 queue.addLast(node); } } //是否还有下一个元素 public boolean hasNext() { if (queue.isEmpty()) { return false; } return true; } //取下一个元素 public Entry next() { if (hasNext()) { //取栈顶迭元素 Entry treeNode = (Entry) queue.removeFirst(); if (treeNode.left != null) {//如果有左子树,加入有序列表中 queue.addLast(treeNode.left); } if (treeNode.right != null) {//如果有右子树,加入有序列表中 queue.addLast(treeNode.right); } // 返回遍历得到的节点 return treeNode; } else { // 如果队列为空 return null; } } public void remove() { throw new UnsupportedOperationException(); } } /** * 向外界提供广度优先迭代器 * @return Iterator 返回遍历迭代器 */ public Iterator createLayerOrderItr() { return new LevelOrderIterator(root); } public static void main(String[] args) { //创建一棵满二叉树 BinTreeOutOrder treeOrder = new BinTreeOutOrder(); treeOrder.createFullBiTree(15); Iterator preOrderItr = treeOrder.createPreOrderItr(); System.out.print("深度优先(先根)遍历 - "); while (preOrderItr.hasNext()) { System.out.print(((Entry) preOrderItr.next()).elem + " "); } System.out.println(); System.out.print("广度优先(层次)遍历 - "); Iterator layerOrderItr = treeOrder.createLayerOrderItr(); while (layerOrderItr.hasNext()) { System.out.print(((Entry) layerOrderItr.next()).elem + " "); } /* * output: * 深度优先(先根)遍历 - 1 2 4 8 9 5 10 11 3 6 12 13 7 14 15 * 广度优先(层次)遍历 - 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 */ } }  2、利用二叉树节点的父节点指针进行非递归遍历 要想采用非递归的方法遍历树,又不借助于前面的队列与栈,我们需要该树是一棵可回溯的二叉树,即从子节点要能够知道他的父节点及祖先节点,与前面的二叉树不同的是,树的节点结构体中多一个指向父的节点指针,这样外界可以以非递归的方式来遍历二叉树了 。 Java代码 1. package tree.bintree;    2.    3. /**   4.  *    5.  * 可回溯的二叉树   6.  * 二叉树的非递归遍历   7.  *    8.  * @author jzj   9.  * @date 2009-12-23   10.  */   11. public class BackBinTree {// Bin=Binary(二进位的, 二元的)    12.    13.     protected Entry root;//根    14.     private int size;//树的节点数    15.    16.     /**   17.      * 树的节点结构   18.      * @author jzj   19.      * @date 2009-12-23   20.      */   21.     private static class Entry {    22.         int elem;//数据域,这里为了测试,就作为节点编号吧    23.         Entry paraent;//父节点    24.         Entry left;//左节点    25.         Entry right;//右节点    26.    27.         //构造函数只有两个参数,左右节点是调用add方法时设置    28.         public Entry(int elem, Entry parent) {    29.             this.elem = elem;    30.             this.paraent = parent;    31.         }    32.     }    33.    34.     /**   35.      * 查找前序遍历(根左右)直接后继节点   36.      *    37.      * 以非递归 根左右 的方式遍历树   38.      *    39.      * @param e 需要查找哪个节点的直接后继节点   40.      * @return Entry 前序遍历直接后继节点   41.      */   42.     public Entry preOrderSuccessor(Entry e) {    43.         if (e == null) {    44.             return null;    45.         }//如果左子树不为空,则直接后继为左子节点    46.         else if (e.left != null) {//先看左子节点是否为空    47.             return e.left;//如果不为空,则直接后继为左子节点    48.         }//否则如果右子树不为空,则直接后继为右子节点    49.         else if (e.right != null) {//如果左子节点为空,则看右子节点是否为空    50.             return e.right;//如果右子节点不为空,则返回    51.         }//左右子节点都为空的情况下    52.         else {    53.             Entry s = e.paraent;    54.             Entry c = e;    55.    56.             /*   57.             * 一直向上,直到c是s的左子树,且s的右子树不为空。请试着找一下36与68节点的   58.             * 直接后继节点,36的应该是75,而68则没有后继节点了   59.             *    60.             *                            50   61.             *                            /\   62.             *                          37  75   63.             *                         /    /   64.             *                       25    61   65.             *                      /\     /\   66.             *                    15 30   55 68   67.             *                       /\    \   68.             *                     28 32   59   69.             *                         \   70.             *                         36   71.             */   72.             while (s != null && (c == s.right || s.right == null)) {    73.                 c = s;    74.                 s = s.paraent;    75.             }    76.             //退出循环时 s 可以为null,比如查找 68 节点的直接后继时退出循环时s=null    77.             if (s == null) {    78.                 return null;    79.             } else {    80.                 return s.right;    81.             }    82.         }    83.     }    84.    85.     /**   86.      * 查找前序遍历(根左右)直接前驱节点   87.      *    88.      * 以非递归 右左根 的方式遍历树   89.      *    90.      * @param e 需要查找哪个节点的直接前驱节点   91.      * @return Entry 前序遍历直接前驱节点   92.      */   93.     public Entry preOrderAncestor(Entry e) {    94.         if (e == null) {    95.             return null;    96.         }//如果节点为父节点的左节点,则父节点就是直接前驱节点    97.         else if (e.paraent != null && e == e.paraent.left) {    98.             return e.paraent;    99.         }//如果节点为父节点的右节点    100.         else if (e.paraent != null && e == e.paraent.right) {    101.    102.             Entry s = e.paraent;//前驱节点默认为父节点    103.             if (s.left != null) {//如果父节点没有左子,前驱节点就为父节点    104.                 s = s.left;//如果父节点的左子节点不空,则初始为父节点左子节点    105.    106.                 /*   107.                 * 只要父节点左子节点还有子节点,则前驱节点要从其子树中找。请试着找   108.                 * 一下75直接前驱节点,应该是36   109.                 *    110.                 *                            50   111.                 *                            /\   112.                 *                          37  75   113.                 *                         /    /   114.                 *                       25    61   115.                 *                      /\     /\   116.                 *                    15 30   55 68   117.                 *                       /\    \   118.                 *                     28 32   59   119.                 *                         \   120.                 *                         36   121.                 */   122.                 while (s.left != null || s.right != null) {    123.                     //在父节点的左子节点的子树中查找时,一定要先向右边拐    124.                     if (s.right != null) {    125.                         s = s.right;    126.                     } else {//如果右边没有,然后才能向左边拐    127.                         s = s.left;    128.                     }    129.                 }    130.             }    131.             return s;    132.         } else {//如果是根节点,则没有直接前驱节点了    133.             return null;    134.         }    135.     }    136.    137.     /**   138.      * 查找后序遍历(左右根)直接后继节点   139.      *    140.      * 以非递归 左右根 的方式遍历树   141.      *    142.      * @param e 需要查找哪个节点的直接后继节点   143.      * @return Entry 后序遍历直接后继节点   144.      */   145.     public Entry postOrderSuccessor(Entry e) {    146.         if (e == null) {    147.             return null;    148.         }//如果节点为父节点的右子节点,则父节点就是直接后继节点    149.         else if (e.paraent != null && e == e.paraent.right) {    150.             return e.paraent;    151.         }//如果节点为父节点的左子节点    152.         else if (e.paraent != null && e == e.paraent.left) {    153.             Entry s = e.paraent;//后继节点默认为父节点    154.             if (s.right != null) {//如果父节点没有右子,后继节点就为父节点    155.                 s = s.right;//如果父节点的右子节点不空,则初始为父节点右子节点    156.                 /*   157.                  * 只要父节点右子节点还有子节点,则后断节点要从其子树中找,   158.                  * 如15的后继节点为28   159.                  *                            50   160.                  *                            /\   161.                  *                          37  75   162.                  *                         /    /   163.                  *                       25    61   164.                  *                      /\     /\   165.                  *                    15 30   55 68   166.                  *                       /\    \   167.                  *                     28 32   59   168.                  *                         \   169.                  *                         36   170.                  */   171.    172.                 while (s.left != null || s.right != null) {    173.                     //在父节点的右子节点的子树中查找时,一定要先向左边拐    174.                     if (s.left != null) {    175.                         s = s.left;    176.                     } else {//如果左边没有,然后才能向右边拐    177.                         s = s.right;    178.                     }    179.                 }    180.             }    181.             return s;    182.         } else {    183.             //如果是根节点,则没有后继节点了    184.             return null;    185.         }    186.     }    187.    188.     /**   189.      * 查找后序遍历(左右根)直接前驱节点   190.      *    191.      * 以非递归 根右左 的方式遍历树   192.      *    193.      * @param e 需要查找哪个节点的直接前驱节点   194.      * @return Entry 后序遍历直接前驱节点   195.      */   196.     public Entry postOrderAncestor(Entry e) {    197.    198.         if (e == null) {    199.             return null;    200.         }//如果右子树不为空,则直接前驱为右子节点    201.         else if (e.right != null) {//先看右子节点是否为空    202.             return e.right;//如果不为空,则直接后继为右子节点    203.         }//否则如果左子树不为空,则直接前驱为左子节点    204.         else if (e.left != null) {    205.             return e.left;    206.         }//左右子节点都为空的情况下    207.         else {    208.             Entry s = e.paraent;    209.             Entry c = e;    210.    211.             /*   212.             * 一直向上,直到c是s的右子树,且s的左子树不为空。请试着找一下59与15节点的   213.             * 直接后继节点,59的应该是37,而15则没有后继节点了   214.             *    215.             *                            50   216.             *                            /\   217.             *                          37  75   218.             *                         /    /   219.             *                       25    61   220.             *                      /\     /\   221.             *                    15 30   55 68   222.             *                       /\    \   223.             *                     28 32   59   224.             *                         \   225.             *                         36   226.             */   227.             while (s != null && (c == s.left || s.left == null)) {    228.                 c = s;    229.                 s = s.paraent;    230.             }    231.             if (s == null) {    232.                 return null;    233.             } else {    234.                 return s.left;    235.             }    236.         }    237.     }    238.    239.     /**   240.      * 查找中序遍历(左根右)直接后继节点   241.      *    242.      * 以非递归 左根右 的方式遍历树   243.      *    244.      * @param e 需要查找哪个节点的直接后继节点   245.      * @return Entry 中序遍历直接后继节点   246.      */   247.     public Entry inOrderSuccessor(Entry e) {    248.         if (e == null) {    249.             return null;    250.         }//如果待找的节点有右子树,则在右子树上查找    251.         else if (e.right != null) {    252.             //默认后继节点为右子节点(如果右子节点没有左子树时即为该节点)    253.             Entry p = e.right;    254.             while (p.left != null) {    255.                 //注,如果右子节点的左子树不为空,则在左子树中查找,且后面找时要一直向左拐    256.                 p = p.left;    257.             }    258.             return p;    259.         }//如果待查节点没有右子树,则要在祖宗节点中查找后继节点     260.         else {    261.             //默认后继节点为父节点(如果待查节点为父节点的左子树,则后继为父节点)    262.             Entry p = e.paraent;    263.             Entry current = e;//当前节点,如果其父不为后继,则下次指向父节点    264.             //如果待查节点为父节点的右节点时,继续向上找,一直要找到current为左子节点,则s才是后继    265.             while (p != null && current == p.right) {    266.                 current = p;    267.                 p = p.paraent;    268.             }    269.             return p;    270.         }    271.     }    272.    273.     /**   274.      * 查找中序遍历(左根右)直接前驱节点   275.      *    276.      * 以非递归 右根左 的方式遍历树   277.      *    278.      * @param e 需要查找哪个节点的直接前驱节点   279.      * @return Entry 中序遍历直接前驱节点   280.      */   281.     public Entry inOrderAncestor(Entry e) {    282.         if (e == null) {    283.             return null;    284.         }//如果待找的节点有左子树,则在在子树上查找    285.         else if (e.left != null) {    286.             //默认直接前驱节点为左子节点(如果左子节点没有右子树时即为该节点)    287.             Entry p = e.left;    288.             while (p.right != null) {    289.                 //注,如果左子节点的右子树不为空,则在右子树中查找,且后面找时要一直向右拐    290.                 p = p.right;    291.             }    292.             return p;    293.         }//如果待查节点没有左子树,则要在祖宗节点中查找前驱节点     294.         else {    295.             //默认前驱节点为父节点(如果待查节点为父节点的右子树,则前驱为父节点)    296.             Entry p = e.paraent;    297.             Entry current = e;//当前节点,如果其父不为前驱,则下次指向父节点    298.             //如果待查节点为父节点的左节点时,继续向上找,一直要找到current为p的右子节点,则s才是前驱    299.             while (p != null && current == p.left) {    300.                 current = p;    301.                 p = p.paraent;    302.             }    303.             return p;    304.         }    305.     }    306.    307.     /**   308.      * 查找指定的节点   309.      * @param num   310.      * @return Entry   311.      */   312.     public Entry getEntry(int num) {    313.         return getEntry(root, num);    314.     }    315.    316.     /**   317.      * 使用树的先序遍历递归方式查找指定的节点   318.      *    319.      * @param entry   320.      * @param num   321.      * @return   322.      */   323.     private Entry getEntry(Entry entry, int num) {    324.    325.         //如果找到,则停止后续搜索,并把查找到的节点返回给上层调用者    326.         if (entry.elem == num) {//1、先与父节点比对    327.             return entry;    328.         }    329.    330.         Entry tmp = null;    331.    332.         if (entry.left != null) {//2、再在左子树上找    333.             tmp = getEntry(entry.left, num);    334.             //如果左子树上找到,返回并停止查找,否则继续在后续节点中找    335.             if (tmp != null) {    336.                 //节点在左子树中找到,返回给上层调用者    337.                 return tmp;    338.             }    339.         }    340.    341.         if (entry.right != null) {//3、否则在右子树上找    342.             tmp = getEntry(entry.right, num);    343.             //如果右子树上找到,返回并停止查找,否则继续在后续节点中找    344.             if (tmp != null) {    345.                 //节点在右子树中找到,返回给上层调用者    346.                 return tmp;    347.             }    348.         }    349.    350.         //当前比较节点 entry 子树为空或不为空时没有找到,直接返回给上层调用者null    351.         return null;    352.     }    353.    354.     /**   355.      * 根据给定的数组创建一棵树,这个棵树可以是完全二叉树也可是普通二叉树   356.      * 数组中为0的表示不创建该位置上的节点   357.      * @param nums 数组中指定了要创建的节点的编号,如果为0,表示不创建   358.      */   359.     public void createBinTree(int[] nums) {    360.         root = recurCreateBinTree(nums, null, 0);    361.     }    362.    363.     /**   364.      * 递归创建二叉树   365.      * @param nums 数组中指定了要创建的节点的编号,如果为0,表示不创建   366.      * @param paraent 父节点   367.      * @param index 需要使用数组中的哪个元素创建节点,如果为元素为0,则不创建   368.      * @return Entry 返回创建的节点,最终会返回树的根节点   369.      */   370.     private Entry recurCreateBinTree(int[] nums, Entry pararent, int index) {    371.         //指定索引上的编号不为零上才需创建节点    372.         if (nums[index] != 0) {    373.             size++;    374.             Entry root = new Entry(nums[index], pararent);//根节点    375.             //如果有左子树则创建左子树    376.             if ((index + 1) * 2 <= nums.length) {    377.                 root.left = (Entry) recurCreateBinTree(nums, root, (index + 1) * 2 - 1);    378.                 //如果还可以创建右子树,则创建    379.                 if ((index + 1) * 2 + 1 <= nums.length) {    380.                     root.right = (Entry) recurCreateBinTree(nums, root, (index + 1) * 2);    381.                 }    382.             }    383.             return (Entry) root;    384.         }    385.         return null;    386.    387.     }    388.    389.     public int size() {    390.         return size;    391.     }    392.    393.     //测试    394.     public static void main(String[] args) {    395.    396.         //创建一棵非完全二叉树    397.         BackBinTree binTree = new BackBinTree();    398.         /*   399.         *                            50   400.         *                            /\   401.         *                          37  75   402.         *                         /    /   403.         *                       25    61   404.         *                      /\     /\   405.         *                    15 30   55 68   406.         *                       /\    \   407.         *                     28 32   59   408.         *                         \   409.         *                         36   410.         */   411.         int[] nums = new int[] { 50, 37, 75, 25, 0, 61, 0, 15, 30, 0, 0, 55, 68, 0, 0, 0,    412.                 0, 28, 32, 0, 0, 0, 0, 0, 59, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 36 };    413.         binTree.createBinTree(nums);    414.    415.         Entry entry = binTree.getEntry(50);    416.         System.out.print("根左右(先序遍历)- ");    417.         while (entry != null) {    418.             System.out.print(entry.elem + " ");    419.             entry = binTree.preOrderSuccessor(entry);    420.         }    421.         System.out.println();    422.         entry = binTree.getEntry(68);    423.         System.out.print("右左根(先序的逆)- ");    424.         while (entry != null) {    425.             System.out.print(entry.elem + " ");    426.             entry = binTree.preOrderAncestor(entry);    427.         }    428.         System.out.println();    429.         entry = binTree.getEntry(15);    430.         System.out.print("左右根(后序遍历)- ");    431.         while (entry != null) {    432.             System.out.print(entry.elem + " ");    433.             entry = binTree.postOrderSuccessor(entry);    434.         }    435.         System.out.println();    436.    437.         entry = binTree.getEntry(50);    438.         System.out.print("根右左(后序的逆)- ");    439.         while (entry != null) {    440.             System.out.print(entry.elem + " ");    441.             entry = binTree.postOrderAncestor(entry);    442.         }    443.         System.out.println();    444.    445.         entry = binTree.getEntry(15);    446.         System.out.print("左根右(中序遍历)- ");    447.         while (entry != null) {    448.             System.out.print(entry.elem + " ");    449.             entry = binTree.inOrderSuccessor(entry);    450.         }    451.         System.out.println();    452.    453.         entry = binTree.getEntry(75);    454.         System.out.print("右根左(中序的逆)- ");    455.         while (entry != null) {    456.             System.out.print(entry.elem + " ");    457.             entry = binTree.inOrderAncestor(entry);    458.         }    459.         System.out.println();    460.         /*   461.          * output:   462.          * 根左右(先序遍历)- 50 37 25 15 30 28 32 36 75 61 55 59 68    463.          * 右左根(先序的逆)- 68 59 55 61 75 36 32 28 30 15 25 37 50   464.          * 左右根(后序遍历)- 15 28 36 32 30 25 37 59 55 68 61 75 50   465.          * 根右左(后序的逆)- 50 75 61 68 55 59 37 25 30 32 36 28 15   466.          * 左根右(中序遍历)- 15 25 28 30 32 36 37 50 55 59 61 68 75   467.          * 右根左(中序的逆)- 75 68 61 59 55 50 37 36 32 30 28 25 15     468.          */   469.     }    470. }   package tree.bintree; /** * * 可回溯的二叉树 * 二叉树的非递归遍历 * * @author jzj * @date 2009-12-23 */ public class BackBinTree {// Bin=Binary(二进位的, 二元的) protected Entry root;//根 private int size;//树的节点数 /** * 树的节点结构 * @author jzj * @date 2009-12-23 */ private static class Entry { int elem;//数据域,这里为了测试,就作为节点编号吧 Entry paraent;//父节点 Entry left;//左节点 Entry right;//右节点 //构造函数只有两个参数,左右节点是调用add方法时设置 public Entry(int elem, Entry parent) { this.elem = elem; this.paraent = parent; } } /** * 查找前序遍历(根左右)直接后继节点 * * 以非递归 根左右 的方式遍历树 * * @param e 需要查找哪个节点的直接后继节点 * @return Entry 前序遍历直接后继节点 */ public Entry preOrderSuccessor(Entry e) { if (e == null) { return null; }//如果左子树不为空,则直接后继为左子节点 else if (e.left != null) {//先看左子节点是否为空 return e.left;//如果不为空,则直接后继为左子节点 }//否则如果右子树不为空,则直接后继为右子节点 else if (e.right != null) {//如果左子节点为空,则看右子节点是否为空 return e.right;//如果右子节点不为空,则返回 }//左右子节点都为空的情况下 else { Entry s = e.paraent; Entry c = e; /* * 一直向上,直到c是s的左子树,且s的右子树不为空。请试着找一下36与68节点的 * 直接后继节点,36的应该是75,而68则没有后继节点了 * * 50 * /\ * 37 75 * / / * 25 61 * /\ /\ * 15 30 55 68 * /\ \ * 28 32 59 * \ * 36 */ while (s != null && (c == s.right || s.right == null)) { c = s; s = s.paraent; } //退出循环时 s 可以为null,比如查找 68 节点的直接后继时退出循环时s=null if (s == null) { return null; } else { return s.right; } } } /** * 查找前序遍历(根左右)直接前驱节点 * * 以非递归 右左根 的方式遍历树 * * @param e 需要查找哪个节点的直接前驱节点 * @return Entry 前序遍历直接前驱节点 */ public Entry preOrderAncestor(Entry e) { if (e == null) { return null; }//如果节点为父节点的左节点,则父节点就是直接前驱节点 else if (e.paraent != null && e == e.paraent.left) { return e.paraent; }//如果节点为父节点的右节点 else if (e.paraent != null && e == e.paraent.right) { Entry s = e.paraent;//前驱节点默认为父节点 if (s.left != null) {//如果父节点没有左子,前驱节点就为父节点 s = s.left;//如果父节点的左子节点不空,则初始为父节点左子节点 /* * 只要父节点左子节点还有子节点,则前驱节点要从其子树中找。请试着找 * 一下75直接前驱节点,应该是36 * * 50 * /\ * 37 75 * / / * 25 61 * /\ /\ * 15 30 55 68 * /\ \ * 28 32 59 * \ * 36 */ while (s.left != null || s.right != null) { //在父节点的左子节点的子树中查找时,一定要先向右边拐 if (s.right != null) { s = s.right; } else {//如果右边没有,然后才能向左边拐 s = s.left; } } } return s; } else {//如果是根节点,则没有直接前驱节点了 return null; } } /** * 查找后序遍历(左右根)直接后继节点 * * 以非递归 左右根 的方式遍历树 * * @param e 需要查找哪个节点的直接后继节点 * @return Entry 后序遍历直接后继节点 */ public Entry postOrderSuccessor(Entry e) { if (e == null) { return null; }//如果节点为父节点的右子节点,则父节点就是直接后继节点 else if (e.paraent != null && e == e.paraent.right) { return e.paraent; }//如果节点为父节点的左子节点 else if (e.paraent != null && e == e.paraent.left) { Entry s = e.paraent;//后继节点默认为父节点 if (s.right != null) {//如果父节点没有右子,后继节点就为父节点 s = s.right;//如果父节点的右子节点不空,则初始为父节点右子节点 /* * 只要父节点右子节点还有子节点,则后断节点要从其子树中找, * 如15的后继节点为28 * 50 * /\ * 37 75 * / / * 25 61 * /\ /\ * 15 30 55 68 * /\ \ * 28 32 59 * \ * 36 */ while (s.left != null || s.right != null) { //在父节点的右子节点的子树中查找时,一定要先向左边拐 if (s.left != null) { s = s.left; } else {//如果左边没有,然后才能向右边拐 s = s.right; } } } return s; } else { //如果是根节点,则没有后继节点了 return null; } } /** * 查找后序遍历(左右根)直接前驱节点 * * 以非递归 根右左 的方式遍历树 * * @param e 需要查找哪个节点的直接前驱节点 * @return Entry 后序遍历直接前驱节点 */ public Entry postOrderAncestor(Entry e) { if (e == null) { return null; }//如果右子树不为空,则直接前驱为右子节点 else if (e.right != null) {//先看右子节点是否为空 return e.right;//如果不为空,则直接后继为右子节点 }//否则如果左子树不为空,则直接前驱为左子节点 else if (e.left != null) { return e.left; }//左右子节点都为空的情况下 else { Entry s = e.paraent; Entry c = e; /* * 一直向上,直到c是s的右子树,且s的左子树不为空。请试着找一下59与15节点的 * 直接后继节点,59的应该是37,而15则没有后继节点了 * * 50 * /\ * 37 75 * / / * 25 61 * /\ /\ * 15 30 55 68 * /\ \ * 28 32 59 * \ * 36 */ while (s != null && (c == s.left || s.left == null)) { c = s; s = s.paraent; } if (s == null) { return null; } else { return s.left; } } } /** * 查找中序遍历(左根右)直接后继节点 * * 以非递归 左根右 的方式遍历树 * * @param e 需要查找哪个节点的直接后继节点 * @return Entry 中序遍历直接后继节点 */ public Entry inOrderSuccessor(Entry e) { if (e == null) { return null; }//如果待找的节点有右子树,则在右子树上查找 else if (e.right != null) { //默认后继节点为右子节点(如果右子节点没有左子树时即为该节点) Entry p = e.right; while (p.left != null) { //注,如果右子节点的左子树不为空,则在左子树中查找,且后面找时要一直向左拐 p = p.left; } return p; }//如果待查节点没有右子树,则要在祖宗节点中查找后继节点 else { //默认后继节点为父节点(如果待查节点为父节点的左子树,则后继为父节点) Entry p = e.paraent; Entry current = e;//当前节点,如果其父不为后继,则下次指向父节点 //如果待查节点为父节点的右节点时,继续向上找,一直要找到current为左子节点,则s才是后继 while (p != null && current == p.right) { current = p; p = p.paraent; } return p; } } /** * 查找中序遍历(左根右)直接前驱节点 * * 以非递归 右根左 的方式遍历树 * * @param e 需要查找哪个节点的直接前驱节点 * @return Entry 中序遍历直接前驱节点 */ public Entry inOrderAncestor(Entry e) { if (e == null) { return null; }//如果待找的节点有左子树,则在在子树上查找 else if (e.left != null) { //默认直接前驱节点为左子节点(如果左子节点没有右子树时即为该节点) Entry p = e.left; while (p.right != null) { //注,如果左子节点的右子树不为空,则在右子树中查找,且后面找时要一直向右拐 p = p.right; } return p; }//如果待查节点没有左子树,则要在祖宗节点中查找前驱节点 else { //默认前驱节点为父节点(如果待查节点为父节点的右子树,则前驱为父节点) Entry p = e.paraent; Entry current = e;//当前节点,如果其父不为前驱,则下次指向父节点 //如果待查节点为父节点的左节点时,继续向上找,一直要找到current为p的右子节点,则s才是前驱 while (p != null && current == p.left) { current = p; p = p.paraent; } return p; } } /** * 查找指定的节点 * @param num * @return Entry */ public Entry getEntry(int num) { return getEntry(root, num); } /** * 使用树的先序遍历递归方式查找指定的节点 * * @param entry * @param num * @return */ private Entry getEntry(Entry entry, int num) { //如果找到,则停止后续搜索,并把查找到的节点返回给上层调用者 if (entry.elem == num) {//1、先与父节点比对 return entry; } Entry tmp = null; if (entry.left != null) {//2、再在左子树上找 tmp = getEntry(entry.left, num); //如果左子树上找到,返回并停止查找,否则继续在后续节点中找 if (tmp != null) { //节点在左子树中找到,返回给上层调用者 return tmp; } } if (entry.right != null) {//3、否则在右子树上找 tmp = getEntry(entry.right, num); //如果右子树上找到,返回并停止查找,否则继续在后续节点中找 if (tmp != null) { //节点在右子树中找到,返回给上层调用者 return tmp; } } //当前比较节点 entry 子树为空或不为空时没有找到,直接返回给上层调用者null return null; } /** * 根据给定的数组创建一棵树,这个棵树可以是完全二叉树也可是普通二叉树 * 数组中为0的表示不创建该位置上的节点 * @param nums 数组中指定了要创建的节点的编号,如果为0,表示不创建 */ public void createBinTree(int[] nums) { root = recurCreateBinTree(nums, null, 0); } /** * 递归创建二叉树 * @param nums 数组中指定了要创建的节点的编号,如果为0,表示不创建 * @param paraent 父节点 * @param index 需要使用数组中的哪个元素创建节点,如果为元素为0,则不创建 * @return Entry 返回创建的节点,最终会返回树的根节点 */ private Entry recurCreateBinTree(int[] nums, Entry pararent, int index) { //指定索引上的编号不为零上才需创建节点 if (nums[index] != 0) { size++; Entry root = new Entry(nums[index], pararent);//根节点 //如果有左子树则创建左子树 if ((index + 1) * 2 <= nums.length) { root.left = (Entry) recurCreateBinTree(nums, root, (index + 1) * 2 - 1); //如果还可以创建右子树,则创建 if ((index + 1) * 2 + 1 <= nums.length) { root.right = (Entry) recurCreateBinTree(nums, root, (index + 1) * 2); } } return (Entry) root; } return null; } public int size() { return size; } //测试 public static void main(String[] args) { //创建一棵非完全二叉树 BackBinTree binTree = new BackBinTree(); /* * 50 * /\ * 37 75 * / / * 25 61 * /\ /\ * 15 30 55 68 * /\ \ * 28 32 59 * \ * 36 */ int[] nums = new int[] { 50, 37, 75, 25, 0, 61, 0, 15, 30, 0, 0, 55, 68, 0, 0, 0, 0, 28, 32, 0, 0, 0, 0, 0, 59, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 36 }; binTree.createBinTree(nums); Entry entry = binTree.getEntry(50); System.out.print("根左右(先序遍历)- "); while (entry != null) { System.out.print(entry.elem + " "); entry = binTree.preOrderSuccessor(entry); } System.out.println(); entry = binTree.getEntry(68); System.out.print("右左根(先序的逆)- "); while (entry != null) { System.out.print(entry.elem + " "); entry = binTree.preOrderAncestor(entry); } System.out.println(); entry = binTree.getEntry(15); System.out.print("左右根(后序遍历)- "); while (entry != null) { System.out.print(entry.elem + " "); entry = binTree.postOrderSuccessor(entry); } System.out.println(); entry = binTree.getEntry(50); System.out.print("根右左(后序的逆)- "); while (entry != null) { System.out.print(entry.elem + " "); entry = binTree.postOrderAncestor(entry); } System.out.println(); entry = binTree.getEntry(15); System.out.print("左根右(中序遍历)- "); while (entry != null) { System.out.print(entry.elem + " "); entry = binTree.inOrderSuccessor(entry); } System.out.println(); entry = binTree.getEntry(75); System.out.print("右根左(中序的逆)- "); while (entry != null) { System.out.print(entry.elem + " "); entry = binTree.inOrderAncestor(entry); } System.out.println(); /* * output: * 根左右(先序遍历)- 50 37 25 15 30 28 32 36 75 61 55 59 68 * 右左根(先序的逆)- 68 59 55 61 75 36 32 28 30 15 25 37 50 * 左右根(后序遍历)- 15 28 36 32 30 25 37 59 55 68 61 75 50 * 根右左(后序的逆)- 50 75 61 68 55 59 37 25 30 32 36 28 15 * 左根右(中序遍历)- 15 25 28 30 32 36 37 50 55 59 61 68 75 * 右根左(中序的逆)- 75 68 61 59 55 50 37 36 32 30 28 25 15 */ } } · · 大小: 1.4 KB · · 大小: 12.3 KB package tree.bintree; /** * 创建 非完全二叉树、完全二叉树、满二叉树 * * 由于二叉树的节点增加没有什么规则,所以这里只是简单的使用了递一 * 次性把整棵树创建出来,而没有设计出一个一个添加节点的方法与删除 * * @author jzj * @date 2009-12-23 */ public class BinTree {// Bin=Binary(二进位的, 二元的) protected Entry root;//根 private int size;//树的节点数 /** * 树的节点结构 * @author jzj * @date 2009-12-23 */ protected static class Entry { int elem;//数据域,这里我们作为编号 Entry left;//左子树 Entry right;//右子树 public Entry(int elem) { this.elem = elem; } public String toString() { return " number=" + elem; } } /** * 根据给定的节点数创建一个完全二叉树或是满二叉树 * @param nodeCount 要创建节点总数 */ public void createFullBiTree(int nodeCount) { root = recurCreateFullBiTree(1, nodeCount); } /** * 递归创建完全二叉树 * @param num 节点编号 * @param nodeCount 节点总数 * @return TreeNode 返回创建的节点 */ private Entry recurCreateFullBiTree(int num, int nodeCount) { size++; Entry rootNode = new Entry(num);//根节点 //如果有左子树则创建左子树 if (num * 2 <= nodeCount) { rootNode.left = recurCreateFullBiTree(num * 2, nodeCount); //如果还可以创建右子树,则创建 if (num * 2 + 1 <= nodeCount) { rootNode.right = recurCreateFullBiTree(num * 2 + 1, nodeCount); } } return (Entry) rootNode; } /** * 根据给定的数组创建一棵树,这个棵树可以是完全二叉树也可是普通二叉树 * 数组中为0的表示不创建该位置上的节点 * @param nums 数组中指定了要创建的节点的编号,如果为0,表示不创建 */ public void createBinTree(int[] nums) { root = recurCreateBinTree(nums, 0); } /** * 递归创建二叉树 * @param nums 数组中指定了要创建的节点的编号,如果为0,表示不创建 * @param index 需要使用数组中的哪个元素创建节点,如果为元素为0,则不创建 * @return TreeNode 返回创建的节点,最终会返回树的根节点 */ private Entry recurCreateBinTree(int[] nums, int index) { //指定索引上的编号不为零上才需创建节点 if (nums[index] != 0) { size++; Entry rootNode = new Entry(nums[index]);//根节点 //如果有左子树则创建左子树 if ((index + 1) * 2 <= nums.length) { rootNode.left = (Entry) recurCreateBinTree(nums, (index + 1) * 2 - 1); //如果还可以创建右子树,则创建 if ((index + 1) * 2 + 1 <= nums.length) { rootNode.right = (Entry) recurCreateBinTree(nums, (index + 1) * 2); } } return (Entry) rootNode; } return null; } public int size() { return size; } //取树的最左边的节点 public int getLast() { Entry e = root; while (e.right != null) { e = e.right; } return e.elem; } //测试 public static void main(String[] args) { //创建一个满二叉树 BinTree binTree = new BinTree(); binTree.createFullBiTree(15); System.out.println(binTree.size());//15 System.out.println(binTree.getLast());//15 //创建一个完全二叉树 binTree = new BinTree(); binTree.createFullBiTree(14); System.out.println(binTree.size());//14 System.out.println(binTree.getLast());//7 //创建一棵非完全二叉树 binTree = new BinTree(); int[] nums = new int[] { 1, 2, 3, 4, 0, 0, 5, 0, 6, 0, 0, 0, 0, 7, 8 }; binTree.createBinTree(nums); System.out.println(binTree.size());//8 System.out.println(binTree.getLast());//8 } }  package tree.bintree; /** * 二叉树的三种 内部 遍历:前序、中序、后序 * 但不管是哪种方式,左子树的遍历在右子树的遍历之前遍历是这有三种遍历方式都 * 必须遵循的约定 * @author jzj * @date 2009-12-23 */ public class BinTreeInOrder extends BinTree { /** * 节点访问者,可根据需要重写visit方法 */ static abstract class Visitor { void visit(Object ele) { System.out.print(ele + " "); } } public void preOrder(Visitor v) { preOrder(v, root); } /** * 树的前序递归遍历 pre=prefix(前缀) * @param node 要遍历的节点 */ private void preOrder(Visitor v, Entry node) { //如果传进来的节点不为空,则遍历,注,叶子节点的子节点为null if (node != null) { v.visit(node.elem);//先遍历父节点 preOrder(v, node.left);//再遍历左节点 preOrder(v, node.right);//最后遍历右节点 } } public void inOrder(Visitor v) { inOrder(v, root); } /** * 树的中序递归遍历 in=infix(中缀) * @param node 要遍历的节点 */ private void inOrder(Visitor v, Entry node) { //如果传进来的节点不为空,则遍历,注,叶子节点的子节点为null if (node != null) { inOrder(v, node.left);//先遍历左节点 v.visit(node.elem);//再遍历父节点 inOrder(v, node.right);//最后遍历右节点 } } public void postOrder(Visitor v) { postOrder(v, root); } /** * 树的后序递归遍历 post=postfix(后缀) * @param node 要遍历的节点 */ private void postOrder(Visitor v, Entry node) { //如果传进来的节点不为空,则遍历,注,叶子节点的子节点为null if (node != null) { postOrder(v, node.left);//先遍历左节点 postOrder(v, node.right);//再遍历右节点 v.visit(node.elem);//最后遍历父节点 } } //测试 public static void main(String[] args) { //创建二叉树 int[] nums = new int[] { 1, 2, 3, 4, 0, 0, 5, 0, 6, 0, 0, 0, 0, 7, 8 }; BinTreeInOrder treeOrder = new BinTreeInOrder(); treeOrder.createBinTree(nums); System.out.print("前序遍历 - "); treeOrder.preOrder(new Visitor() { }); System.out.println(); System.out.print("中序遍历 - "); treeOrder.inOrder(new Visitor() { }); System.out.println(); System.out.print("后序遍历 - "); treeOrder.postOrder(new Visitor() { }); /* * output: * 前序遍历 - 1 2 4 6 3 5 7 8 * 中序遍历 - 4 6 2 1 3 7 5 8 * 后序遍历 - 6 4 2 7 8 5 3 1 */ } }  package tree.bintree; import java.util.Iterator; import java.util.LinkedList; import java.util.Stack; /** * 二叉树的外部遍历:深度优先(先根)、广度(层次)优先遍历 * * @author jzj * @date 2009-12-23 */ public class BinTreeOutOrder extends BinTree { /** * 二叉树深序优先遍历(即二叉树的先根遍历)迭代器,外部可以使用该迭代器 * 进行非递归的遍历,这是一种在二叉树结构外部的一种遍历算法,它没有使用 * 二叉树本身的结构特点(左右子树递归)进行递归遍历 * @author jzj */ private class DepthOrderIterator implements Iterator { //栈里存放的是每个节点 private Stack stack = new Stack(); public DepthOrderIterator(Entry node) { //根入栈,但在放入左右子节点前会马上出栈,即根先优于左右子节点访问 stack.push(node); } //是否还有下一个元素 public boolean hasNext() { if (stack.isEmpty()) { return false; } return true; } //取下一个元素 public Entry next() { if (hasNext()) { //取栈顶元素 Entry treeNode = (Entry) stack.pop();//先访问根 if (treeNode.right != null) { stack.push(treeNode.right);//再放入右子节点 } if (treeNode.left != null) { stack.push(treeNode.left);//最后放入左子节点,但访问先于右节点 } // 返回遍历得到的节点 return treeNode; } else { // 如果栈为空 return null; } } public void remove() { throw new UnsupportedOperationException(); } } /** * 向外界提供先根遍历迭代器 * @return Iterator 返回先根遍历迭代器 */ public Iterator createPreOrderItr() { return new DepthOrderIterator(root); } /** * 二叉树广度优先遍历迭代器,外部可以使用该迭代器 * 进行非递归的遍历,这是一种在二叉树结构外部的一种遍历算法,它没有使用 * 二叉树本身的结构特点(左右子树递归)进行递归遍历 * @author jzj */ private class LevelOrderIterator implements Iterator { //使用队列结构实现层次遍历,队列里存储的为节点 private LinkedList queue = new LinkedList(); public LevelOrderIterator(Entry node) { if (node != null) { //将根入队 queue.addLast(node); } } //是否还有下一个元素 public boolean hasNext() { if (queue.isEmpty()) { return false; } return true; } //取下一个元素 public Entry next() { if (hasNext()) { //取栈顶迭元素 Entry treeNode = (Entry) queue.removeFirst(); if (treeNode.left != null) {//如果有左子树,加入有序列表中 queue.addLast(treeNode.left); } if (treeNode.right != null) {//如果有右子树,加入有序列表中 queue.addLast(treeNode.right); } // 返回遍历得到的节点 return treeNode; } else { // 如果队列为空 return null; } } public void remove() { throw new UnsupportedOperationException(); } } /** * 向外界提供广度优先迭代器 * @return Iterator 返回遍历迭代器 */ public Iterator createLayerOrderItr() { return new LevelOrderIterator(root); } public static void main(String[] args) { //创建一棵满二叉树 BinTreeOutOrder treeOrder = new BinTreeOutOrder(); treeOrder.createFullBiTree(15); Iterator preOrderItr = treeOrder.createPreOrderItr(); System.out.print("深度优先(先根)遍历 - "); while (preOrderItr.hasNext()) { System.out.print(((Entry) preOrderItr.next()).elem + " "); } System.out.println(); System.out.print("广度优先(层次)遍历 - "); Iterator layerOrderItr = treeOrder.createLayerOrderItr(); while (layerOrderItr.hasNext()) { System.out.print(((Entry) layerOrderItr.next()).elem + " "); } /* * output: * 深度优先(先根)遍历 - 1 2 4 8 9 5 10 11 3 6 12 13 7 14 15 * 广度优先(层次)遍历 - 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 */ } }  package tree.bintree; /** * * 可回溯的二叉树 * 二叉树的非递归遍历 * * @author jzj * @date 2009-12-23 */ public class BackBinTree {// Bin=Binary(二进位的, 二元的) protected Entry root;//根 private int size;//树的节点数 /** * 树的节点结构 * @author jzj * @date 2009-12-23 */ private static class Entry { int elem;//数据域,这里为了测试,就作为节点编号吧 Entry paraent;//父节点 Entry left;//左节点 Entry right;//右节点 //构造函数只有两个参数,左右节点是调用add方法时设置 public Entry(int elem, Entry parent) { this.elem = elem; this.paraent = parent; } } /** * 查找前序遍历(根左右)直接后继节点 * * 以非递归 根左右 的方式遍历树 * * @param e 需要查找哪个节点的直接后继节点 * @return Entry 前序遍历直接后继节点 */ public Entry preOrderSuccessor(Entry e) { if (e == null) { return null; }//如果左子树不为空,则直接后继为左子节点 else if (e.left != null) {//先看左子节点是否为空 return e.left;//如果不为空,则直接后继为左子节点 }//否则如果右子树不为空,则直接后继为右子节点 else if (e.right != null) {//如果左子节点为空,则看右子节点是否为空 return e.right;//如果右子节点不为空,则返回 }//左右子节点都为空的情况下 else { Entry s = e.paraent; Entry c = e; /* * 一直向上,直到c是s的左子树,且s的右子树不为空。请试着找一下36与68节点的 * 直接后继节点,36的应该是75,而68则没有后继节点了 * * 50 * /\ * 37 75 * / / * 25 61 * /\ /\ * 15 30 55 68 * /\ \ * 28 32 59 * \ * 36 */ while (s != null && (c == s.right || s.right == null)) { c = s; s = s.paraent; } //退出循环时 s 可以为null,比如查找 68 节点的直接后继时退出循环时s=null if (s == null) { return null; } else { return s.right; } } } /** * 查找前序遍历(根左右)直接前驱节点 * * 以非递归 右左根 的方式遍历树 * * @param e 需要查找哪个节点的直接前驱节点 * @return Entry 前序遍历直接前驱节点 */ public Entry preOrderAncestor(Entry e) { if (e == null) { return null; }//如果节点为父节点的左节点,则父节点就是直接前驱节点 else if (e.paraent != null && e == e.paraent.left) { return e.paraent; }//如果节点为父节点的右节点 else if (e.paraent != null && e == e.paraent.right) { Entry s = e.paraent;//前驱节点默认为父节点 if (s.left != null) {//如果父节点没有左子,前驱节点就为父节点 s = s.left;//如果父节点的左子节点不空,则初始为父节点左子节点 /* * 只要父节点左子节点还有子节点,则前驱节点要从其子树中找。请试着找 * 一下75直接前驱节点,应该是36 * * 50 * /\ * 37 75 * / / * 25 61 * /\ /\ * 15 30 55 68 * /\ \ * 28 32 59 * \ * 36 */ while (s.left != null || s.right != null) { //在父节点的左子节点的子树中查找时,一定要先向右边拐 if (s.right != null) { s = s.right; } else {//如果右边没有,然后才能向左边拐 s = s.left; } } } return s; } else {//如果是根节点,则没有直接前驱节点了 return null; } } /** * 查找后序遍历(左右根)直接后继节点 * * 以非递归 左右根 的方式遍历树 * * @param e 需要查找哪个节点的直接后继节点 * @return Entry 后序遍历直接后继节点 */ public Entry postOrderSuccessor(Entry e) { if (e == null) { return null; }//如果节点为父节点的右子节点,则父节点就是直接后继节点 else if (e.paraent != null && e == e.paraent.right) { return e.paraent; }//如果节点为父节点的左子节点 else if (e.paraent != null && e == e.paraent.left) { Entry s = e.paraent;//后继节点默认为父节点 if (s.right != null) {//如果父节点没有右子,后继节点就为父节点 s = s.right;//如果父节点的右子节点不空,则初始为父节点右子节点 /* * 只要父节点右子节点还有子节点,则后断节点要从其子树中找, * 如15的后继节点为28 * 50 * /\ * 37 75 * / / * 25 61 * /\ /\ * 15 30 55 68 * /\ \ * 28 32 59 * \ * 36 */ while (s.left != null || s.right != null) { //在父节点的右子节点的子树中查找时,一定要先向左边拐 if (s.left != null) { s = s.left; } else {//如果左边没有,然后才能向右边拐 s = s.right; } } } return s; } else { //如果是根节点,则没有后继节点了 return null; } } /** * 查找后序遍历(左右根)直接前驱节点 * * 以非递归 根右左 的方式遍历树 * * @param e 需要查找哪个节点的直接前驱节点 * @return Entry 后序遍历直接前驱节点 */ public Entry postOrderAncestor(Entry e) { if (e == null) { return null; }//如果右子树不为空,则直接前驱为右子节点 else if (e.right != null) {//先看右子节点是否为空 return e.right;//如果不为空,则直接后继为右子节点 }//否则如果左子树不为空,则直接前驱为左子节点 else if (e.left != null) { return e.left; }//左右子节点都为空的情况下 else { Entry s = e.paraent; Entry c = e; /* * 一直向上,直到c是s的右子树,且s的左子树不为空。请试着找一下59与15节点的 * 直接后继节点,59的应该是37,而15则没有后继节点了 * * 50 * /\ * 37 75 * / / * 25 61 * /\ /\ * 15 30 55 68 * /\ \ * 28 32 59 * \ * 36 */ while (s != null && (c == s.left || s.left == null)) { c = s; s = s.paraent; } if (s == null) { return null; } else { return s.left; } } } /** * 查找中序遍历(左根右)直接后继节点 * * 以非递归 左根右 的方式遍历树 * * @param e 需要查找哪个节点的直接后继节点 * @return Entry 中序遍历直接后继节点 */ public Entry inOrderSuccessor(Entry e) { if (e == null) { return null; }//如果待找的节点有右子树,则在右子树上查找 else if (e.right != null) { //默认后继节点为右子节点(如果右子节点没有左子树时即为该节点) Entry p = e.right; while (p.left != null) { //注,如果右子节点的左子树不为空,则在左子树中查找,且后面找时要一直向左拐 p = p.left; } return p; }//如果待查节点没有右子树,则要在祖宗节点中查找后继节点 else { //默认后继节点为父节点(如果待查节点为父节点的左子树,则后继为父节点) Entry p = e.paraent; Entry current = e;//当前节点,如果其父不为后继,则下次指向父节点 //如果待查节点为父节点的右节点时,继续向上找,一直要找到current为左子节点,则s才是后继 while (p != null && current == p.right) { current = p; p = p.paraent; } return p; } } /** * 查找中序遍历(左根右)直接前驱节点 * * 以非递归 右根左 的方式遍历树 * * @param e 需要查找哪个节点的直接前驱节点 * @return Entry 中序遍历直接前驱节点 */ public Entry inOrderAncestor(Entry e) { if (e == null) { return null; }//如果待找的节点有左子树,则在在子树上查找 else if (e.left != null) { //默认直接前驱节点为左子节点(如果左子节点没有右子树时即为该节点) Entry p = e.left; while (p.right != null) { //注,如果左子节点的右子树不为空,则在右子树中查找,且后面找时要一直向右拐 p = p.right; } return p; }//如果待查节点没有左子树,则要在祖宗节点中查找前驱节点 else { //默认前驱节点为父节点(如果待查节点为父节点的右子树,则前驱为父节点) Entry p = e.paraent; Entry current = e;//当前节点,如果其父不为前驱,则下次指向父节点 //如果待查节点为父节点的左节点时,继续向上找,一直要找到current为p的右子节点,则s才是前驱 while (p != null && current == p.left) { current = p; p = p.paraent; } return p; } } /** * 查找指定的节点 * @param num * @return Entry */ public Entry getEntry(int num) { return getEntry(root, num); } /** * 使用树的先序遍历递归方式查找指定的节点 * * @param entry * @param num * @return */ private Entry getEntry(Entry entry, int num) { //如果找到,则停止后续搜索,并把查找到的节点返回给上层调用者 if (entry.elem == num) {//1、先与父节点比对 return entry; } Entry tmp = null; if (entry.left != null) {//2、再在左子树上找 tmp = getEntry(entry.left, num); //如果左子树上找到,返回并停止查找,否则继续在后续节点中找 if (tmp != null) { //节点在左子树中找到,返回给上层调用者 return tmp; } } if (entry.right != null) {//3、否则在右子树上找 tmp = getEntry(entry.right, num); //如果右子树上找到,返回并停止查找,否则继续在后续节点中找 if (tmp != null) { //节点在右子树中找到,返回给上层调用者 return tmp; } } //当前比较节点 entry 子树为空或不为空时没有找到,直接返回给上层调用者null return null; } /** * 根据给定的数组创建一棵树,这个棵树可以是完全二叉树也可是普通二叉树 * 数组中为0的表示不创建该位置上的节点 * @param nums 数组中指定了要创建的节点的编号,如果为0,表示不创建 */ public void createBinTree(int[] nums) { root = recurCreateBinTree(nums, null, 0); } /** * 递归创建二叉树 * @param nums 数组中指定了要创建的节点的编号,如果为0,表示不创建 * @param paraent 父节点 * @param index 需要使用数组中的哪个元素创建节点,如果为元素为0,则不创建 * @return Entry 返回创建的节点,最终会返回树的根节点 */ private Entry recurCreateBinTree(int[] nums, Entry pararent, int index) { //指定索引上的编号不为零上才需创建节点 if (nums[index] != 0) { size++; Entry root = new Entry(nums[index], pararent);//根节点 //如果有左子树则创建左子树 if ((index + 1) * 2 <= nums.length) { root.left = (Entry) recurCreateBinTree(nums, root, (index + 1) * 2 - 1); //如果还可以创建右子树,则创建 if ((index + 1) * 2 + 1 <= nums.length) { root.right = (Entry) recurCreateBinTree(nums, root, (index + 1) * 2); } } return (Entry) root; } return null; } public int size() { return size; } //测试 public static void main(String[] args) { //创建一棵非完全二叉树 BackBinTree binTree = new BackBinTree(); /* * 50 * /\ * 37 75 * / / * 25 61 * /\ /\ * 15 30 55 68 * /\ \ * 28 32 59 * \ * 36 */ int[] nums = new int[] { 50, 37, 75, 25, 0, 61, 0, 15, 30, 0, 0, 55, 68, 0, 0, 0, 0, 28, 32, 0, 0, 0, 0, 0, 59, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 36 }; binTree.createBinTree(nums); Entry entry = binTree.getEntry(50); System.out.print("根左右(先序遍历)- "); while (entry != null) { System.out.print(entry.elem + " "); entry = binTree.preOrderSuccessor(entry); } System.out.println(); entry = binTree.getEntry(68); System.out.print("右左根(先序的逆)- "); while (entry != null) { System.out.print(entry.elem + " "); entry = binTree.preOrderAncestor(entry); } System.out.println(); entry = binTree.getEntry(15); System.out.print("左右根(后序遍历)- "); while (entry != null) { System.out.print(entry.elem + " "); entry = binTree.postOrderSuccessor(entry); } System.out.println(); entry = binTree.getEntry(50); System.out.print("根右左(后序的逆)- "); while (entry != null) { System.out.print(entry.elem + " "); entry = binTree.postOrderAncestor(entry); } System.out.println(); entry = binTree.getEntry(15); System.out.print("左根右(中序遍历)- "); while (entry != null) { System.out.print(entry.elem + " "); entry = binTree.inOrderSuccessor(entry); } System.out.println(); entry = binTree.getEntry(75); System.out.print("右根左(中序的逆)- "); while (entry != null) { System.out.print(entry.elem + " "); entry = binTree.inOrderAncestor(entry); } System.out.println(); /* * output: * 根左右(先序遍历)- 50 37 25 15 30 28 32 36 75 61 55 59 68 * 右左根(先序的逆)- 68 59 55 61 75 36 32 28 30 15 25 37 50 * 左右根(后序遍历)- 15 28 36 32 30 25 37 59 55 68 61 75 50 * 根右左(后序的逆)- 50 75 61 68 55 59 37 25 30 32 36 28 15 * 左根右(中序遍历)- 15 25 28 30 32 36 37 50 55 59 61 68 75 * 右根左(中序的逆)- 75 68 61 59 55 50 37 36 32 30 28 25 15 */ } }

下载文档到电脑,查找使用更方便

文档的实际排版效果,会与网站的显示效果略有不同!!

需要 11 金币 [ 分享文档获得金币 ] 1 人已下载

下载文档