Berkeley CS 61B Data Structures(in Java) Lab9 讨论帖

Lab 9， 之前没有人开贴， 就开一个吧。作业链接
上完Trees and traversals 这一节课就可以做了。

先贴作业：

真是蛋疼。。。乍看好简单，结果到处bug。。。

小结：
1.最容易出错的bug感觉就是null和invalid node的区别：
实际上永远应该多用parent(), nextSibing(), child(1) 而不是 parent, nextSibling, firstChild;
要让前者返回一个invalid node，而不是后者＝＝null；
原因是invalid node仍然是个node，可以避免很多NullPointerException；
当然在parent()这些函数里面，该用null的还是得用null了。
这次出各种bug实际上是在还前面某次作业的债了。。。
2. insert()要把children()和c两个变量都拿来分情况讨论
3. remove()要找到this之前的node，分this在开头和非开头两种情况就好，但是因为要找之前的node，所以要回溯parent，就要讨论是否root；如果是个双向链表该多好。。。


补充内容 (2015-6-6 22:31):
请版主标注一下 06年的lab9 即为 14年的lab10；
14年多了个lab9是纯数学证明

Creating 2-node tree.
Testing parent().

Testing insertChild().  Adding two more nodes to the 2-node tree.
Adding two more nodes to the 4-node tree.
This node is invalid, cannot insert a child.
  ERROR:  insertChild() failed to throw exception on invalid node.
The tree looks like this:
1
  11
  12
  13
    131
    132
[The above sequence should be 1, 11, 12, 13, 131, 132.]

Testing removeLeaf().  Removing one node from 6-node tree.
Removing another node from 5-node tree.
Attempting to remove non-leaf node from 4-node tree.
  Operation should have no effect.
Attempting to remove invalid node from 4-node tree.
The tree looks like this:
1
  12
  13
    131
[The above sequence should be 1, 12, 13, 131.]
Removing remaining nodes from 4-node tree.

Process finished with exit code 0

我上的是2014年的 所以是Lab10

1. D:\Git\DSA\CS61B\lab10>java -ea tree.SibTree
   
2. Creating 2-node tree.
   
3. Testing parent().
   
4. 
   
5. Testing insertChild().  Adding two more nodes to the 2-node tree.
   
6. Adding two more nodes to the 4-node tree.
   
7. The tree looks like this:
   
8. 1
   
9.   11
   
10.   12
    
11.   13
    
12.     131
    
13.     132
    
14. [The above sequence should be 1, 11, 12, 13, 131, 132.]
    
15. 
    
16. Testing removeLeaf().  Removing one node from 6-node tree.
    
17. Removing another node from 5-node tree.
    
18. Attempting to remove non-leaf node from 4-node tree.
    
19.   Operation should have no effect.
    
20. Attempting to remove invalid node from 4-node tree.
    
21. The tree looks like this:
    
22. 1
    
23.   12
    
24.   13
    
25.     131
    
26. [The above sequence should be 1, 12, 13, 131.]
    
27. Removing remaining nodes from 4-node tree.

复制代码

新手请问课程课程在哪里呢？谢谢。

reading2012 发表于 2015-3-26 09:01
新手请问课程课程在哪里呢？谢谢。

http://www.cs.berkeley.edu/~jrs/61bf10/

Lab9~求加学分。

一开始没看清楚很多要求，导致走了很多弯路   

其实这个lab不算难，但是我却做了很长时间，bug超级多。最大的问题出在用parent(), nextSibing(), child(1) 还是 parent, nextSibling, firstChild;上。
想返回invalidnode用前者，想反回null用后者。

14年版的lab 10～～

remove的时候把root单独拎出来考虑

bug超级多~终于写完了~开心！！！