Short Questions: Programming: ACST_Trees
chris13888Nov 17, 2019a = input() class Node(): def __init__(self, value, depth=0): self.value = value self.left = self.right = None self.depth = depth def insert(self, value): if value <= self.value: if self.left == None: self.left = Node(value, self.depth+1) # print(f'{value} is the left child of {self.value}') else: self.left.insert(value) if value > self.value: if self.right == None: self.right = Node(value, self.depth+1) # print(f'{value} is the right child of {self.value}') else: self.right.insert(value) def children(self): children = 0 if self.left != None: children += 1 if self.right != None: children += 1 return children def match(self, other): if self.left == None and self.right == None: return True if other.left == None and self.left != None: return False if other.right == None and self.right != None: return False if self.left == None: return self.right.match(other.right) if self.right == None: return self.left.match(other.left) return self.left.match(other.left) and self.right.match(other.right) def traverse(self): # print(self.value, self.left, self.right) yield self if self.left != None: yield from self.left.traverse() if self.right != None: yield from self.right.traverse() A = Node(a[0]) for c in a[1:]: A.insert(c) leaf = external = external_path = internal_path = depth = 0 for node in A.traverse(): if node.children() == 0: leaf += 1 external += 2 external_path += 2*(node.depth+1) if node.children() == 1: external += 1 external_path += node.depth+1 internal_path += node.depth depth = max(node.depth, depth) print(depth, leaf, external, internal_path, external_path)
colinzhao777Nov 18, 2019#include <bits/stdc++.h>using namespace std;#define pb push_back#define ii pair<int, int>#define vi vector<int>#define vii vector<ii>#define vs vector<string>#define ll long long#define ull usigned ll#define INF 1000000000int depth = 0;int leaf = 0;int ext = 0;int intPath = 0;int extPath = 0;struct node{ int depth; bool c1, c2; char val = '~';};vector<node> nTree;void insert(int depth, int pos, char t) { if (nTree[pos].val == '~') { nTree[pos].val = t; nTree[pos].depth = depth; } else { if (t <= nTree[pos].val) { nTree[pos].c1 = true; insert(depth + 1, 2 * pos, t); } else { nTree[pos].c2 = true; insert(depth + 1, 2 * pos + 1, t); } }}void dfs(int pos) { if (!nTree[pos].c1 && !nTree[pos].c2) { leaf++; depth = max(depth, nTree[pos].depth); ext += 2; extPath += 2 * (nTree[pos].depth + 1); intPath += nTree[pos].depth; return; } intPath += nTree[pos].depth; if (!nTree[pos].c1) { extPath += nTree[pos].depth + 1; ext++; } if (!nTree[pos].c2) { extPath += nTree[pos].depth + 1; ext++; } if (nTree[pos].c1) dfs(pos * 2); if (nTree[pos].c2) dfs(pos * 2 + 1);}int main() { string a; cin >> a; int maxSize = pow(2, a.size()); nTree.resize(maxSize + 1); for (int i = 0; i < (int)a.size(); i++) { insert(0, 1, a[i]); } dfs(1); cout << depth << endl << leaf << endl << ext << endl << intPath << endl << extPath << endl;}
1. E
2. A
3. B
2. E
3. A
12. B
a = input() class Node(): def __init__(self, value, depth=0): self.value = value self.left = self.right = None self.depth = depth def insert(self, value): if value <= self.value: if self.left == None: self.left = Node(value, self.depth+1) # print(f'{value} is the left child of {self.value}') else: self.left.insert(value) if value > self.value: if self.right == None: self.right = Node(value, self.depth+1) # print(f'{value} is the right child of {self.value}') else: self.right.insert(value) def children(self): children = 0 if self.left != None: children += 1 if self.right != None: children += 1 return children def match(self, other): if self.left == None and self.right == None: return True if other.left == None and self.left != None: return False if other.right == None and self.right != None: return False if self.left == None: return self.right.match(other.right) if self.right == None: return self.left.match(other.left) return self.left.match(other.left) and self.right.match(other.right) def traverse(self): # print(self.value, self.left, self.right) yield self if self.left != None: yield from self.left.traverse() if self.right != None: yield from self.right.traverse() A = Node(a[0]) for c in a[1:]: A.insert(c) leaf = external = external_path = internal_path = depth = 0 for node in A.traverse(): if node.children() == 0: leaf += 1 external += 2 external_path += 2*(node.depth+1) if node.children() == 1: external += 1 external_path += node.depth+1 internal_path += node.depth depth = max(node.depth, depth) print(depth, leaf, external, internal_path, external_path)
2)e 3)a 12)b
2. E
3. A
12. B
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define ii pair<int, int>
#define vi vector<int>
#define vii vector<ii>
#define vs vector<string>
#define ll long long
#define ull usigned ll
#define INF 1000000000
int depth = 0;
int leaf = 0;
int ext = 0;
int intPath = 0;
int extPath = 0;
struct node{
int depth;
bool c1, c2;
char val = '~';
};
vector<node> nTree;
void insert(int depth, int pos, char t) {
if (nTree[pos].val == '~') {
nTree[pos].val = t;
nTree[pos].depth = depth;
} else {
if (t <= nTree[pos].val) {
nTree[pos].c1 = true;
insert(depth + 1, 2 * pos, t);
} else {
nTree[pos].c2 = true;
insert(depth + 1, 2 * pos + 1, t);
}
}
}
void dfs(int pos) {
if (!nTree[pos].c1 && !nTree[pos].c2) {
leaf++;
depth = max(depth, nTree[pos].depth);
ext += 2;
extPath += 2 * (nTree[pos].depth + 1);
intPath += nTree[pos].depth;
return;
}
intPath += nTree[pos].depth;
if (!nTree[pos].c1) {
extPath += nTree[pos].depth + 1;
ext++;
}
if (!nTree[pos].c2) {
extPath += nTree[pos].depth + 1;
ext++;
}
if (nTree[pos].c1) dfs(pos * 2);
if (nTree[pos].c2) dfs(pos * 2 + 1);
}
int main() {
string a;
cin >> a;
int maxSize = pow(2, a.size());
nTree.resize(maxSize + 1);
for (int i = 0; i < (int)a.size(); i++) {
insert(0, 1, a[i]);
}
dfs(1);
cout << depth << endl << leaf << endl << ext << endl << intPath << endl << extPath << endl;
}