MyException - 我的异常网
当前位置:我的异常网» 数据结构与算法 » [数据结构与算法]二叉树的多种遍历模式

[数据结构与算法]二叉树的多种遍历模式

www.MyException.Cn  网友分享于:2015-02-15  浏览:0次
[数据结构与算法]二叉树的多种遍历方式
声明:原创作品转载时请注明文章来自SAP师太技术博客:www.cnblogs.com/jiangzhengjun并以超链接形式标明文章原始出处否则将追究法律责任!原文链接:http://www.cnblogs.com/jiangzhengjun/p/4289830.html

一、数据结构分类

(一)按逻辑结构

  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。

.

三、二叉树的遍历

遍历是按某种策略访问树中的每个节点,且仅访问一次。

(一) 二叉树结构实现

 

  1 package tree.bintree;
  2 
  3 /**
  4  * 创建 非完全二叉树、完全二叉树、满二叉树
  5  *
  6  * 由于二叉树的节点增加没有什么规则,所以这里只是简单的使用了递一
  7  * 次性把整棵树创建出来,而没有设计出一个一个添加节点的方法与删除
  8  * 
  9  * @author jzj
 10  * @date 2009-12-23
 11  */
 12 public class BinTree {// Bin=Binary(二进位的, 二元的)
 13 
 14     protected Entry root;//
 15     private int size;//树的节点数
 16 
 17     /**
 18      * 树的节点结构
 19      * @author jzj
 20      * @date 2009-12-23
 21      */
 22     protected static class Entry {
 23         int elem;//数据域,这里我们作为编号
 24         Entry left;//左子树
 25         Entry right;//右子树
 26 
 27         public Entry(int elem) {
 28             this.elem = elem;
 29         }
 30 
 31         public String toString() {
 32             return " number=" + elem;
 33         }
 34     }
 35 
 36     /**
 37      * 根据给定的节点数创建一个完全二叉树或是满二叉树
 38      * @param nodeCount 要创建节点总数
 39      */
 40     public void createFullBiTree(int nodeCount) {
 41         root = recurCreateFullBiTree(1, nodeCount);
 42     }
 43 
 44     /**
 45      * 递归创建完全二叉树
 46      * @param num 节点编号
 47      * @param nodeCount 节点总数
 48      * @return TreeNode 返回创建的节点
 49      */
 50     private Entry recurCreateFullBiTree(int num, int nodeCount) {
 51         size++;
 52         Entry rootNode = new Entry(num);//根节点
 53         //如果有左子树则创建左子树
 54         if (num * 2 <= nodeCount) {
 55             rootNode.left = recurCreateFullBiTree(num * 2, nodeCount);
 56             //如果还可以创建右子树,则创建
 57             if (num * 2 + 1 <= nodeCount) {
 58                 rootNode.right = recurCreateFullBiTree(num * 2 + 1, nodeCount);
 59             }
 60         }
 61         return (Entry) rootNode;
 62     }
 63 
 64     /**
 65      * 根据给定的数组创建一棵树,这个棵树可以是完全二叉树也可是普通二叉树
 66      * 数组中为0的表示不创建该位置上的节点
 67      * @param nums 数组中指定了要创建的节点的编号,如果为0,表示不创建
 68      */
 69     public void createBinTree(int[] nums) {
 70         root = recurCreateBinTree(nums, 0);
 71     }
 72 
 73     /**
 74      * 递归创建二叉树
 75      * @param nums 数组中指定了要创建的节点的编号,如果为0,表示不创建
 76      * @param index 需要使用数组中的哪个元素创建节点,如果为元素为0,则不创建
 77      * @return TreeNode 返回创建的节点,最终会返回树的根节点
 78      */
 79     private Entry recurCreateBinTree(int[] nums, int index) {
 80         //指定索引上的编号不为零上才需创建节点
 81         if (nums[index] != 0) {
 82             size++;
 83             Entry rootNode = new Entry(nums[index]);//根节点
 84             //如果有左子树则创建左子树
 85             if ((index + 1) * 2 <= nums.length) {
 86                 rootNode.left = (Entry) recurCreateBinTree(nums, (index + 1) * 2 - 1);
 87                 //如果还可以创建右子树,则创建
 88                 if ((index + 1) * 2 + 1 <= nums.length) {
 89                     rootNode.right = (Entry) recurCreateBinTree(nums, (index + 1) * 2);
 90                 }
 91             }
 92             return (Entry) rootNode;
 93         }
 94         return null;
 95 
 96     }
 97 
 98     public int size() {
 99         return size;
100     }
101 
102     //取树的最左边的节点
103     public int getLast() {
104         Entry e = root;
105         while (e.right != null) {
106             e = e.right;
107         }
108         return e.elem;
109     }
110 
111     //测试
112     public static void main(String[] args) {
113 
114         //创建一个满二叉树
115         BinTree binTree = new BinTree();
116         binTree.createFullBiTree(15);
117         System.out.println(binTree.size());//15
118         System.out.println(binTree.getLast());//15
119 
120         //创建一个完全二叉树
121         binTree = new BinTree();
122         binTree.createFullBiTree(14);
123         System.out.println(binTree.size());//14
124         System.out.println(binTree.getLast());//7
125 
126         //创建一棵非完全二叉树
127         binTree = new BinTree();
128         int[] nums = new int[] { 1, 2, 3, 4, 0, 0, 5, 0, 6, 0, 0, 0, 0, 7, 8 };
129         binTree.createBinTree(nums);
130         System.out.println(binTree.size());//8
131         System.out.println(binTree.getLast());//8
132 
133     }
134 }

 

(二)利用二叉树本身特点进行递归遍历(属内部遍历)

由于二叉树所具有的递归性质,一棵非空的二叉树可以看作是由根节点、左子树和右 子树3部分构成,因为若能依次遍历这3部分的信息,也就遍历了整个二叉树。按照左子树的遍历在右子树的遍历之前进行的约定,根据访问根节点位置的不同,可 以得到二叉的前序、中序、后序3种遍历方法。

 

 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 }

 

(三)二叉树的非递归遍历(属外部遍历)

1、利用栈与队列对二叉树进行非递归遍历

  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 }

2、利用二叉树节点的父节点指针进行非递归遍历

要想采用非递归的方法遍历树,又不借助于前面的队列与栈,我们需要该树是一棵可回溯的二叉树,即从子节点要能够知道他的父节点及祖先节点,与前面的二叉树不同的是,树的节点结构体中多一个指向父的节点指针,这样外界可以以非递归的方式来遍历二叉树了 。

 

  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 }

文章评论

当下全球最炙手可热的八位少年创业者
当下全球最炙手可热的八位少年创业者
Java程序员必看电影
Java程序员必看电影
科技史上最臭名昭著的13大罪犯
科技史上最臭名昭著的13大罪犯
为什么程序员都是夜猫子
为什么程序员都是夜猫子
Web开发人员为什么越来越懒了?
Web开发人员为什么越来越懒了?
鲜为人知的编程真相
鲜为人知的编程真相
看13位CEO、创始人和高管如何提高工作效率
看13位CEO、创始人和高管如何提高工作效率
我跳槽是因为他们的显示器更大
我跳槽是因为他们的显示器更大
程序猿的崛起——Growth Hacker
程序猿的崛起——Growth Hacker
做程序猿的老婆应该注意的一些事情
做程序猿的老婆应该注意的一些事情
程序员最害怕的5件事 你中招了吗?
程序员最害怕的5件事 你中招了吗?
Web开发者需具备的8个好习惯
Web开发者需具备的8个好习惯
旅行,写作,编程
旅行,写作,编程
什么才是优秀的用户界面设计
什么才是优秀的用户界面设计
老美怎么看待阿里赴美上市
老美怎么看待阿里赴美上市
写给自己也写给你 自己到底该何去何从
写给自己也写给你 自己到底该何去何从
每天工作4小时的程序员
每天工作4小时的程序员
10个帮程序员减压放松的网站
10个帮程序员减压放松的网站
聊聊HTTPS和SSL/TLS协议
聊聊HTTPS和SSL/TLS协议
10个调试和排错的小建议
10个调试和排错的小建议
老程序员的下场
老程序员的下场
中美印日四国程序员比较
中美印日四国程序员比较
程序员周末都喜欢做什么?
程序员周末都喜欢做什么?
“懒”出效率是程序员的美德
“懒”出效率是程序员的美德
 程序员的样子
程序员的样子
代码女神横空出世
代码女神横空出世
如何区分一个程序员是“老手“还是“新手“?
如何区分一个程序员是“老手“还是“新手“?
初级 vs 高级开发者 哪个性价比更高?
初级 vs 高级开发者 哪个性价比更高?
程序员都该阅读的书
程序员都该阅读的书
如何成为一名黑客
如何成为一名黑客
我是如何打败拖延症的
我是如何打败拖延症的
5款最佳正则表达式编辑调试器
5款最佳正则表达式编辑调试器
亲爱的项目经理,我恨你
亲爱的项目经理,我恨你
60个开发者不容错过的免费资源库
60个开发者不容错过的免费资源库
程序员的鄙视链
程序员的鄙视链
程序员必看的十大电影
程序员必看的十大电影
十大编程算法助程序员走上高手之路
十大编程算法助程序员走上高手之路
一个程序员的时间管理
一个程序员的时间管理
程序员应该关注的一些事儿
程序员应该关注的一些事儿
要嫁就嫁程序猿—钱多话少死的早
要嫁就嫁程序猿—钱多话少死的早
团队中“技术大拿”并非越多越好
团队中“技术大拿”并非越多越好
为啥Android手机总会越用越慢?
为啥Android手机总会越用越慢?
漫画:程序员的工作
漫画:程序员的工作
“肮脏的”IT工作排行榜
“肮脏的”IT工作排行榜
我的丈夫是个程序员
我的丈夫是个程序员
软件开发程序错误异常ExceptionCopyright © 2009-2015 MyException 版权所有