두 갈래 나무 제목 요약 (1)
44074 단어 두 갈래 나무
n개의 노드가 있는 두 갈래 나무는 반드시 n+1개의 빈 바늘이 있다. 이런 빈 바늘을 이용하여 두 갈래 나무의 어떤 역행 순서의 전구와 (또는) 후계 정보를 기록할 수 있다
다음은 중간 순서의 단서화된 두 갈래 트리의 코드를 보여 줍니다.
1 #include <iostream>
2
3 struct ThreadTreeNode {
4 int val;
5 bool ltag; /* 0 for link, 1 for thread */
6 bool rtag;
7 ThreadTreeNode *left;
8 ThreadTreeNode *right;
9 ThreadTreeNode(int v = -1) : val(v), ltag(0), rtag(0), left(NULL), right(NULL) { }
10 };
11
12 class Solution {
13 public:
14 void *inorderThreadMirror(ThreadTreeNode *root) {
15 if(!root) return NULL;
16 ThreadTreeNode *prev = NULL;
17 ThreadTreeNode *curr = root;
18 while(curr) {
19 if(!curr->left) {
20 curr->ltag = 1; /* no left child threaded it */
21 curr->left = prev; /* if curr is the first node in inorder, its prev is NULL */
22 prev = curr;
23 curr = curr->right;
24 }
25 else {
26 ThreadTreeNode *temp = curr->left;
27 while(temp->right && temp->right != curr) temp = temp->right;
28 if(!temp->right) { /* has not been visited */
29 temp->rtag = 1;
30 temp->right = curr;
31 curr = curr->left;
32 }
33 else { /* has been visited */
34 prev = curr;
35 curr = curr->right;
36 }
37 }
38 }
39 }
40 void inorderTraversal(ThreadTreeNode *root) {
41 while(root && root->ltag != 1) root = root->left; /* find the first node in inorder */
42 while(root) {
43 std::cout << root->val << " ";
44 if(!root->right) break; /* right node in NULL, says that its the last node */
45 if(root->rtag == 1) /* thread */
46 root = root->right;
47 else { /* link */
48 root = root->right;
49 while(root && root->ltag != 1) root = root->left;
50 }
51 }
52 std::cout << std::endl;
53 }
54 };
55
56 int main() {
57 ThreadTreeNode *root = new ThreadTreeNode(0);
58 root->left = new ThreadTreeNode(1);
59 root->right = new ThreadTreeNode(2);
60 root->left->left = new ThreadTreeNode(3);
61 root->left->right = new ThreadTreeNode(4);
62 root->left->right->left = new ThreadTreeNode(5);
63 root->left->right->right = new ThreadTreeNode(6);
64 Solution s;
65 s.inorderThreadMirror(root);
66 s.inorderTraversal(root);
67 return 0;
68 }2. 두 갈래 나무 노드 사이의 최대 거리를 구한다
모든 노드에 대해 이 노드가 왼쪽까지의 최대 거리 + 오른쪽까지의 최대 거리를 계산하여 저장하지만, 왼쪽이나 오른쪽까지의 최대 거리만 되돌려줍니다.
1 #include <iostream>
2
3 struct TreeNode {
4 int val;
5 TreeNode *left;
6 TreeNode *right;
7 TreeNode(int v = -1) : val(v), left(NULL), right(NULL) { }
8 };
9
10 class Solution {
11 public:
12 Solution() {r_max = 0;}
13
14 int maxDistanceDFS(TreeNode *root) {
15 dfs(root);
16 return r_max;
17 }
18 int maxDistance(TreeNode *root) {
19 if(!root) return 0;
20 int a = maxDep(root->left) + maxDep(root->right);
21 int b = maxDistance(root->left);
22 int c = maxDistance(root->right);
23 return std::max(std::max(a, b), c);
24 }
25 int r_max;
26 private:
27 int maxDep(TreeNode *root) {
28 if(!root) return 0;
29 return std::max(maxDep(root->left), maxDep(root->right)) + 1;
30 }
31 int dfs(TreeNode *root) {
32 if(!root) return 0;
33 int l = dfs(root->left);
34 int r = dfs(root->right);
35 r_max = std::max(r_max, l + r);
36 return l > r ? l + 1 : r + 1;
37 }
38 };
39
40 int main() {
41 TreeNode *root = new TreeNode(1);
42 root->right = new TreeNode(3);
43 root->right->left = new TreeNode(4);
44 root->right->right = new TreeNode(5);
45 root->right->left->left = new TreeNode(6);
46 root->right->left->right = new TreeNode(7);
47 root->right->right->right = new TreeNode(8);
48 std::cout << (new Solution)->maxDistanceDFS(root) << std::endl;
49 std::cout << (new Solution)->maxDistance(root) << std::endl;
50 return 0;
51 }3. 요즘 공공조상
1 #include <iostream>
2
3 struct TreeNode {
4 int val;
5 TreeNode *left;
6 TreeNode *right;
7 TreeNode(int v = -1) : val(v), left(NULL), right(NULL) { }
8 };
9
10 class Solution {
11 public:
12 TreeNode *commonForefather(TreeNode *root, TreeNode *childa, TreeNode *childb) {
13 if(isHere(root->left, childa) && isHere(root->left, childb)) {
14 if(root->left == childa || root->left == childb)
15 return root;
16 return commonForefather(root->left, childa, childb);
17 }
18 else if(isHere(root->right, childa) && isHere(root->right, childb)) {
19 if(root->right == childa || root->right == childb)
20 return root;
21 return commonForefather(root->right, childa, childb);
22 }
23 else
24 return root;
25 }
26 private:
27 bool isHere(TreeNode *root, TreeNode *child) {
28 if(root == child)
29 return true;
30 if(root == NULL)
31 return false;
32 return isHere(root->left, child) || isHere(root->right, child);
33 }
34 };
35
36 int main() {
37 TreeNode *root = new TreeNode(1);
38 root->left = new TreeNode(2);
39 root->right = new TreeNode(3);
40 root->right->left = new TreeNode(4);
41 root->right->left->left = new TreeNode(5);
42 root->right->left->right = new TreeNode(6);
43 std::cout << (new Solution)->commonForefather(root, root->right->left->left, root->right->left)->val << std::endl;
44 return 0;
45 }4. 두 갈래 나무의 높이와 너비
높이는 두 갈래 나무의 최대 깊이로 정의된다
너비는 높이가 같은 노드 수의 최대값으로 정의됩니다.
1 #include <iostream>
2 #include <queue>
3
4 struct TreeNode{
5 int val;
6 TreeNode *left;
7 TreeNode *right;
8 TreeNode(int v = -1) : val(v), left(NULL), right(NULL) { }
9 };
10
11 class Solution {
12 public:
13 int biTreeDep(TreeNode *root) {
14 if(!root) return 0;
15 return std::max(biTreeDep(root->left), biTreeDep(root->right)) + 1;
16 }
17 int biTreeWidth(TreeNode *root) {
18 if(!root) return 0;
19 std::queue<TreeNode *> que;
20 int maxWidth = 0;
21 int curWidth = 0;
22 que.push(root);
23 que.push(NULL);
24 while(!que.empty()) {
25 while(que.front()) {
26 TreeNode *curr = que.front();
27 que.pop();
28 curWidth++;
29 if(curr->left) que.push(curr->left);
30 if(curr->right) que.push(curr->right);
31 }
32 maxWidth = std::max(maxWidth, curWidth);
33 curWidth = 0;
34 que.pop();
35 if(que.empty()) break;
36 que.push(NULL);
37 }
38 return maxWidth;
39 }
40 };
41
42 int main() {
43 TreeNode *root = new TreeNode(1);
44 root->left = new TreeNode(2);
45 root->right = new TreeNode(3);
46 root->right->right = new TreeNode(4);
47 root->right->right->left = new TreeNode(5);
48 root->right->right->left->right = new TreeNode(6);
49 Solution s;
50 std::cout << s.biTreeDep(root) << std::endl;
51 std::cout << s.biTreeWidth(root) << std::endl;
52 return 0;
53 }5. Huffman 인코딩
1 #include <iostream>
2 #include <vector>
3 #include <queue>
4 #include <map>
5 using namespace std;
6
7 typedef unsigned int uint;
8 struct HuffTreeNode {
9 uint weight;
10 HuffTreeNode *lchild;
11 HuffTreeNode *rchild;
12 HuffTreeNode *parent;
13 HuffTreeNode(uint w = 0) : weight(w), lchild(NULL), rchild(NULL), parent(NULL) { }
14 };
15 struct Cmp {
16 bool operator() (const HuffTreeNode *a, const HuffTreeNode *b) {
17 return a->weight > b->weight;
18 }
19 };
20 class Solution {
21 public:
22 HuffTreeNode* createHuffmanCodingTree(const vector<uint> &weight) {
23 priority_queue<HuffTreeNode *, vector<HuffTreeNode *>, Cmp > pri_que;
24 HuffTreeNode *prev = NULL;
25 HuffTreeNode *curr = NULL;
26 for(int i = 0; i < weight.size(); i++)
27 pri_que.push(new HuffTreeNode(weight[i]));
28 while(!pri_que.empty()) {
29 prev = pri_que.top(), pri_que.pop();
30 if(pri_que.empty()) break;
31 curr = pri_que.top(), pri_que.pop();
32 HuffTreeNode *parent = new HuffTreeNode(prev->weight + curr->weight);
33 parent->lchild = prev->lchild ? curr : prev;
34 parent->rchild = prev->lchild ? prev : curr;
35 prev->parent = curr->parent = parent;
36 pri_que.push(parent);
37 }
38 this->root = prev;
39 return prev;
40 }
41 void createHuffmanEncodeMap() {
42 string bits;
43 HuffTreeNode *curr = this->root;
44 while(curr) {
45 if(!curr->lchild) {
46 encode_map[curr->weight] = bits;
47 curr = curr->rchild;
48 }
49 else {
50 HuffTreeNode *temp = curr->lchild;
51 int backlevel = 1;
52 while(temp->rchild && temp->rchild != curr) temp = temp->rchild, backlevel++;
53 if(!temp->rchild) {
54 /* visit curr */
55 bits += "0";
56 temp->rchild = curr;
57 curr = curr->lchild;
58 }
59 else {
60 /* trace back to "root" node */
61 bits = bits.substr(0, bits.size() - backlevel);
62 bits += "1";
63 temp->rchild = NULL;
64 curr = curr->rchild;
65 }
66 }
67 }
68 }
69 private:
70 map<uint, string> encode_map;
71 map<string, uint> decode_map;
72 HuffTreeNode *root;
73 };
74
75 int main(int argc, char **argv) {
76 vector<uint> v_ui;
77 v_ui.push_back(5);
78 v_ui.push_back(29);
79 v_ui.push_back(7);
80 v_ui.push_back(8);
81 v_ui.push_back(14);
82 v_ui.push_back(23);
83 v_ui.push_back(3);
84 v_ui.push_back(11);
85 Solution s;
86 s.createHuffmanCodingTree(v_ui);
87 s.createHuffmanEncodeMap();
88 for(int i = 0; i < v_ui.size(); i++)
89 cout << v_ui[i] << " : " << s.encode_map[v_ui[i]] << endl;
90 return 0;
91 }본인의 수준이 제한되어 있기 때문에 문장의 부당함과 잘못된 점은 피하기 어렵습니다. 여러분의 비판과 지적을 환영합니다. 함께 진보하시기 바랍니다!!!
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
java 데이터 구조 2차원 트리의 실현 코드일.두 갈래 트리 인터페이스 2 노드 클래스 3. 두 갈래 나무 구현 이 글을 통해 여러분께 도움이 되었으면 좋겠습니다. 본 사이트에 대한 지지에 감사드립니다!...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
