- 浏览: 2551878 次
- 性别:
- 来自: 成都
文章分类
最新评论
-
nation:
你好,在部署Mesos+Spark的运行环境时,出现一个现象, ...
Spark(4)Deal with Mesos -
sillycat:
AMAZON Relatedhttps://www.godad ...
AMAZON API Gateway(2)Client Side SSL with NGINX -
sillycat:
sudo usermod -aG docker ec2-use ...
Docker and VirtualBox(1)Set up Shared Disk for Virtual Box -
sillycat:
Every Half an Hour30 * * * * /u ...
Build Home NAS(3)Data Redundancy -
sillycat:
3 List the Cron Job I Have>c ...
Build Home NAS(3)Data Redundancy
Interview(5)Binary Tree
Binary Tree
public class BinTreeNode implements BinTreePosition {
protected Object element; // item in this node
protected BinTreePosition parent; //parent
protected BinTreePosition lChild; // left child
protected BinTreePosition rChild; // right child
protected int size; // children size
protected int height; //height
protected int depth; //depth
public BinTreeNode(){
this(null, null, true, null, null);
}
public BinTreeNode(Object e, //element in node
BinTreePosition p, //parent node
boolean asLChild, // left child of parent
BinTreePosition l, // left child
BinTreePosition r // right child
){
size = 1; height = depth = 0; parent = lChid = rChild = null;
element = e;
if(null != p){ //set link to parent
if(asLChild){
p.attachL(this);
}else{
p.attachR(this);
}
}
if(null != l){ attachL(l); }
if(null != r){ attachR(r); }
}
public Object getElem(){ return element; }
public Object setElem(Object obj){
Object bak = element; element = obj; return bak;
}
public boolean hasParent(){
return null != parent;
}
public BinTreePosition getParent(){ return parent; }
public void setParent(BinTreePosition p){ parent = p; }
public boolean isLeaf(){
return !hasLChild() && !hasRChild();
}
public boolean isLChild(){
return (hasParent() && this == getParent().getLChild())? true: false;
}
public boolean hasLChild() { return null != lChild; }
public BinTreePosition getLChild() { return lChild; }
public void setLChild(BinTreePosition c){ lChild = c; }
public boolean isRChild(){
return (hasParent() && this == getParent().getRChild()) ? true : false;
}
public boolean hasRChild() { return null != rChild; }
public BinTreePosition getRChild(){ return rChild; }
public void setRChild(BinTreePosition c){ rChild = c; }
public int getSize() { return size; }
public void udpateSize() {
size = 1; //current node
if(hasLChild()) { size += getLChild().getSize();}
if(hasRChild()) { size += getRChild().getSize(); }
if(hasParent()) { getParent().updateSize(); }
}
public it getHeight(){ return height; }
public void updateHeight() {
height = 0;
if(hasLChild()) { height = Math.max(height, 1 + getLChild().getHeight()); }
if(hasRChild()) { height = Math.max(height, 1 + getRChild().getHeight()); }
if(hasParent()) { getParent().updateHeight(); }
}
public int getDepth(){ return depth; }
public void updateDepth(){
depth = hasParent() ? 1+ getParent().getDepth() : 0; //current node
if(hasLChild()) { getLChild().updateDepth(); }
if(hasRChild()) { getRChild().updateDepth(); }
}
public BinTreePosition getPrev(){ //use mid iterator find the previous node
..snip...
}
…snip...
}
Method: updateSize(v)
Inputs: Binary Tree Node v
Outputs: update the size for v
{
size(v) = 1 + size(lc) + size(rc);
update size for parents till root
}
Method: updateHeight(v) - O(depth(v) + 1)
Input: Binary Tree Node v
Outputs: update height of v
{
height(v) = 0; //no children
if has left child node, height(v) = Max(height(v), 1 + height(lc));
if has right child node, height(v) = Max(height(v), 1 + height(rc));
update height for all parents
}
Method: updateDepth(v)
Inputs: Binary tree Node v
Outputs: Update depth for v
{
if parent node p, depth(v) = depth(p) + 1;
else depth(v) = 0;
if v left child node, updateDepth(lc);
if v right child node, updateDepth(rc);
}
Method: secede(v) - O(depth(v) + size(v) +1)
Inputs: binary tree node v
Outputs: v is root, the sub tree will secede
{
if v has parent,
#1 cut the reference from parent to v
#2 updateSize(v) updateHeight(v)
#3 cut the reference from v to parent
#4 updateDepth(v)
}
Method: attachL(p, c)
Inputs: binary tree node p and c
Outputs: c will be the left child of p
{
if p has left child node, secede(lc)
secede(c)
set the reference between p and c
updateSize(p) updateHeight(p)
updateDepth(c)
}
Inorder Traversal
Method: InorderTraversal(v)
Inputs: binary tree node v
Outputs: v inorder traversal
{
if(null != v){
InorderTraversal(lc) //left child node inorder traversal
visit v
InorderTraversal(rc)//right child node inorder traversal
}
}
Full Binary Tree
public interface FullBinaryTree extend BinaryTree{
public BinTreePosition addLast(Object e);
public Object delLast();
public BinTreePosition posOfNode(int i);
}
…snip...
References:
http://sillycat.iteye.com/blog/2382186
Binary Tree
public class BinTreeNode implements BinTreePosition {
protected Object element; // item in this node
protected BinTreePosition parent; //parent
protected BinTreePosition lChild; // left child
protected BinTreePosition rChild; // right child
protected int size; // children size
protected int height; //height
protected int depth; //depth
public BinTreeNode(){
this(null, null, true, null, null);
}
public BinTreeNode(Object e, //element in node
BinTreePosition p, //parent node
boolean asLChild, // left child of parent
BinTreePosition l, // left child
BinTreePosition r // right child
){
size = 1; height = depth = 0; parent = lChid = rChild = null;
element = e;
if(null != p){ //set link to parent
if(asLChild){
p.attachL(this);
}else{
p.attachR(this);
}
}
if(null != l){ attachL(l); }
if(null != r){ attachR(r); }
}
public Object getElem(){ return element; }
public Object setElem(Object obj){
Object bak = element; element = obj; return bak;
}
public boolean hasParent(){
return null != parent;
}
public BinTreePosition getParent(){ return parent; }
public void setParent(BinTreePosition p){ parent = p; }
public boolean isLeaf(){
return !hasLChild() && !hasRChild();
}
public boolean isLChild(){
return (hasParent() && this == getParent().getLChild())? true: false;
}
public boolean hasLChild() { return null != lChild; }
public BinTreePosition getLChild() { return lChild; }
public void setLChild(BinTreePosition c){ lChild = c; }
public boolean isRChild(){
return (hasParent() && this == getParent().getRChild()) ? true : false;
}
public boolean hasRChild() { return null != rChild; }
public BinTreePosition getRChild(){ return rChild; }
public void setRChild(BinTreePosition c){ rChild = c; }
public int getSize() { return size; }
public void udpateSize() {
size = 1; //current node
if(hasLChild()) { size += getLChild().getSize();}
if(hasRChild()) { size += getRChild().getSize(); }
if(hasParent()) { getParent().updateSize(); }
}
public it getHeight(){ return height; }
public void updateHeight() {
height = 0;
if(hasLChild()) { height = Math.max(height, 1 + getLChild().getHeight()); }
if(hasRChild()) { height = Math.max(height, 1 + getRChild().getHeight()); }
if(hasParent()) { getParent().updateHeight(); }
}
public int getDepth(){ return depth; }
public void updateDepth(){
depth = hasParent() ? 1+ getParent().getDepth() : 0; //current node
if(hasLChild()) { getLChild().updateDepth(); }
if(hasRChild()) { getRChild().updateDepth(); }
}
public BinTreePosition getPrev(){ //use mid iterator find the previous node
..snip...
}
…snip...
}
Method: updateSize(v)
Inputs: Binary Tree Node v
Outputs: update the size for v
{
size(v) = 1 + size(lc) + size(rc);
update size for parents till root
}
Method: updateHeight(v) - O(depth(v) + 1)
Input: Binary Tree Node v
Outputs: update height of v
{
height(v) = 0; //no children
if has left child node, height(v) = Max(height(v), 1 + height(lc));
if has right child node, height(v) = Max(height(v), 1 + height(rc));
update height for all parents
}
Method: updateDepth(v)
Inputs: Binary tree Node v
Outputs: Update depth for v
{
if parent node p, depth(v) = depth(p) + 1;
else depth(v) = 0;
if v left child node, updateDepth(lc);
if v right child node, updateDepth(rc);
}
Method: secede(v) - O(depth(v) + size(v) +1)
Inputs: binary tree node v
Outputs: v is root, the sub tree will secede
{
if v has parent,
#1 cut the reference from parent to v
#2 updateSize(v) updateHeight(v)
#3 cut the reference from v to parent
#4 updateDepth(v)
}
Method: attachL(p, c)
Inputs: binary tree node p and c
Outputs: c will be the left child of p
{
if p has left child node, secede(lc)
secede(c)
set the reference between p and c
updateSize(p) updateHeight(p)
updateDepth(c)
}
Inorder Traversal
Method: InorderTraversal(v)
Inputs: binary tree node v
Outputs: v inorder traversal
{
if(null != v){
InorderTraversal(lc) //left child node inorder traversal
visit v
InorderTraversal(rc)//right child node inorder traversal
}
}
Full Binary Tree
public interface FullBinaryTree extend BinaryTree{
public BinTreePosition addLast(Object e);
public Object delLast();
public BinTreePosition posOfNode(int i);
}
…snip...
References:
http://sillycat.iteye.com/blog/2382186
发表评论
-
Stop Update Here
2020-04-28 09:00 316I will stop update here, and mo ... -
NodeJS12 and Zlib
2020-04-01 07:44 476NodeJS12 and Zlib It works as ... -
Docker Swarm 2020(2)Docker Swarm and Portainer
2020-03-31 23:18 369Docker Swarm 2020(2)Docker Swar ... -
Docker Swarm 2020(1)Simply Install and Use Swarm
2020-03-31 07:58 370Docker Swarm 2020(1)Simply Inst ... -
Traefik 2020(1)Introduction and Installation
2020-03-29 13:52 337Traefik 2020(1)Introduction and ... -
Portainer 2020(4)Deploy Nginx and Others
2020-03-20 12:06 431Portainer 2020(4)Deploy Nginx a ... -
Private Registry 2020(1)No auth in registry Nginx AUTH for UI
2020-03-18 00:56 436Private Registry 2020(1)No auth ... -
Docker Compose 2020(1)Installation and Basic
2020-03-15 08:10 374Docker Compose 2020(1)Installat ... -
VPN Server 2020(2)Docker on CentOS in Ubuntu
2020-03-02 08:04 455VPN Server 2020(2)Docker on Cen ... -
Buffer in NodeJS 12 and NodeJS 8
2020-02-25 06:43 385Buffer in NodeJS 12 and NodeJS ... -
NodeJS ENV Similar to JENV and PyENV
2020-02-25 05:14 478NodeJS ENV Similar to JENV and ... -
Prometheus HA 2020(3)AlertManager Cluster
2020-02-24 01:47 423Prometheus HA 2020(3)AlertManag ... -
Serverless with NodeJS and TencentCloud 2020(5)CRON and Settings
2020-02-24 01:46 337Serverless with NodeJS and Tenc ... -
GraphQL 2019(3)Connect to MySQL
2020-02-24 01:48 247GraphQL 2019(3)Connect to MySQL ... -
GraphQL 2019(2)GraphQL and Deploy to Tencent Cloud
2020-02-24 01:48 451GraphQL 2019(2)GraphQL and Depl ... -
GraphQL 2019(1)Apollo Basic
2020-02-19 01:36 328GraphQL 2019(1)Apollo Basic Cl ... -
Serverless with NodeJS and TencentCloud 2020(4)Multiple Handlers and Running wit
2020-02-19 01:19 314Serverless with NodeJS and Tenc ... -
Serverless with NodeJS and TencentCloud 2020(3)Build Tree and Traverse Tree
2020-02-19 01:19 318Serverless with NodeJS and Tenc ... -
Serverless with NodeJS and TencentCloud 2020(2)Trigger SCF in SCF
2020-02-19 01:18 294Serverless with NodeJS and Tenc ... -
Serverless with NodeJS and TencentCloud 2020(1)Running with Component
2020-02-19 01:17 312Serverless with NodeJS and Tenc ...
相关推荐
7. **面试准备(Interview Practice)**:对于正在寻找工作或提升技能的开发者,`binarytree`库提供了模拟面试场景的练习,例如解决与二叉树相关的编程问题,这有助于提高对数据结构和算法的理解和应用能力。...
Leetcode 使用 Javascript 的解决方案Leetcode Problems and interview problems in Javascript10 Regular Expresion Matching.js100 Same Tree.js101 Symmetric Tree.js102 Binary Tree Level Order Traversal.js...
二叉树的中序遍历LeetCode原题难度:中等解答* Definition for a binary tree node.* function TreeNode
《Grokking the Coding Interview - Patterns for Coding Questions》是一份专为北美算法面试准备的压缩包资源,其中包含了多种常见的编程题目模式。这份资源旨在帮助面试者熟练掌握各种算法和数据结构,以便在面试...
Tree Serialization, Finding the Top k Elements of Data Streams, MapReduce, Partial Sorting, the Skyline Problem, DFS, BFS and Topological Sorting of Dags, the Alternative Alphabet and the Phone Words...
grokking-the-coding-interview ├───0-1-knapsack ├───bitwise-XOR ├───codesetup ├───cyclic-sort ├───fast-and-slow-pointers ├───in-place-reversal-of-linked-list ├───k-way-merge...
lru cache leetcode Coding-Interview A repo for popular coding interview problems mainly from Leetcode. 二分搜索/有序数组旋转 ...Binary Search Tree Value 二叉树查找/二叉树第K个 Kth Smallest Element In A
data_structure_binary_tree包为二叉树专题记录。 introduction_to_data_structure_binary_search_tree包为二叉搜索树专题记录。 n_ary_tree包为N叉树专题记录。 trie包为前缀树专题记录。 算法 binary_search包为二...
leetcode中国 大赫的算法宝典 Treasure of Algorithm 目录 Content Basic LeetCode problems, including ...Interview ...二叉树(BinaryTree) │ │ ├─01.算法总结 │ │ ├─02.入门题目 │ │ └─
玩转算法面试-- Leetcode真题分门别类 资源列表: 00-The-Opening 01-What-is-Algorithm-Interview ...07-Binary-Tree-and-Recursion 08-Recurion-and-Backstracking 09-Dynamic-Programming 10-Greedy-Algorithms
关于 这些是从易到难的最流行的编码面试问题。 问题涵盖面试中的常见模式/算法: 二进制搜索 两个指针 回溯 DFS BFS 动态编程 堆叠/贪婪/堆 交换对应的值 将一个或多个不同的值存储在同一指针中 ...O(1)
话题二元搜寻二进制搜索树二叉树(Segment Tree) N-Aray树(Trie,二进制索引树) 图(Dijkstra,Union Find,Kruskal,Prim's,最小生成树,拓扑排序等) 堆队列大批排序哈希表堆链表位操作动态编程
要在控制台中运行特定问题,请转至文件test,将调用添加到测试函数( test() ),然后在控制台node <problem> (例如, node LeetcodeProblems/Lowest_Common_Ancestor_of_a_Binary_Tree.js )。 Leetcode问题 名称...
interview)的程式码偶尔也会放一些跟java开发相关的code在Other目录 該Readme會與hackmd上的筆記進行同步 https://hackmd.io/G_mtZGV6R7KnMZ2hv4D5Hg 准备方式 开始刷题日期2019年12/4号开始看了上面牛人们解题的...
6. **树(Tree)**:包括二叉树(Binary Tree)、二叉搜索树(Binary Search Tree)等。在Objective-C中,可以通过自定义结构体或类来实现。 7. **图(Graph)**:用于表示对象之间的关系,通常用邻接矩阵或邻接表...
技术访谈2020 该存储库包含各种资源的解决方案,可用于即将进行的采访。 数组 前缀和 总和小于K的最大子数组大小 M范围增量后的最大值 给定范围内的最大出现整数 ...叠放
5. **二叉查找树(Binary Search Tree, BST)**:BST是一种特殊的二叉树,每个节点的值大于左子树的所有节点,小于右子树的所有节点。这种结构使得查找、插入和删除操作非常高效。 6. **二叉树(Binary Trees)**:...
如“Binary Tree Inorder Traversal”要求实现二叉树的中序遍历,可以采用递归或栈来解决。 5. **堆**:堆是一种特殊的树形数据结构,常用于实现优先队列。例如,“Kth Largest Element in an Array”可以使用大...
二叉搜索树(Binary Search Tree, BST)是一种特殊的二叉树,左子树上的所有节点都小于根节点,右子树上的所有节点都大于根节点。 3. 图(Graphs):图由顶点和边组成,可以用来表示对象之间的关系。图可以是无向的...