算法-二叉查找樹

二叉查找樹（Binary Search Tree），也稱有序二叉樹（ordered binary tree）,排序二叉樹（sorted binary tree），是指一棵空樹或者具有下列性質的二叉樹：

1. 若任意節點的左子樹不空，則左子樹上所有結點的值均小于它的根結點的值；

2. 若任意節點的右子樹不空，則右子樹上所有結點的值均大于它的根結點的值；

3. 任意節點的左、右子樹也分别為二叉查找樹；

4. 沒有鍵值相等的節點；

本文跟前文一樣隻是實作了增加和查找功能，需要一個節點輔助類:

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

<code>@interface</code> <code>BinaryNode:</code><code>NSObject</code>

<code>@property</code>  <code>(strong,</code><code>nonatomic</code><code>)  </code><code>NSString</code>  <code>*key;</code><code>//鍵</code>

<code>@property</code>  <code>(strong,</code><code>nonatomic</code><code>)  </code><code>NSString</code>  <code>*value;</code><code>//值</code>

<code>@property</code> <code>(strong,</code><code>nonatomic</code><code>) BinaryNode  *left;</code><code>//左子樹的節點</code>

<code>@property</code> <code>(strong,</code><code>nonatomic</code><code>) BinaryNode  *right;</code><code>//右子樹的節點</code>

<code>@property</code>  <code>(assign,</code><code>nonatomic</code><code>)  </code><code>NSInteger</code> <code>childCount;</code><code>//以該結點為根的自述中的結點總數</code>

<code>-(</code><code>void</code><code>)initWithData:(</code><code>NSString</code> <code>*)key  value:(</code><code>NSString</code> <code>*)value  childCount:(</code><code>NSInteger</code><code>)childCount;</code>

<code>@end</code>

BinaryNode實作代碼：

<code>@implementation</code> <code>BinaryNode</code>

<code>-(</code><code>void</code><code>)initWithData:(</code><code>NSString</code> <code>*)key value:(</code><code>NSString</code> <code>*)value childCount:(</code><code>NSInteger</code><code>)childCount{</code>

<code>    </code><code>self</code><code>.key=key;</code>

<code>    </code><code>self</code><code>.value=value;</code>

<code>    </code><code>self</code><code>.childCount=childCount;</code>

<code>}</code>

二叉查找樹需要定義一個根結點:

<code>@interface</code> <code>BinarySearchTree : </code><code>NSObject</code>

<code>@property</code>  <code>(strong,</code><code>nonatomic</code><code>)  BinaryNode  *root;</code><code>//二叉平衡樹的根節點</code>

<code>-(</code><code>NSString</code>  <code>*)get:(</code><code>NSString</code> <code>*)key;</code><code>//擷取鍵對應的值</code>

<code>-(</code><code>void</code><code>)put:(</code><code>NSString</code> <code>*)key  value:(</code><code>NSString</code> <code>*)value;</code><code>//插入鍵值對</code>

實作代碼:

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

<code>@implementation</code> <code>BinarySearchTree</code>

<code>-(</code><code>NSString</code> <code>*)get:(</code><code>NSString</code> <code>*)key{</code>

<code>    </code><code>return</code> <code>[</code><code>self</code> <code>getByKey:</code><code>self</code><code>.root key:key];</code>

<code>-(</code><code>NSString</code> <code>*)getByKey:(BinaryNode *)node  key:(</code><code>NSString</code> <code>*)key{</code>

<code>    </code><code>//在node為根結點的子樹種查找并傳回key所對應的值</code>

<code>    </code><code>//如果找不到傳回null</code>

<code>    </code><code>if</code> <code>(node==</code><code>nil</code><code>) {</code>

<code>        </code><code>return</code> <code>nil</code><code>;</code>

<code>    </code><code>}</code>

<code>    </code><code>//左右節點進行比較，每個結點的鍵值大于左子樹的結點值小于右子樹的結點值</code>

<code>    </code><code>NSInteger</code>  <code>compare=[key integerValue]-[node.key integerValue];</code>

<code>    </code><code>if</code> <code>(compare&gt;0) {</code>

<code>        </code><code>return</code> <code>[</code><code>self</code> <code>getByKey:node.right key:key];</code>

<code>    </code><code>}</code><code>else</code> <code>if</code><code>(compare&lt;0){</code>

<code>        </code><code>return</code> <code>[</code><code>self</code> <code>getByKey:node.left key:key];</code>

<code>    </code><code>}</code><code>else</code><code>{</code>

<code>        </code><code>return</code> <code>node.value;</code>

<code>//http://www.cnblogs.com/xiaofeixiang</code>

<code>-(</code><code>void</code><code>)put:(</code><code>NSString</code> <code>*)key value:(</code><code>NSString</code> <code>*)value{</code>

<code>    </code><code>//查找鍵值，找到則更新它的值，否則為它建立一個新的結點</code>

<code>    </code><code>self</code><code>.root=[</code><code>self</code> <code>putNode:</code><code>self</code><code>.root key:key value:value];</code>

<code>-(BinaryNode *)putNode:(BinaryNode *)node  key:(</code><code>NSString</code> <code>*)key  value:(</code><code>NSString</code> <code>*)value{</code>

<code>        </code><code>BinaryNode  *newNode=[[BinaryNode alloc]init];</code>

<code>        </code><code>[newNode initWithData:key value:value childCount:1];</code>

<code>        </code><code>return</code> <code>newNode;</code>

<code>        </code><code>node.right=[</code><code>self</code> <code>putNode:node.right key:key value:value];</code>

<code>        </code><code>node.left=[</code><code>self</code> <code>putNode:node.left key:key value:value];</code>

<code>        </code><code>node.value=value;</code>

<code>    </code><code>node.childCount=[</code><code>self</code> <code>childSizeCount:node.left]+[</code><code>self</code> <code>childSizeCount:node.right]+1;</code>

<code>    </code><code>return</code> <code>node;</code>

<code>-(</code><code>NSInteger</code><code>)childSize{</code>

<code>    </code><code>return</code> <code>[</code><code>self</code> <code>childSizeCount:</code><code>self</code><code>.root];</code>

<code>-(</code><code>NSInteger</code><code>)childSizeCount:(BinaryNode *)node{</code>

<code>        </code><code>return</code> <code>0;</code>

<code>        </code><code>return</code> <code>node.childCount;</code>

測試:

<code>BinarySearchTree  *binaryTree=[[BinarySearchTree alloc]init];</code>

<code>[binaryTree put:@</code><code>"3"</code> <code>value:@</code><code>"FlyElephant"</code><code>];</code>

<code>[binaryTree put:@</code><code>"9"</code> <code>value:@</code><code>"http://www.cnblogs.com/xiaofeixiang"</code><code>];</code>

<code>[binaryTree put:@</code><code>"10"</code> <code>value:@</code><code>"部落格園"</code><code>];</code>

<code>[binaryTree put:@</code><code>"0"</code> <code>value:@</code><code>"228407086"</code><code>];</code>

<code>NSString</code>  <code>*temp=[binaryTree get:@</code><code>"9"</code><code>];</code>

<code>NSLog</code><code>(@</code><code>"二叉查找樹:%@"</code><code>,temp);</code>

效果如下:

本文轉自Fly_Elephant部落格園部落格，原文連結：http://www.cnblogs.com/xiaofeixiang/p/4634487.html，如需轉載請自行聯系原作者