BINARY SEARCH TREES - Introduction to Java Programming: Comprehensive Version - page 938

54
55 // Create the new node and attach it to the parent node
56 if (e.compareTo(parent.element) < 0 )
57 parent.left = createNewNode(e);
58 else
59 parent.right = createNewNode(e);
60 }
61
62 size++;
63

link to parent

increase size

return true ; // Element inserted successfully

64 }
65
66

protected TreeNode<E> createNewNode(E e) {

create new node

67 return new TreeNode<>(e);

68 }
69
70 @Override /** Inorder traversal from the root */
71 public void inorder() {
72 inorder(root);
73 }
74
75 /** Inorder traversal from a subtree */
76 protected void inorder(TreeNode<E> root) {
77 if (root == null ) return ;
78 inorder(root.left);
79 System.out.print(root.element + " " );
80 inorder(root.right);
81 }
82
83 @Override /** Postorder traversal from the root */
84 public void postorder() {
85 postorder(root);
86 }
87
88 /** Postorder traversal from a subtree */
89 protected void preorder(TreeNode<E> root) {
90 if (root == null ) return ;
91 postorder(root.left);
92 postorder(root.right);
93 System.out.print(root.element + " " );
94 }
95
96 @Override /** Preorder traversal from the root */
97 public void preorder() {
98 preorder(root);
99 }
100
101 /** Preorder traversal from a subtree */
102 protected void postorder(TreeNode<E> root) {
103 if (root == null ) return ;
104 System.out.print(root.element + " " );
105 preorder(root.left);
106 preorder(root.right);
107 }
108
109

inorder

recursive helper method

postorder

recursive helper method

preorder

recursive helper method

/** This inner class is static, because it does not access

110 any instance members defined in its outer class */

inner class

111 public static class TreeNode<E extends Comparable<E>> {

112 protected E element;

113 protected TreeNode<E> left;