Лекция №6. Деревья. Предмет "Структуры и алгоритмы обработки данных"

• Published on
02-Jul-2015

• View
1.761

0

Embed Size (px)

Transcript

• 1. . .. : , www.grebenshikov.ru

2. - T : 1. , - T. 2. m 0 - T1, . . . , Tm, ( T1, . . . , Tm -). - , , .1 3. - . ?2 4. {A, {B, {H} , {J}} , {C, {D} , {E, {G}} , {F }}}3 5. a b (c/d + e/f )4 6. 5 7. - , - , - 6 8. - , . : , - ( )7 9. 1interface Action { 2 void doAction(T o); 3} 4 5interface Tree { 6 T getData(); 7 void setData(T o); 8 Tree getLeftMostChild(); 9 Tree getRightMostChild(); 10Tree getLeftSibling(); 11void setLeftSibling(Tree sibling); 12Tree getRightSibling(); 13void setRightSibling(Tree sibling); 14Tree getParent();8 10. 15 void setParent(Tree parent); 16 void insertChildAsRightMost(Tree child); 17 void preOrder(Action a); 18 void postOrder(Action a); 19 void levelPreOrder(Action a); 20 void descendantsPreOrder(Action a); 21 void parentsFromRoot(Action a); 22 } 11. 1 public void preOrder(Action a) { 2a.doAction(data); 3Tree child = leftMostChild; 4while(null != child) { 5 child.preOrder(a); 6 child = child.getRightSibling(); 7} 8 }9 12. 1 class PrintData implements Action { 2public void doAction(Integer data) { 3 try { 4 wr.write(data + " "); 5 } catch (Exception e) {} 6} 7 }10 13. A:1 2 3 4 5 6 7 8 9 100 1 1 2 2 5 5 5 3 3A[i]=j j i ; A[i]=0 i 11 14. 12 15. 1 class PointerTree implements Tree { 2private T data; 3private Tree parent; 4private Tree leftMostChild; 5private Tree rightMostChild; 6private Tree leftSibling; 7private Tree rightSibling; 8... 9 }13 16. 1interface BinaryTree { 2 T getData(); 3 void setData(T o); 45 BinaryTree getParent(); 6 void setParent(BinaryTree parent); 78 void setLeft(BinaryTree value); 9 BinaryTree getLeft(); 1011void setRight(BinaryTree value); 12BinaryTree getRight(); 13 }14 17. - A:1 2 3 4 5 6 7a b c d e f gA[i] A[2*i] A[2*i+1], A[2*i] A[2*i+1] . 15 18. 1 class BinaryTreeImpl implements BinaryTree { 2BinaryTree parent; 3BinaryTree left; 4BinaryTree right; 5T data; 6 }16 19. : 1 2 a000000 b00111 c01001 d011001 e10010bcd 001 010 011 ( 1) 11 01 001 ( 2)17 20. - , : a, b ab . , . : - () , . - . ?18 21. 19 22. 1. >1 2. i = , j = 3. i j 4. i- i- j- 5. j- 20 23. 1 class HaffmanTree extends BinaryTreeImpl { 2public double weight; 34public HaffmanTree(String str, double weight) { 5 super(str); 6 this.weight = weight; 7} 8 } 910HaffmanTree[] forest = new HaffmanTree[MAX_COUNT]; 11int forestLength = 0;21 24. 1length=forestLength; 2while (length > 1) { 3 swapInForest(getIndexWithMinWeight(), length-1); 4 forestLength--; 5 int min = getIndexWithMinWeight(); 6 HaffmanTree newTree = new HaffmanTree( 7forest[min].getData()+forest[length].getData(), 8forest[min].weight + forest[length].weight); 9 newTree.setLeft(forest[min]); 10newTree.setRight(forest[length]); 11forest[min] = newTree; 12 } 22 25. ., ., . . - . : , 2000..77-102. ., ., ., . -: , 2- . - . : - , 2007. .274-281, 459-467. , , 1. , 3- . - . : ,2000. .352-475. 23