首页 > 代码库 > Java版——二叉树

Java版——二叉树

2024-09-16 10:03:35   213人阅读

1.一般有2i个节点在第i+1层上，满足这个条件的树称作是完全二叉树。

2.对于所有的非空二叉树，如果它的中间节点都恰好有两个非空子女，那么叶的数目m大于中间节点的数目k，并且m=k+1。

　　证明：1??如果一个树仅有一个根，那么很容易验证上述条件。假如他对某个树成立，就将两个树连接到一个已存在的树叶上，则该树叶就称为一个中间节点，所以m减少了1，而k增加了1。但是，因为新添加了两个树叶到树上，m有增加了2.增加2且减少1，以及m=k+1，可得等式（m-1）+2=（k+1）+1，正是需要的结果。这暗示了一个i+1层的完全决策树有2i个树叶，并且根据前面的结论，应该有2i-1个中间节点，所以共有2i+2i-1=2i+1-1个节点。  　　　　

3.IntBST.java

  1 package binary_search_tree1;
  2 
  3 import java.util.Queue;
  4 import java.util.Stack;
  5 
  6 public class IntBST {
  7     protected IntBSTNode root;
  8     public IntBST(){
  9         root = null;
 10     }
 11     protected void visit(IntBSTNode p){
 12         System.out.println(p.key+" ");
 13     }
 14     public IntBSTNode search(IntBSTNode p, int e1){
 15         while(p != null)
 16             if(e1 == p.key)
 17                 return p;
 18             else if(e1<p.key)
 19                 p = p.left;
 20             else p = p.right;
 21         return null;
 22     }
 23     public void breadthFirst(){
 24         IntBSTNode p = root;
 25         Queue queue = new Queue();
 26         if(p != null){
 27             queue.enqueue(p);
 28         }
 29         while(!queue.isempty()){
 30             p = (IntBSTNode)queue.dequeue();
 31             visit(p);
 32             if(p.left != null)
 33                 queue.qnqueue(p.left);
 34             if(p.right != null)
 35                 queue.enqueue(p.right);
 36         }
 37     }
 38     public void preorder(){
 39         preorder(root);
 40     }
 41     protected void preorder(IntBSTNode p){
 42         if(p != null)
 43             visit(p);
 44         preorder(p.left);
 45         preorder(p.right);
 46     }
 47     public void inorder(){
 48         inorder(root);
 49     }
 50     protected void inorder(IntBSTNode p){
 51         if(p != null)
 52             inorder(p.left);
 53         visit(p);
 54         inorder(p.right);
 55     }
 56     public void postorder(){
 57         postorder(root);
 58     }
 59     protected void postorder(IntBSTNode p){
 60         if(p != null)
 61             postorder(p.left);
 62         postorder(p.right);
 63         visit(p);
 64     }
 65     public void iterativePreoder(){        //先序遍历树的非递归实现
 66         IntBSTNode p = root;
 67         Stack traveStack = new Stack();
 68         if(p != null)
 69             traveStack.push(p);
 70             while(!traveStack.isEmpty()){
 71                 p = (IntBSTNode)traveStack.pop();
 72                 visit(p);
 73                 if(p.right != null)
 74                     traveStack.push(p.right);
 75                 if(p.left != null)
 76                     traveStack.push(p.left);
 77         }
 78     }
 79     public void iterativeInorder(){                //中序遍历树的非递归实现
 80         IntBSTNode p = root;
 81         Stack traveStack = new Stack();
 82         while(p != null){
 83             while(p != null){
 84                 if(p.right != null)
 85                     traveStack.push(p.right);
 86                 traveStack.push(p);
 87                 p = p.left;
 88             }
 89             p = (IntBSTNode)traveStack.pop();
 90             while(!traveStack.isEmpty()&&p.right==null){
 91                 visit(p);
 92                 p = (IntBSTNode)traveStack.pop();
 93             }
 94             visit(p);
 95             if(!traveStack.isEmpty())
 96                 p = (IntBSTNode)traveStack.pop();
 97             else p = null;
 98         }
 99     }
100     public void iterativePostorder(){            //后序遍历树的非递归实现
101         IntBSTNode p = root, q = root;
102         Stack traveStack = new Stack();
103         while(p != null){
104             for(; p.left != null; p = p.left)
105                 traveStack.push(p);
106             while(p != null&&(p.right==null||p.right==q)){
107                 visit(p);
108                 q = p;
109                 if(traveStack.isEmpty())
110                     return;
111                 p = (IntBSTNode)traveStack.pop();
112             }
113             traveStack.push(p);
114             p = p.right;
115         }
116     }
117     public void MorrisInorder(){            //Morris中序遍历算法的实现
118         IntBSTNode p = root,tmp;
119         while(p != null)
120             if(p.left == null){
121                 visit(p);
122                 p = p.right;
123             }
124             else{
125                 tmp = p.left;
126                 while(tmp.right != null&&tmp.right != p)
127                     tmp = tmp.right;
128                 if(tmp.right == null){
129                     tmp.right = p;
130                     p = p.left;
131                 }
132                 else{
133                     visit(p);
134                     tmp.right = null;
135                     p = p.right;
136             }
137         }
138     }
139     public void insert(int e1){
140         IntBSTNode p = root, prev = null;
141         while(p != null){
142             prev = p;
143             if(p.key < e1)
144                 p = p.right;
145             else p = p.left;
146         }
147         if(root == null)
148             root = new IntBSTNode(e1);
149         else if(prev.key < e1)
150             prev.right = new IntBSTNode(e1);
151         else prev.left = new IntBSTNode(e1);
152     }
153     public void deleteByMerging(int e1){
154         //归并删除算法实现
155         IntBSTNode tmp, node, p = root, prev = null;
156         while(p != null&&p.key != e1){
157             prev = p;
158             if(p.key<e1)
159                 p = p.right;
160             else p = p.left;
161         }
162         node = p;
163         if(p != null&&p.key == e1){
164             if(node.right == null)
165                 node = node.left;
166             else if(node.left == null)
167                 node = node.right;
168             else{
169                 tmp = node.left;
170                 while(tmp.right != null)
171                     tmp = tmp.right;
172                 tmp.right = node.right;
173                 node = node.left;
174             }
175             if(p == root)
176                 root = node;
177             else if(prev.left == p)
178                 prev.left = node;
179             else prev.right = node;
180         }
181         else if(root != null)
182             System.out.println("key"+e1+"is not in the tree");
183         else System.out.println("the tree is empty");
184     }
185     public void deleteByCopying(int e1){            //复制删除法的算法实现
186         IntBSTNode node, p = root, prev = null;
187         while(p != null &&p.key != e1){
188             prev = p;
189         if(p.key<e1)
190             p = p.right;
191         else p = p.left;
192     }
193     node = p;
194     if(p != null && p == e1){
195         if(node.right==null)
196             node = node.left;
197         else if(node.left == null)
198             node = node.right;
199         else{
200             IntBSTNode tmp = node.left;
201             IntBSTNode previous = node;
202             while(tmp.right != null){
203                 previous = tmp;
204                 tmp = tmp.right;
205             }
206             node.key = tmp.key;
207             if(previous == node)
208                 previous.left = tmp.left;
209             else previous.right = tmp.left;
210         }
211         if(p == root)
212             root = node;
213         else if(prev.left == p)
214             prev.left = node;
215         else prev.right = node;
216         }
217     else if(root != null)
218         System.out.println("key" + e1 + "is not in the tree");
219     else System.out.println("the tree is empty");
220     }
221 }

4.IntBSTNode.java

 1 package binary_search_tree1;
 2 
 3 public class IntBSTNode {
 4     protected int key;
 5     protected IntBSTNode left, right;
 6     public IntBSTNode(){
 7         left = right = null;
 8     }
 9     public IntBSTNode(int e1){
10         this(e1, null, null);
11     }
12     public IntBSTNode(int e1, IntBSTNode lt, IntBSTNode rt){
13         key = e1; left = lt; right = rt;
14     }
15 }

5.二叉查找树：也称作有序二叉树。对于树中的每个节点n，其左子树中保存的所有数值都小于n中保存的数值v，其右子树中保存的所有数值都会大于v。　　

6.树的遍历：1??广度优先遍历　　从最底层（或最高层）开始逐层向上（或向下）遍历，而在同一层自左向右（或自右向左）访问每一个节点；

　　　　　　2??深度优先遍历　　尽可能地沿着左边（或右边）前进，然后返回到第一个岔路口，转而访问其右边（或左边）的一个节点，然后再次尽可能地沿着左边（或右边）前进。重复这个进程，直到访问完所有的节点：1.先序遍历；

　　　　　　　　　　　　　　　　　　　　　　　　　　2.中序遍历；

　　　　　　　　　　　　　　　　　　　　　　　　　　3.后序遍历。

7.

Java版——二叉树


联系
我们