作业
Bubble Sort
C
#include <stdio.h>
#include <stdbool.h>
void BubbleSort(int *a, int length)
{
for (bool swapped = true; swapped; --length)
{
swapped = false;
for (int i = 0; i != length - 1; ++i)
{
if (a[i] > a[i + 1])
{
int temp = a[i];
a[i] = a[i + 1];
a[i + 1] = temp;
swapped = true;
}
}
}
}
int main(int argc, char **argv)
{
int a[5] = {0};
for (int i = 0; i < 5; ++i)
{
scanf("%d", &a[i]);
}
BubbleSort(a, 5);
for (int i = 0; i < 5; ++i)
{
printf("%d ", a[i]);
}
}
C++
#include <algorithm>
#include <iostream>
#include <iterator>
template <typename T>
void BubbleSort(T begin, T end)
{
auto swapped = true;
while (begin != end-- && swapped)
{
swapped = false;
for (auto i = begin; i != end; ++i)
{
if (*(i + 1) < *i)
{
std::iter_swap(i, i + 1);
swapped = true;
}
}
}
}
int main()
{
int a[5] = { 0 };
for (int i = 0; i < 5; ++i)
{
std::cin >> a[i];
}
BubbleSort(std::begin(a), std::end(a));
copy(std::begin(a), std::end(a), std::ostream_iterator<int>(std::cout, " "));
std::cout << "\n";
}
C#
using System;
using System.Collections.Generic;
using static System.Console;
namespace BubbleSort
{
public static class BubbleSortMethods
{
public static void BubbleSort<T>(this List<T> list) where T : IComparable
{
var count = list.Count - 1;
for (var swapped = true; swapped; --count)
{
swapped = false;
for (var i = 0; i < count; ++i)
{
if (list[i].CompareTo(list[i + 1]) > 0)
{
T temp = list[i + 1];
list[i + 1] = list[i];
list[i] = temp;
swapped = true;
}
}
}
}
}
class Program
{
static void Main()
{
var list = new List<int>();
foreach(var i in ReadLine().Split(' '))
{
list.Add(Convert.ToInt32(i));
}
list.BubbleSort();
foreach(var i in list)
{
Write(i + " ");
}
}
}
}
Java
import java.util.Scanner;
class Main
{
public static <T extends Comparable<? super T>> void BubbleSort(T[] comparable)
{
int count = comparable.length - 1;
for(boolean swapped = true; swapped; --count)
{
swapped = false;
for(int i = 0; i < count; ++i)
{
if (comparable[i].compareTo(comparable[i + 1]) > 0)
{
T temp = comparable[i + 1];
comparable[i + 1] = comparable[i];
comparable[i] = temp;
swapped = true;
}
}
}
}
public static void main(String[] args)
{
Scanner scan = new Scanner(System.in);
String[] input = scan.nextLine().split("\\s+");
scan.close();
Integer[] lst = new Integer[input.length];
for(int i = 0; i < input.length; ++i)
{
lst[i] = Integer.parseInt(input[i]);
}
BubbleSort(lst);
for(Integer i : lst)
{
System.out.print(i + " ");
}
}
}
F#
open System
let BubbleSort (lst : list<int>) =
let rec sort accum rev lst =
match lst, rev with
| [], true -> accum |> List.rev
| [], false -> accum |> List.rev |> sort [] true
| x::y::tail, _ when x > y -> sort (y::accum) false (x::tail)
| head::tail, _ -> sort (head::accum) rev tail
sort [] true lst
[<EntryPoint>]
let main _ =
' '
|> Console.ReadLine().Split
|> List.ofArray
|> List.map (fun i ->
i |> Convert.ToInt32)
|> BubbleSort
|> List.map (fun i ->
i.ToString() + " " |> Console.Write)
|> ignore
JavaScript
<!DOCTYPE html>
<html>
<body>
<script>
Array.prototype.BubbleSort = function () {
var count = this.length - 1;
for (var swapped = true; swapped; --count) {
swapped = false;
for (var i = 0; i < count; i++) {
if (this[i] > this[i + 1]) {
var tmp = this[i + 1];
this[i + 1] = this[i];
this[i] = tmp;
swapped = true;
}
}
}
return this;
}
var input = prompt('input :').split(' ').map(function(x){
return parseInt(x, 10);
})
input.BubbleSort();
alert(input);
</script>
</body>
</html>
WolframLanguage
bubbleSort[sort[{w___, x_, y_, z___}] /; x > y := sort[{w, y, x, z}]] := list
PHP
<?php
function BubbleSort(array &$array){
$count = count($array) - 1;
for($swapped = true;$swapped;--$count){
$swapped = false;
for ($i = 0; $i < $count; ++$i){
if ($array[$i] > $array[$i + 1]){
list($array[$i + 1], $array[$i]) = array($array[$i], $array[$i + 1]);
$swapped = true;
}
}
}
return $array;
}
$test = array(32132,132,132,132,165,5646,4897,4564,654986,4651651,2313212312,2);
print_r(BubbleSort($test));
?>
PowerShell
function BubbleSort ($a)
{
$count = $a.Length - 1
for ($swapped = $true; $swapped; --$count)
{
$swapped = $false
for ($i = 0; $i -lt $count; ++$i)
{
if ($a[$i] -gt $a[$i+1])
{
$a[$i], $a[$i+1] = $a[$i+1], $a[$i]
$swapped = $true
}
}
}
}
$test = (31,65,56,4564,1,3513,5468,46584,684,52)
BubbleSort($test)
$test
Python
def BubbleSort(lst):
def sort(accum,rev,lst):
if lst == [] and rev:
return list(reversed(accum))
elif lst == [] and rev == False:
return sort([], True, list(reversed(accum)))
else:
if len(lst) == 1:
return sort(lst + accum, rev, [])
x,y,tail = lst[:1],lst[1:2],lst[2:]
if x > y:
return sort(y + accum, False, x + tail)
else:
return sort(x + accum, rev, y + tail)
return sort([],True,lst)
print(BubbleSort(list(map(int,input().split()))))
Sequence List
F#
type SeqList<'a> (?items) =
let items = defaultArg items []
member this.InsertAfter index item =
SeqList((List.chunkBySize index items).Head @ [item] @ List.skip index items)
member this.RemoveAt index =
SeqList((List.chunkBySize index items).Head @ List.skip index items)
member this.Items =
items
[<EntryPoint>]
let main _ =
let s = new SeqList<int>([654;54;64;78;2;2])
printfn "%A" s.Items
printfn "%A" (s.InsertAfter 1 233).Items
printfn "%A" (s.RemoveAt 2).Items
System.Console.ReadLine() |> ignore
0
Singly-linked List
C++
#include<iostream>
template<typename T>
struct SinglyLinkedListNode
{
SinglyLinkedListNode* next;
T data;
SinglyLinkedListNode(T data, SinglyLinkedListNode* next = nullptr) : next(next), data(data) {}
};
template<typename T>
void Insert(SinglyLinkedListNode<T>* node, SinglyLinkedListNode<T>* newNode)
{
newNode->next = node->next;
node->next = newNode;
}
template<typename T>
void Delete(SinglyLinkedListNode<T>* node, SinglyLinkedListNode<T>* delNode)
{
node->next = delNode;
delete delNode;
}
int main()
{
auto a = new SinglyLinkedListNode<int>(1);
auto b = new SinglyLinkedListNode<int>(2);
Insert(a, b);
std::cout << a->data << " " << a->next << " " << a->next->data << " " << a->next->next;
}
Stack
F#
type Stack<'a> (?items) =
let items = defaultArg items []
member x.Items = items
member x.Push(A) =
Stack(A::items)
member x.Pop() =
match items with
| head::tail -> (head,Stack(tail))
| _ -> failwith "Null"
[<EntryPoint>]
let main _ =
let s1 = Stack([5;4;3;2;1])
let s2 = s1.Push(6)
let i,s3 = s2.Pop()
printfn "%A" s1.Items
printfn "%A" s2.Items
printfn "%A" (i,s3.Items)
System.Console.ReadLine() |> ignore
0
Queue
F#
type Queue<'T> (?items) =
let items = defaultArg items []
member this.Items = items
member this.Enqueue(A) =
Queue(items@[A])
member this.Dequeue() =
match items with
| head::tail -> (head,Queue(tail))
| _ -> failwith "Null"
[<EntryPoint>]
let main _ =
let q1 = Queue([1;2;3;4;5])
let q2 = q1.Enqueue 6
let i,q3 = q2.Dequeue()
printfn "%A" q1.Items
printfn "%A" q2.Items
printfn "%A" (i,q3.Items)
System.Console.ReadLine() |> ignore
0
Tree Traversal
C
#include <stdio.h>
#include <stdlib.h>
#define T int
typedef struct node
{
T value;
struct node* left;
struct node* right;
} node;
node* Tree(T v, node* l, node* r)
{
node* n = (node*)malloc(sizeof(node));
n->value = v;
n->left = l;
n->right = r;
return n;
}
void Preorder(node* n, void(*fun)(T))
{
fun(n->value);
if (n->left) Preorder(n->left, fun);
if (n->right) Preorder(n->right, fun);
}
void Inorder(node* n, void(*fun)(T))
{
if (n->left) Inorder(n->left, fun);
fun(n->value);
if (n->right) Inorder(n->right, fun);
}
void Postorder(node* n, void(*fun)(T))
{
if (n->left) Postorder(n->left, fun);
if (n->right) Postorder(n->right, fun);
fun(n->value);
}
void PrintInt(int n)
{
printf("%d ", n);
}
int main()
{
/*
1
/ \
/ \
2 3
/ \ /
4 5 6
/ / \
7 8 9
*/
node* n = Tree(1,
Tree(2,
Tree(4,
Tree(7, NULL, NULL),
NULL),
Tree(5, NULL, NULL)),
Tree(3,
Tree(6,
Tree(8, NULL, NULL),
Tree(9, NULL, NULL)),
NULL));
Preorder(n, PrintInt);
printf("\n");
Inorder(n, PrintInt);
printf("\n");
Postorder(n, PrintInt);
}
C++
#include <iostream>
template<typename T>
class Node
{
public:
T Value;
Node* Left;
Node* Right;
Node(const T &v, Node* l = nullptr, Node* r = nullptr) :Value(v), Left(l), Right(r) {}
void Preorder(void(*fun)(T)) const
{
fun(Value);
if (Left) Left->Preorder(fun);
if (Right) Right->Preorder(fun);
}
void Inorder(void(*fun)(T)) const
{
if (Left) Left->Inorder(fun);
fun(Value);
if (Right) Right->Inorder(fun);
}
void Postorder(void(*fun)(T)) const
{
if (Left) Left->Postorder(fun);
if (Right) Right->Postorder(fun);
fun(Value);
}
};
int main()
{
Node<int> n(1,
new Node<int>(2,
new Node<int>(4,
new Node<int>(7)),
new Node<int>(5)),
new Node<int>(3,
new Node<int>(6,
new Node<int>(8),
new Node<int>(9))));
auto fun = [](auto n) { std::cout << n << " "; };
n.Preorder(fun);
std::cout << std::endl;
n.Inorder(fun);
std::cout << std::endl;
n.Postorder(fun);
}
C++
#include <iostream>
#include <stack>
template<typename T>
class Node
{
public:
T Value;
Node* Left;
Node* Right;
Node(const T &v, Node* l = nullptr, Node* r = nullptr) :Value(v), Left(l), Right(r) {}
void Preorder(void(*fun)(T)) const
{
std::stack<const Node*> s;
s.push(this);
while (!s.empty())
{
const Node* n = s.top();
s.pop();
fun(n->Value);
if (n->Right) s.push(n->Right);
if (n->Left) s.push(n->Left);
}
}
void Inorder(void(*fun)(T)) const
{
std::stack<const Node*> s;
for (const Node* n = this; !s.empty() || n; n = n->Right)
{
while (n)
{
s.push(n);
n = n->Left;
}
n = s.top();
s.pop();
fun(n->Value);
}
}
void Postorder(void(*fun)(T)) const
{
std::stack<const Node*> s;
const Node* n = this, *last = nullptr, *top = nullptr;
while (!s.empty() || n)
{
while (n)
{
s.push(n);
n = n->Left;
}
top = s.top();
if (top->Right && top->Right != last) n = top->Right;
else
{
fun(top->Value);
last = s.top();
s.pop();
}
}
}
};
int main()
{
Node<int> n(1,
new Node<int>(2,
new Node<int>(4,
new Node<int>(7)),
new Node<int>(5)),
new Node<int>(3,
new Node<int>(6,
new Node<int>(8),
new Node<int>(9))));
auto fun = [](auto n) { std::cout << n << " "; };
n.Preorder(fun);
std::cout << std::endl;
n.Inorder(fun);
std::cout << std::endl;
n.Postorder(fun);
std::cout << std::endl;
}
C++/CLI
using namespace System;
using namespace System::Collections::Generic;
template<typename T>
public class Node
{
public:
Node(const T &v, Node* l = nullptr, Node* r = nullptr) :Value(v), Left(l), Right(r) {}
void Preorder(void(*fun)(T)) const
{
fun(Value);
if (Left) Left->Preorder(fun);
if (Right) Right->Preorder(fun);
}
void Inorder(void(*fun)(T)) const
{
if (Left) Left->Inorder(fun);
fun(Value);
if (Right) Right->Inorder(fun);
}
void Postorder(void(*fun)(T)) const
{
if (Left) Left->Postorder(fun);
if (Right) Right->Postorder(fun);
fun(Value);
}
private:
T Value;
Node* Left;
Node* Right;
};
Node<int>* BuildIntTree(List<String ^> ^input , int index = 0)
{
auto level = input[index]->Split(' ')->Length - 1;
auto child = gcnew List<int>();
for (auto i = index + 1; i < input->Count; ++i)
{
if (input[i]->Split(' ')->Length - 1 == level + 1) child->Add(i);
if (input[i]->Split(' ')->Length - 1 < level + 1) break;
}
return new Node<int>(Convert::ToInt32(input[index]->Trim()), child->Count > 0 ? BuildIntTree(input, child[0]) : nullptr, child->Count > 1 ? BuildIntTree(input, child[1]) : nullptr);
}
int main()
{
auto input = gcnew List<String ^>();
for (auto i = Console::ReadLine(); i != ""; i = Console::ReadLine()) input->Add(i);
auto n = BuildIntTree(input);
auto fun = [](auto n) { Console::Write(n.ToString() + " "); };
n->Preorder(fun);
Console::WriteLine();
n->Inorder(fun);
Console::WriteLine();
n->Postorder(fun);
}
CUDA
#include "cuda_runtime.h"
#include "device_launch_parameters.h"
#include <stdlib.h>
#include <stdio.h>
#include <iostream>
#define v 0
#define l 1
#define r 2
__host__ void Preorder(void*** nodes, void(*fun)(void*))
{
int id = 0;
printf("Preorder %d:", id);
int* top = NULL;
void*** stack = NULL;
top = (int*)malloc(sizeof(int));
stack = (void***)malloc(100 * sizeof(void**));
*top = -1;
stack[++*top] = nodes[id];
while (*top > -1)
{
stack[99] = stack[(*top)--];
fun(stack[99][v]);
if (stack[99][r]) stack[++*top] = (void**)stack[99][r];
if (stack[99][l]) stack[++*top] = (void**)stack[99][l];
}
}
__host__ void Inorder(void*** nodes, void(*fun)(void*))
{
int id = 0;
printf("Preorder %d:", id);
int* top = NULL;
void*** stack = NULL;
top = (int*)malloc(sizeof(int));
stack = (void***)malloc(100 * sizeof(void***));
*top = -1;
for (stack[99] = nodes[id]; *top > -1 || stack[99]; stack[99] = (void**)stack[99][r])
{
while(stack[99])
{
stack[++*top] = stack[99];
stack[99] = (void**)stack[99][l];
}
stack[99] = stack[(*top)--];
fun(stack[99][v]);
}
}
__host__ void Postorder(void*** nodes, void(*fun)(void*))
{
int id = 0;
printf("Preorder %d:", id);
int* top = NULL;
void*** stack = NULL;
top = (int*)malloc(sizeof(int));
stack = (void***)malloc(100 * sizeof(void***));
*top = -1;
stack[99] = nodes[id];
while (*top > -1 || stack[99])
{
while (stack[99])
{
stack[++*top] = stack[99];
stack[99] = (void**)stack[99][l];
}
if (stack[*top][r] && stack[*top][r] != (void*)stack[98]) stack[99] = (void**)stack[*top][r];
else
{
fun(stack[*top][v]);
stack[98] = stack[(*top)--];
}
}
}
__host__ void** Tree(void* value, void* left, void* right)
{
void** node = NULL;
node = (void**)malloc(3 * sizeof(void*));
node[v] = value;
node[l] = left;
node[r] = right;
return node;
}
__host__ void callCuda()
{
int n[9];
for (auto i = 0; i < 9; ++i)n[i] = i + 1;
void*** nodes = NULL;
nodes = (void***)malloc(5 * sizeof(void***));
for (int i = 0; i < 5; i++)
{
nodes[i] = Tree((void*)&n[0],
Tree((void*)&n[1],
Tree((void*)&n[3],
Tree((void*)&n[6], NULL, NULL),
NULL),
Tree((void*)&n[4], NULL, NULL)),
Tree((void*)&n[2],
Tree((void*)&n[5],
Tree((void*)&n[7], NULL, NULL),
Tree((void*)&n[8], NULL, NULL)),
NULL));
}
auto fun = [](void* n) { std::cout << *(int*)n << " "; };
Preorder(nodes, fun);
std::cout << std::endl;
Inorder(nodes, fun);
std::cout << std::endl;
Postorder(nodes, fun);
}
int main()
{
callCuda();
return 0;
}
C#
using System;
using System.Collections.Generic;
namespace Temp
{
public class Node<T>
{
private T Value;
private Node<T> Left;
private Node<T> Right;
public Node(T v, Node<T> l = default, Node<T> r = default)
{
Value = v;
Left = l;
Right = r;
}
public IEnumerable<T> Preorder()
{
yield return Value;
if (Left != default) foreach (var v in Left.Preorder()) yield return v;
if (Right != default) foreach (var v in Right.Preorder()) yield return v;
}
public IEnumerable<T> Inorder()
{
if (Left != default) foreach (var v in Left.Inorder()) yield return v;
yield return Value;
if (Right != default) foreach (var v in Right.Inorder()) yield return v;
}
public IEnumerable<T> Postorder()
{
if (Left != default) foreach (var v in Left.Postorder()) yield return v;
if (Right != default) foreach (var v in Right.Postorder()) yield return v;
yield return Value;
}
}
class Temp
{
static void Main(string[] args)
{
var t =
new Node<int>(1,
new Node<int>(2,
new Node<int>(4,
new Node<int>(7)),
new Node<int>(5)),
new Node<int>(3,
new Node<int>(6,
new Node<int>(8),
new Node<int>(9))));
foreach (var f in new Func<IEnumerable<int>>[] { t.Preorder, t.Inorder, t.Postorder })
{
Console.WriteLine("{0}:{1}", f.Method.Name, string.Join(" ", f()));
}
}
}
}
Erlang
-module(traversal).
-export([main/0]).
tree() -> {}.
tree(V) -> {V, {}, {}}.
tree(V, L, R) -> {V, L, R}.
preorder(_, {}) -> ok;
preorder(F, {V, L, R}) -> F(V), preorder(F, L), preorder(F, R).
inorder(_, {}) -> ok;
inorder(F, {V, L, R}) -> inorder(F, L), F(V), inorder(F, R).
postorder(_, {}) -> ok;
postorder(F, {V, L, R}) -> postorder(F, L), postorder(F, R), F(V).
main() ->
T =
tree(1,
tree(2,
tree(4,
tree(7),
tree()),
tree(5)),
tree(3,
tree(6,
tree(8),
tree(9)),
tree())),
F = fun(X) -> io:format("~p ", [X]) end,
preorder(F, T), io:format("~n"), inorder(F, T), io:format("~n"), postorder(F, T).
F#
type 'T Tree =
| Empty
| Node of 'T * 'T Tree * 'T Tree
let rec Preorder f = function
| Empty -> ()
| Node(v,l,r) ->
f v
Preorder f l
Preorder f r
let rec Inorder f = function
| Empty -> ()
| Node(v,l,r) ->
Inorder f l
f v
Inorder f r
let rec Postorder f = function
| Empty -> ()
| Node(v,l,r) ->
Postorder f l
Postorder f r
f v
[<EntryPoint>]
let main _ =
let t =
Node(1,
Node(2,
Node(4,
Node(7,Empty,Empty),
Empty),
Node(5,Empty,Empty)),
Node(3,
Node(6,
Node(8,Empty,Empty),
Node(9,Empty,Empty)),
Empty))
let f = (fun x -> printf "%A " x)
Preorder f t
printfn ""
Inorder f t
printfn ""
Postorder f t
0
Java
import java.util.function.Consumer;
class Node<T>
{
private T Value;
private Node<T> Left = null;
private Node<T> Right =null;
public Node(T v)
{
Value=v;
}
public Node(T v,Node<T> l,Node<T> r)
{
Value=v;
Left=l;
Right=r;
}
public void Preorder(Consumer<T> f)
{
f.accept(Value);
if(Left != null) Left.Preorder(f);
if(Right != null) Right.Preorder(f);
}
public void Inorder(Consumer<T> f)
{
if(Left != null) Left.Inorder(f);
f.accept(Value);
if(Right != null) Right.Inorder(f);
}
public void Postorder(Consumer<T> f)
{
if(Left != null) Left.Postorder(f);
if(Right != null) Right.Postorder(f);
f.accept(Value);
}
}
public class Main
{
public static void main(String[] args)
{
Node<Integer> t = new Node<Integer>(1,
new Node<Integer>(2,
new Node<Integer>(4,
new Node<Integer>(7),null),
new Node<Integer>(5)),
new Node<Integer>(3,
new Node<Integer>(6,
new Node<Integer>(8),
new Node<Integer>(9)),
null));
Consumer<Integer> f = (x) -> System.out.print(x+" ");
t.Preorder(f);
System.out.println();
t.Inorder(f);
System.out.println();
t.Postorder(f);
}
}
JavaScript
var v = 0, l = 1, r = 2,
Preorder = n => [n[v]].concat(n[l] ? Preorder(n[l]) : []).concat(n[r] ? Preorder(n[r]) : []),
Inorder = n => (n[l] ? Inorder(n[l]) : []).concat(n[v]).concat(n[r] ? Inorder(n[r]) : []),
Postorder = n => (n[l] ? Postorder(n[l]) : []).concat(n[r] ? Postorder(n[r]) : []).concat(n[v]),
t = [1,
[2,
[4,
[7]],
[5]],
[3,
[6,
[8],
[9]]]];
[Preorder, Inorder, Postorder].map(f => document.write(f(t)+"<br>"));
Node.js
var v = 0, l = 1, r = 2,
Preorder = n => [n[v]].concat(n[l] ? Preorder(n[l]) : []).concat(n[r] ? Preorder(n[r]) : []),
Inorder = n => (n[l] ? Inorder(n[l]) : []).concat(n[v]).concat(n[r] ? Inorder(n[r]) : []),
Postorder = n => (n[l] ? Postorder(n[l]) : []).concat(n[r] ? Postorder(n[r]) : []).concat(n[v]),
t = [1,
[2,
[4,
[7]
],
[5]],
[3,
[6,
[8],
[9]
]
]];
[Preorder, Inorder, Postorder].map(f => console.log(f(t)));
PHP
<?php
class Node
{
private $Value;
private $Left;
private $Right;
function __construct($v,$l = null,$r = null)
{
$this->Value=$v;
$this->Left=$l;
$this->Right=$r;
}
public function Preorder($f)
{
$f($this->Value);
if($this->Left != null) $this->Left->Preorder($f);
if($this->Right != null) $this->Right->Preorder($f);
}
public function Inorder($f)
{
if($this->Left != null) $this->Left->Inorder($f);
$f($this->Value);
if($this->Right != null) $this->Right->Inorder($f);
}
public function Postorder($f)
{
if($this->Left != null) $this->Left->Postorder($f);
if($this->Right != null) $this->Right->Postorder($f);
$f($this->Value);
}
}
$tree = new Node(1,
new Node(2,
new Node(4,
new Node(7)),
new Node(5)),
new Node(3,
new Node(6,
new Node(8),
new Node(9))));
$f=function($x){echo $x;};
$tree->Preorder($f);
echo " ";
$tree->Inorder($f);
echo " ";
$tree->Postorder($f);
?>
Python
node = lambda v,l,r:[v,l,r]
leaf = lambda v:[v,[],[]]
null = []
def Preorder(f,t):
if not t == []:
v,l,r = t
f(v)
Preorder(f,l)
Preorder(f,r)
def Inorder(f,t):
if not t == []:
v,l,r = t
Inorder(f,l)
f(v)
Inorder(f,r)
def Postorder(f,t):
if not t == []:
v,l,r = t
Postorder(f,l)
Postorder(f,r)
f(v)
t = node(1,
node(2,
node(4,
leaf(7),
null),
leaf(5)),
node(3,
node(6,
leaf(8),
leaf(9)),
null))
f = lambda x:print(x,end=' ')
Preorder(f,t)
print()
Inorder(f,t)
print()
Postorder(f,t)
Shell
node()
{
value[$1]=$1
left[$1]=$2
right[$1]=$3
}
node 1 2 3
node 2 4 5
node 3 6
node 4 7
node 5
node 6 8 9
node 7
node 8
node 9
traversal()
{
local nx=$1
shift
for branch in $@ ; do
case "$branch" in
left) if [ ${left[$nx]} ]; then traversal ${left[$nx]} $@ ; fi ;;
right) if [ "${right[$nx]}" ]; then traversal ${right[$nx]} $@ ; fi ;;
self) printf "%d " ${value[$nx]} ;;
esac
done
}
preorder() { traversal $1 self left right ; }
inorder() { traversal $1 left self right ; }
postorder() { traversal $1 left right self ; }
preorder 1
echo ''
inorder 1
echo ''
postorder 1
Wolfram Language
preorder[a_] := a;
preorder[a_[b__]] := Flatten@{a, preorder /@ {b}};
inorder[a_] := a;
inorder[a_[b_, c_]] := Flatten@{inorder@b, a, inorder@c};
inorder[a_[b_]] := Flatten@{inorder@b, a};
postorder[a_] := a;
postorder[a_[b__]] := Flatten@{postorder /@ {b}, a};