树的一些操作

  1 package test;
  2 
  3 import java.util.ArrayList;
  4 import java.util.Iterator;
  5 import java.util.LinkedList;
  6 import java.util.List;
  7 import java.util.Stack;
  8 import java.util.Vector;
  9 
 10 public class TreeOperator {
 11     public static void preOrder(TreeNode node) {
 12         if (node != null) {
 13             System.out.print(node.data + " ");
 14             preOrder(node.left);
 15             preOrder(node.right);
 16         }
 17     }
 18 
 19     public static void BFSTreeNode(TreeNode node) {
 20         if (node == null) {
 21             System.out.println("TreeNode is null");
 22         }
 23         LinkedList<TreeNode> linkedList = new LinkedList<TreeNode>();
 24         linkedList.push(node);
 25         while (!linkedList.isEmpty()) {
 26             TreeNode n = linkedList.removeFirst();
 27             System.out.print(n.data + " ");
 28             if (n.left != null) {
 29                 linkedList.add(n.left);
 30             }
 31             if (n.right != null) {
 32                 linkedList.add(n.right);
 33             }
 34         }
 35         System.out.println();
 36     }
 37 
 38     public static int getTreeNodeDepth(TreeNode node) {
 39         if (node == null)
 40             return 0;
 41         return 1 + Math.max(getTreeNodeDepth(node.left),
 42                 getTreeNodeDepth(node.right));
 43     }
 44 
 45     public static boolean IsBalanced(TreeNode node) {
 46         boolean res = true;
 47         if (node == null) {
 48             return res;
 49         }
 50         int leftdepth = getTreeNodeDepth(node.left);
 51         int rightdepth = getTreeNodeDepth(node.right);
 52         if (Math.abs(leftdepth - rightdepth) > 1)
 53             return false;
 54         return IsBalanced(node.left) && IsBalanced(node.right);
 55     }
 56 
 57     // 判断是否是子树
 58     /**
 59      * @param root
 60      * @param node
 61      *            子树
 62      * @return
 63      */
 64     public static boolean isSubTreeNode(TreeNode root, TreeNode node) {
 65         if ((root == null && node != null) || (root != null && node == null)) {
 66             return false;
 67         }
 68         if (root == null && node == null) {
 69             return true;
 70         }
 71         return isSubTreeNodeCore(root, node);
 72     }
 73 
 74     public static boolean isSubTreeNodeCore(TreeNode root, TreeNode node) {
 75         boolean result = false;
 76         if (root.data == node.data) {
 77             result = checkAllNodes(root, node);
 78         }
 79         if (!result && root.left != null) {
 80             result = isSubTreeNodeCore(root.left, node);
 81         }
 82         if (!result && root.right != null) {
 83             result = isSubTreeNodeCore(root.right, node);
 84         }
 85         return result;
 86     }
 87 
 88     public static boolean checkAllNodes(TreeNode root, TreeNode node) {
 89         if (node == null)
 90             return true;
 91         if (root == null)
 92             return false;
 93         if (root.data == node.data) {
 94             return checkAllNodes(root.left, node.left)
 95                     && checkAllNodes(root.right, node.right);
 96         } else {
 97             return false;
 98         }
 99     }
100 
101     public static void printByLayer(TreeNode node) {
102         if (node == null) {
103             System.out.println("TreeNode is null");
104         }
105         Vector<TreeNode> vector = new Vector<TreeNode>();
106         LinkedList<TreeNode> linkedList = new LinkedList<TreeNode>();
107         linkedList.add(node);
108         vector.add(node);
109         int start = 0;
110         int end = vector.size();
111         while (start < vector.size()) {
112             while (start < end) {
113                 node = vector.get(start);
114                 System.out.print(vector.get(start).data + " ");
115                 start++;
116                 if (node.left != null)
117                     vector.add(node.left);
118                 if (node.right != null)
119                     vector.add(node.right);
120             }
121             end = vector.size();
122             System.out.println();
123         }
124     }
125 
126     // 打印从根到每个叶子的路径
127     public static void getAllPath(TreeNode root) {
128         Stack<TreeNode> stack = new Stack<TreeNode>();
129         getAllPath(root, stack);
130     }
131 
132     public static void getAllPath(TreeNode root, Stack s) {
133         if (root != null)
134             s.push(root);
135         if (root.left == null && root.right == null) {
136             Iterator<TreeNode> it = s.iterator();
137             while (it.hasNext()) {
138                 System.out.print(it.next().data + " ");
139             }
140             System.out.println();
141         }
142         if (root.left != null) {
143             getAllPath(root.left, s);
144         }
145         if (root.right != null) {
146             getAllPath(root.right, s);
147         }
148         s.pop();
149     }
150 
151     public static List getNodePath(TreeNode root, TreeNode node) {
152         List list = new ArrayList<TreeNode>();
153         getNodePath(root, node, list);
154         return list;
155     }
156     public static void getNodePath(TreeNode root, TreeNode node,
157             List<TreeNode> list) {
158         if (root != null)
159             list.add(root);
160         if (root == node) {
161             for (TreeNode n : list) {
162                 System.out.print(n.data + " ");
163             }
164             System.out.println();
165         }
166         if (root!=null&&hasNode(root.left, node) == true) {
167             getNodePath(root.left, node, list);
168         }
169         if (root!=null&&hasNode(root.right, node) == true) {
170             getNodePath(root.right, node, list);
171         }
172     }
173     public static boolean hasNode(TreeNode root, TreeNode node) {
174         if (root == node) {
175             return true;
176         }
177         boolean lefthas = false;
178         boolean righthas = false;
179         if (root!=null&&root.left != null) {
180             lefthas = hasNode(root.left, node);
181         }
182         if (root!=null&&lefthas == false && root.right != null) {
183             righthas = hasNode(root.right, node);
184         }
185         return lefthas || righthas;
186     }
187     public static TreeNode getCommonParent(TreeNode root,TreeNode node1 ,TreeNode node2){
188         TreeNode commonParent=null;
189         List<TreeNode> listnode1=getNodePath(root,node1);
190         List<TreeNode> listnode2=getNodePath(root,node2);
191         int len1=listnode1.size();
192         int len2=listnode2.size();
193         int len=len1>len2?len1:len2;
194         int i=0;
195         for(;i<len1&&i<len2;i++){
196             if(listnode1.get(i).data!=listnode2.get(i).data){
197                 break;
198             }
199         }
200         if(i-1>0){
201             commonParent =listnode1.get(i-1);
202         }else if(i==1&&listnode1.get(0).data==listnode2.get(0).data){
203             commonParent=listnode1.get(0);
204         }
205         return commonParent;
206     }
207     public static void main(String[] args) {
208         TreeNode root = new TreeNode(1);
209         TreeNode t1 = new TreeNode(8);
210         TreeNode t2 = new TreeNode(7);
211         TreeNode t3 = new TreeNode(9);
212         TreeNode t4 = new TreeNode(2);
213         TreeNode t5 = new TreeNode(4);
214         TreeNode t6 = new TreeNode(7);
215         root.left = t1;
216         root.right = t2;
217         t1.left = t3;
218         t1.right = t4;
219         t4.left = t5;
220         t4.right = t6;
221         preOrder(root);
222         System.out.println();
223         int depth = getTreeNodeDepth(root);
224         System.out.println(depth);
225         System.out.println("-------------------------------------");
226         TreeNode root1 = new TreeNode(8);
227         TreeNode n1 = new TreeNode(9);
228         TreeNode n2 = new TreeNode(2);
229         root1.left = n1;
230         root1.right = n2;
231         boolean isbalanced = IsBalanced(root1);
232         System.out.println(isbalanced);
233         System.out.println("-------------------------------------");
234         BFSTreeNode(root);
235         System.out.println("-------------------------------------");
236         printByLayer(root);
237         System.out.println("-------------------------------------");
238         boolean res = isSubTreeNode(root, root1);
239         System.out.println(res);
240         System.out.println("----------------所有路径---------------");
241         getAllPath(root);
242         TreeNode t7 = new TreeNode(7);
243         System.out.println(hasNode(root, t5));
244         System.out.println("---------------------------------------");
245         List<TreeNode> list = getNodePath(root, t5);
246         System.out.println("---------------------------------------");
247         TreeNode node=getCommonParent(root,root,root);
248         System.out.println(node.data);
249         System.out.println(IsBalanced(t4));
250     }
251 
252 }