70 數組的Kmin算法和二叉搜索樹的Kmin算法對比，kmin二叉
【本文鏈接】
http://www.cnblogs.com/hellogiser/p/kmin-of-array-vs-kmin-of-bst.html
【分析】
數組的Kmin算法和二叉搜索樹的Kmin算法非常類似，其本質是找序列中的第K大或者第K小的元素，可以借鑒QuickSort的思想加以實現。
【Kmin_of_Array】
C++ Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
// 70_Kmin_of_Array_and_BST.cpp : Defines the entry point for the console application.
//
/*
version: 1.0
author: hellogiser
blog: http://www.cnblogs.com/hellogiser
date: 2014/9/18
*/
#include "stdafx.h"
#include "iostream"
#include <ctime>
#include <algorithm>
using namespace std;
void print(int *a, int n)
{
for (int i = 0; i < n; i++)
{
cout << a[i] << " ";
}
cout << endl;
}
int compare_less (const void *a, const void *b)
{
return ( *(int *)a - * (int *)b );
}
//========================================================
// kmin of array
//========================================================
void myswap(int &a, int &b)
{
int t = a;
a = b;
b = t;
}
int partition1(int *a, int left, int right)
{
// a[left,...p-1]<=a[p]<a[p+1,...right]
int i = left;
int j = right;
int key = a[left];
while(i < j)
{
while(a[i] <= key) i++;
while(a[j] > key) j--;
if (i < j)
{
myswap(a[i], a[j]);
}
}
// left---j---i---right
myswap(a[left], a[j]);
return j;
}
int kmin(int *a, int left, int right, int k)
{
if(left < = right)
{
int p = partition1(a, left, right);
int pk = p - left + 1;
if (k == pk)
{
return a[p];
}
else if (k < pk)
{
return kmin(a, left, p - 1, k);
}
else // k >pk
{
return kmin(a, p + 1, right, k - pk);
}
}
}
int Kmin_of_Array(int *a, int n, int k)
{
if (a == NULL || n <= 0)
return -1;
if (k < 1 || k > n)
return -1;
return kmin(a, 0, n - 1, k);
}
void test_base(int *a, int n, int k)
{
print(a, n);
qsort(a, n, sizeof(int), compare_less);
print(a, n);
cout << k << " min of array is: " << Kmin_of_Array(a, n, k) << endl;
cout << "==============================\n";
}
void test_default()
{
srand((unsigned int)time(NULL));
const int n = 20;
int a[n];
for (int i = 0; i < n; i++)
{
a[i] = rand() % 100;
}
test_base(a, n, 3);
}
void test_main()
{
test_default();
}
int _tmain(int argc, _TCHAR *argv[])
{
test_main();
return 0;
}
/*
37 30 22 10 22 63 6 44 36 41 43 75 54 77 9 99 3 13 28 27
3 6 9 10 13 22 22 27 28 30 36 37 41 43 44 54 63 75 77 99
3 min of array is: 9
==============================
*/
【Kmin_of_BST】
C++ Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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
59
60
61
//========================================================
// kmin of bst
//========================================================
// binary tree node struct
struct BinaryTreeNode
{
int value;
BinaryTreeNode *parent; // for rank of bst
BinaryTreeNode *left;
BinaryTreeNode *right;
int size; // for kmin of bst
// x.size = x.left.size + x.right.size +1
};
int node_size(BinaryTreeNode *node)
{
// get node size of node
if (node == NULL)
return 0;
node->size = node_size(node->left) + node_size(node->right) + 1;
return node->size;
}
int left_size(BinaryTreeNode *node)
{
// get left size of node in o(1)
return node->left != NULL ? node->left->size : 0;
}
BinaryTreeNode *kmin_bst(BinaryTreeNode *root, int k)
{
if (root == NULL)
return NULL;
int pk = left_size(root) + 1; // get node rank first
if (k == pk)
{
return root;
}
else if (k < pk)
{
return kmin_bst(root->left, k);
}
else // k>pk
{
return kmin_bst(root->right, k - pk);
}
}
BinaryTreeNode *Kmin_of_BST(BinaryTreeNode *root, int k)
{
if (root == NULL)
return NULL;
// get node size of bst first
int nodes = node_size(root);
if (k < 1 || k > nodes)
return NULL;
// use node size info to get kmin of bst
return kmin_bst(root, k);
}
用遞歸算法二叉樹的深度
return語句僅結束當前的函數調用。如果是循環調用，僅結束當前層次的調用，並返回上一層次。
對於
int depth(BTree root){
...
if(!root)
return 0;
else{
...
if(ldepth ＞= rdepth)
return ldepth+1;
else
return rdepth+1;
}
return 1;
}
最後一個“return 1;”不會被執行到的。
設計算法二叉樹的深度
#include <stdio.h>
#include <stdlib.h>
typedef struct node
{
char data;
struct node *left,*right;
}Node,*PNode;
PNode createBtree(PNode root)//創建二叉樹，控制台下輸入，基於先序遍歷輸入
{
char data;
scanf("%c",&data);
if (data==' ')
{
root=NULL;
return root;
}
root = (PNode)malloc(sizeof(Node));
root->data = data;
root->left = createBtree(root->left);
root->right = createBtree(root->right);
return root;
}
int depth(PNode root)//這就是你要的函數。
{
int ld,rd;
if (root==NULL)
{
return 0;
}
ld = 1+depth(root->left);
rd = 1+depth(root->right);
return ld>rd?ld:rd;
}
int main()
{
PNode root=NULL;
root = createBtree(root);
printf("%d",depth(root));
return 0;
}
為了測試，寫了二叉樹的建立程序；
如下輸入可以看到結果
虛節點用空格輸入的。例如你輸入
先序遍歷
234空格空格5空格6空格空格7空格空格回車就可以看到結果。
另外，本算法是從1開始算深度的，就是根節點是深度下。
樹的圖形參考
hi.baidu.com/...2.html
