How to define level tree traversal of a binary tree in isabelle/hol
By : Jaycie
Date : September 16 2020, 11:00 AM

To fix the issue you can do In principle, you can do it exactly the same way as in Haskell. The problematic bit is that you have to prove termination of the recursive auxiliary function (what is called tbf in the Haskell code you linked). The easiest way to show this is by finding some sort of measure on the input (a list of trees) that decreases with every recursive call. I propose the following measure: sum the sizes of all the trees in the list, where the size is the number of all the nodes in the tree (including leaf nodes). code :
primrec tree_values :: "'a tree ⇒ 'a list" where
"tree_values Leaf = []"
 "tree_values (Node l x r) = [x]"
primrec tree_children :: "'a tree ⇒ 'a tree list" where
"tree_children Leaf = []"
 "tree_children (Node l x r) = [l, r]"
primrec tree_size :: "'a tree ⇒ nat" where
"tree_size Leaf = 1"
 "tree_size (Node l x r) = tree_size l + tree_size r + 1"
definition tree_list_size :: "'a tree list ⇒ nat"
where "tree_list_size = sum_list ∘ map tree_size"
lemma tree_size_pos: "tree_size t > 0"
by (induction t) auto
lemma tree_size_nonzero [simp]: "tree_size t ≠ 0"
by (simp add: tree_size_pos)
lemma tree_list_size_children [simp]:
"tree_list_size (tree_children t) = tree_size t  1"
by (cases t) (auto simp: tree_list_size_def)
lemma sum_list_concat: "sum_list (concat xs) = sum_list (map sum_list xs)"
by (induction xs) auto
function bfs_aux :: "'a tree list ⇒ 'a list" where
"bfs_aux ts =
(if ts = [] then [] else concat (map tree_values ts) @ bfs_aux (concat (map tree_children ts)))"
by auto
termination
proof (relation "measure tree_list_size")
fix ts :: "'a tree list"
assume ts: "ts ≠ []"
have "tree_list_size (concat (map tree_children ts)) =
sum_list (map (tree_list_size ∘ tree_children) ts)"
by (simp add: map_concat sum_list_concat tree_list_size_def o_assoc)
also from ‹ts ≠ []› have "… < sum_list (map tree_size ts)"
by (intro sum_list_strict_mono) (auto simp: tree_size_pos)
also have "… = tree_list_size ts"
by (simp add: tree_list_size_def)
finally show "(concat (map tree_children ts), ts) ∈ measure tree_list_size"
by simp
qed auto
definition bfs :: "'a tree ⇒ 'a list"
where "bfs t = bfs_aux [t]‹›
value "bfs (⟨⟨⟨Leaf, ''d'', Leaf⟩, ''b'', ⟨Leaf, ''e'', Leaf⟩⟩, ''a'',
⟨⟨Leaf, ''f'', Leaf⟩, ''c'', ⟨Leaf, ''g'', Leaf⟩⟩⟩)"
> "[''a'', ''b'', ''c'', ''d'', ''e'', ''f'', ''g'']"
:: "char list list"
Share :

Binary tree level order traversal
By : James
Date : March 29 2020, 07:55 AM
may help you . Level order traversal is actually a BFS, which is not recursive by nature. It uses Queue instead of Stack to hold the next vertices that should be opened. The reason for it is in this traversal, you want to open the nodes in a FIFO order, instead of a LIFO order, obtained by recursion as I mentioned, the level order is actually a BFS, and its [BFS] pseudo code [taken from wikipedia] is: code :
1 procedure BFS(Graph,source):
2 create a queue Q
3 enqueue source onto Q
4 mark source
5 while Q is not empty:
6 dequeue an item from Q into v
7 for each edge e incident on v in Graph:
8 let w be the other end of e
9 if w is not marked:
10 mark w
11 enqueue w onto Q

How to get the post order traversal of a BINARY TREE (NOT binary search tree), given only its inorder traversal
By : Bhavin
Date : March 29 2020, 07:55 AM
should help you out You can't do that. Your example might represent multiple trees, for example : code :
E D
\ / \
D E B
\ \
B A
\ \
A G ...
\ \
G F
\ \
F G
\ \
H C
\
C

Level Order tree Traversal for a generic tree, displaying the tree level by level
By : Ad Wolters
Date : March 29 2020, 07:55 AM
Any of those help I would like to display the tree structure level by level. My current code does a BFS or Level Order Traversal but I cannot get the output to display the tree structure like a tree See current output and Expected output. , only need to keep track of current level and next level. code :
static void displayBFS(NaryTreeNode root) {
int curlevel = 1;
int nextlevel = 0;
LinkedList<NaryTreeNode> queue = new LinkedList<NaryTreeNode>();
queue.add(root);
while(!queue.isEmpty()) {
NaryTreeNode node = queue.remove(0);
if (curlevel == 0) {
System.out.println();
curlevel = nextlevel;
nextlevel = 0;
}
for(NaryTreeNode n : node.nary_list) {
queue.addLast(n);
nextlevel++;
}
curlevel;
System.out.print(node.data + " ");
}
}

Build binary tree from level order & inorder tree traversal
By : Sepidar123
Date : March 29 2020, 07:55 AM
With these it helps Finally, I could debug my code and work it out to function correctly. Next approach will be to optimise this algorithm. Suggestions to optimise this code (space wise) are welcomed. code :
/*
Algorithm Hint:
A
/ \
B C
/ \ / \
D E F G
inorder order will be DBEAFCG
and leve order will be ABCDEFG
From the level order, we know that A is the root, then check inorder, we further know DBE is left subtree and FCG is right subtree. to construct left subtree, from level order, we know left subtree's level order is BDE(find DBE's order in level order after A), we call the method to construct left subtree with inorder DBE and level order BDE.
*/
struct node * buildLevelInTree(int * in, int in_size, int *level, int l_size){
if(in_size==0  l_size==0)
return NULL;
int in_index,l_count,r_count;
in_index=searchIndex(in,0,in_size,level[0]);
l_count=in_index;r_count=in_sizein_index1;
struct node* root=newNode(level[0]);
int *in_left=makeInorder_left(in,in_size,in_index);
int *in_right=makeInorder_right(in,in_size,in_index);
int *level_left=makeLevel_left(level,l_size,in_left,l_count);
int *level_right=makeLevel_right(level,l_size,in_right,r_count);
root>left=buildLevelInTree(in_left,l_count,level_left,l_count);
root>right=buildLevelInTree(in_right,r_count,level_right,r_count);
return root;
}//end of buildLevelInTree
//Helping function for buildLevelInTree
int * makeInorder_right(int *in, int in_size, int pivot){
if(in==NULL)
return NULL;
int *in_right;
in_right=(int *)malloc(sizeof(int)*(in_sizepivot1));
int i=pivot+1;
for(;i<in_size;i++)
in_right[ipivot1]=in[i];
return in_right;
}
//Helping function for buildLevelInTree
int *makeLevel_left(int *level, int lv_size, int * in_left, int inleft_size){
if(in_left == NULL  level == NULL)
return NULL;
int *level_left;
level_left=(int *)malloc(sizeof(int)*inleft_size);
int i=0;
int temp;
for(i=0;i<inleft_size;i++){
temp=searchLevel(level,lv_size,in_left[i]);
level_left[i]=temp;//searchLevel(level, lv_size, in_left[i]);
}
level_left=sort(level_left,inleft_size);
for(i=0;i<inleft_size;i++){
temp=level[level_left[i]];
level_left[i]=temp;//level[level_left[i]];
}
return level_left;
}
//Helping function for buildLevelInTree
int *makeLevel_right(int *level, int lv_size, int * in_right, int inright_size){
if(in_right == NULL  level == NULL)
return NULL;
int *level_right;
level_right=(int *)malloc(sizeof(int)*inright_size);
int i=0;
for(i=0;i<inright_size;i++)
level_right[i]=searchLevel(level, lv_size, in_right[i]);
level_right=sort(level_right,inright_size);
for(i=0;i<inright_size;i++)
level_right[i]=level[level_right[i]];
return level_right;
}
//Helping function for buildLevelInTree
int * sort(int *a,int n)
{
int i,j,k,temp;
for(i=1;i< n;i++)
{
for(j=0;j< n1;j++)
if(a[j]>a[j+1])
{
temp=a[j];
a[j]=a[j+1];
a[j+1]=temp;
}
}
return a;
}
//Helping function for buildLevelInTree
int searchLevel(int *level, int lv_size, int value){
int i=0;
for(i=0;i<lv_size;i++){
if(level[i]==value)
return i;
}
return 1;
}

Binary tree traversal with level
By : Art C
Date : March 29 2020, 07:55 AM
will help you Yeah, that's definitely possible. It looks like you want to traverse the tree in depth first order which makes things nice and simple. The algorithm will look something like this (in pseudocode since no code provided for reference): code :
void traverse(node, depth) {
print(node.value, depth);
depth++;
traverse(node.leftChild, depth);
traverse(node.rightChild, depth);
depth;
}



Related Posts :
