二叉树题集

1.二叉树一般定义

 1 package algorithm;
 2 import java.util.Stack;
 3 
 4 public class binaryTree {
 5     public static void main(String[] args) {
 6         TreeNode root = new TreeNode(1);
 7         for (int i = 0; i < 10; i++) {
 8             insert(root, (int)(Math.random()*100));
 9         }
10         inOrderTraversal2(root);
11     }
12     //往二叉查找树中插入结点  
13     //插入的话，可能要改变根结点的地址，所以传的是二级指针  
14     public static void insert(TreeNode root,int data)  
15     {  
16         //初始化插入结点  
17         TreeNode p= new TreeNode();  
18         p.data=data;  
19         p.left=p.right=p.parent=null;  
20         //空树时，直接返回
21         if((root)==null)
22             return;  
23         //插入到当前结点（root）的左孩子  
24         if((root).left == null && (root).data > data){  
25             p.parent=(root);  
26             (root).left=p;  
27             return;  
28         }  
29         //插入到当前结点（root）的右孩子  
30         if((root).right == null && (root).data < data){  
31             p.parent=(root);  
32             (root).right=p;  
33             return;  
34         }  
35         if((root).data > data)  
36             insert((root).left,data);  
37         else if((root).data < data)  
38             insert((root).right,data);  
39         else  
40             return;  
41     }  
42       
43     //查找元素,找到返回关键字的结点指针，没找到返回null  
44     public static TreeNode search(TreeNode root,int data)  
45     {  
46         if(root == null)  
47             return null;  
48         if(data > root.data) //查找右子树  
49             return search(root.right,data);  
50         else if(data < root.data) //查找左子树  
51             return search(root.left,data);  
52         else  
53             return root;  
54     }  
55     public static class TreeNode
56     {
57         int data;
58         TreeNode left;
59         TreeNode right;
60         TreeNode parent;
61         public TreeNode(int i){
62             data = i;
63         }
64         public TreeNode(){
65         }
66     };
67 }

View Code

2.中序遍历非递归

 1 public static void inOrderTraversal2(TreeNode node){
 2     if(node == null)
 3         return;
 4     Stack<TreeNode> stack = new Stack<TreeNode>();
 5     TreeNode p = node;
 6     while (p != null || stack.size()!=0) {
 7         while (p != null) {
 8             stack.push(p);
 9             p = p.left;
10         }
11         if (stack.size()!=0) {
12             p = stack.pop();
13             System.out.println(p.data);
14             p = p.right;
15         }
16     }
17 }

3.求出二叉树中最远的两个节点

　　分析：二叉树的一般解法，就是分析问题使之分解，然后思考递归的方式。->就是思考问题的解对某一节点来说有多少情况。

　　这道题：对于某一节点，*要么在左子树 *要么在右子树 *要么一点在左，一点在右，也就是说路径经过这一节点

　　递归解法：