iframe-proxy | Sunbelt Computer Software

History

150 lines (131 loc) · 3.05 KB

Raw

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

* <!--

* This program is distributed under

* the terms of the MIT license.

* Please see the LICENSE file for details.

* -->

* Write an algorithm to do preorder traversal of the binary search

* tree below. The traverse operation should take a delegete to print

* the value of the node being traversed. Use the node structure in 002.js

* You may NOT use recursion.

* 110

* / \

* 62 141

* / \ / \

* 28 79 130 190

* /

* 121

/*____________________________________________________________________________*/

/**

* @class {public} Node

* A typical binary tree node.

* @param {Node} left - the left node.

* @param {Node} right - the right node.

* @param {Integer} value - the value of this node.

function Node(left, right, value) {

this.left = left;

this.right = right;

this.value = value;

}

* Sample tree structure.

var root = new Node(

new Node(

new Node(null, null, 28),

new Node(null, null, 79),

new Node(

new Node(null, null, 121),

null,

130),

new Node(null, null, 190),

141

110

);

/*____________________________________________________________________________*/

/**

* Sample delegate.

function delegate(node) {

console.log(node.value);

console.log(node);

}

/**

* @function {public static} preorderTraversal

* Does a pre-order traversal on the tree.

* @param {Node} node - the node to start.

* @param {Function} delegate - the delegate to execute for each node.

function preorderTraversal(node, delegate) {

var stack = [];

stack.push(node);

var current = null;

var right = null;

var left = null;

while (true) {

current = stack.pop();

if (!current) {

break;

}

delegate(current);

right = current.right;

if (right) {

stack.push(right);

}

left = current.left;

if (left) {

stack.push(left);

}

/*____________________________________________________________________________*/

preorderTraversal(root, delegate);

Output: ($ /usr/bin/node 006.js)

110

{ left:

{ left: { left: null, right: null, value: 28 },

right: { left: null, right: null, value: 79 },

value: 62 },

right:

{ left: { left: [Object], right: null, value: 130 },

right: { left: null, right: null, value: 190 },

value: 141 },

value: 110 }

{ left: { left: null, right: null, value: 28 },

right: { left: null, right: null, value: 79 },

value: 62 }

{ left: null, right: null, value: 28 }

{ left: null, right: null, value: 79 }

141

{ left:

{ left: { left: null, right: null, value: 121 },

right: null,

value: 130 },

right: { left: null, right: null, value: 190 },

value: 141 }

130

{ left: { left: null, right: null, value: 121 },

right: null,

value: 130 }

121

{ left: null, right: null, value: 121 }

190

{ left: null, right: null, value: 190 }

Sunbelt Computer Software

PL/B Language Development and Support

Navigation Menu

Uh oh!

Sunbelt Computer Software

PL/B Language Development and Support

Uh oh!

FilesExpand file tree

007.js

Latest commit

History

007.js

File metadata and controls