Shulou(Shulou.com)06/01 Report--

This article shows you how to achieve a binary tree in Java, the content is concise and easy to understand, it can definitely brighten your eyes. I hope you can get something through the detailed introduction of this article.

Public class BinaryTreeLinked implements BinTree {protected BinTreeNode root;protected Strategy strategy;public BinaryTreeLinked () {this (null);} public BinaryTreeLinked (BinTreeNode root) {this (root,new DefaultStrategy ());} public BinaryTreeLinked (BinTreeNode root, Strategy strategy) {this.root = root; this.strategy = strategy;} / / return the size of the tree public int getSize () {return root==null?0:root.getSize ();} / / determine whether the tree is empty public boolean isEmpty () {return root==null } / / return the root node reference public BinTreeNode getRoot () {return root;} / / get the height of the tree public int getHeight () {return isEmpty ()-1:root.getHeight ();} / / find element e in the tree and return its node public BinTreeNode find (Object e) {return searchE (root,e);} / / Recursive lookup element eprivate BinTreeNode searchE (BinTreeNode rt, Object e) {if (rt==null) return null / / if it is a root node, return the root if (strategy.equal (rt.getData (), e)) return rt;// otherwise find BinTreeNode v = searchE (rt.getLChild (), e) in the left subtree; / / if not found, look for if (v==null) v = searchE (rt.getRChild (), e) in the right subtree; return v;}

It is difficult to jump from e to c. It is important to understand that the recursive function jumps from the innermost recursive function to the outermost function.

/ / preorder traversal binary tree public Iterator preOrder () {LinkedList list = new LinkedListDLNode (); preOrderRecursion (this.root,list); return list.elements ();} / / Recursive algorithm of preorder traversal private void preOrderRecursion (BinTreeNode rt, LinkedList list) {if (rt==null) return; / / Recursive basis, empty tree directly returns list.insertLast (rt) / / access the root node preOrderRecursion (rt.getLChild (), list); / / traverse the left subtree preOrderRecursion (rt.getRChild (), list); / / traverse the right subtree} / / the non-recursive algorithm private void preOrderTraverse (BinTreeNode rt, LinkedList list) {if (rt==null) return; BinTreeNode p = rt;Stack s = new StackSLinked () While (paired trees null) {while (paired trees null) {/ / go left to the end list.insertLast (p); / / access the root if (p.hasRChild ()) s.push (p.getRChild ()); / / the right subtree root node stacks p = p.getLChild () } if (! s.isEmpty ()) p = (BinTreeNode) s.pop (); / / right subtree root backstack traversing the right subtree}}

/ / order traversal binary tree public Iterator inOrder () {LinkedList list = new LinkedListDLNode (); inOrderRecursion (this.root,list); return list.elements ();} / / Recursive algorithm private void inOrderRecursion (BinTreeNode rt, LinkedList list) {if (rt==null) return; / / Recursive basis for medium order traversal, empty tree directly returns inOrderRecursion (rt.getLChild (), list); / / traverses the left subtree list.insertLast (rt); / / accesses the root node inOrderRecursion (rt.getRChild (), list) / / traversing the right subtree} / / the non-recursive algorithm private void inOrderTraverse (BinTreeNode rt, LinkedList list) {if (rt==null) return; BinTreeNode p = rt; Stack s = new StackSLinked (); while (paired ordered null |! s.isEmpty ()) {while (paired null) {/ / go straight left s.push (p); / / put the root node into the stack p = p.getLChild ();} if (! s.isEmpty ()) {p = (BinTreeNode) s.pop () / / take out the list.insertLast (p) accessed by the root node at the top of the stack; p = p.getRChild (); / / turn to the right subtree of the root to traverse the binary tree public Iterator postOrder () {LinkedList list = new LinkedListDLNode (); postOrderRecursion (this.root,list); return list.elements ();} / / Recursive algorithm private void postOrderRecursion (BinTreeNode rt, LinkedList list) {if (rt==null) return / / Recursive basis, empty tree directly returns postOrderRecursion (rt.getLChild (), list); / / traverses left subtree postOrderRecursion (rt.getRChild (), list); / / traverses right subtree list.insertLast (rt); / / visits root node} / / non-recursive algorithm private void postOrderTraverse (BinTreeNode rt, LinkedList list) {if (rt==null) return; BinTreeNode p = rt; Stack s = new StackSLinked () While (paired null null |! s.isEmpty ()) {while (paired null) {/ / s.push (p); / put the root node into the stack if (p.hasLChild ()) p = p.getLChild (); else p = p.getRChild ();} if (! s.isEmpty ()) {p = (BinTreeNode) s.pop (); / / remove the list.insertLast (p) accessed by the root node at the top of the stack } / / if the condition is satisfied, the right subtree of the top root node of the stack has been accessed, and the while (! s.isEmpty () & ((BinTreeNode) s.peek ()). GetRChild () = = p) {p = (BinTreeNode) s.pop (); list.insertLast (p);} / / turn to the right subtree of the top root node of the stack to continue traversing the right subtree of the top root node of the stack in the following order: if (! s.isEmpty ()) p = (BinTreeNode) s.peek (). GetRChild (); else p = null }} / / traversing the binary tree public Iterator levelOrder () {LinkedList list = new LinkedListDLNode (); levelOrderTraverse (this.root,list); return list.elements ();} / / traversing private void levelOrderTraverse (BinTreeNode rt, LinkedList list) {if (rt==null) return; Queue q = new QueueArray (); q.enqueue (rt); / / Root node queuing while (! q.isEmpty ()) {BinTreeNode p = (BinTreeNode) q.dequeue () / / fetch the queue header p and visit list.insertLast (p); if (p.hasLChild ()) q.enqueue (p.getLChild ()); / / enroll the non-empty left and right children of p into the queue if (p.hasRChild ()) q.enqueue (p.getRChild ());} package dsa.adt;import dsa.adt.List;public interface BinTree {/ / return the size of the tree public int getSize (); / / determine whether the tree is empty public boolean isEmpty () / / return root node reference public BinTreeNode getRoot (); / / get the height of the tree public int getHeight (); / / find element e in the tree and return its node public BinTreeNode find (Object e); / / preorder traverse the binary tree public Iterator preOrder (); / / traverse the binary tree public Iterator inOrder () in the middle order; / / traverse the binary tree public Iterator postOrder () in the later order; / / traverse the binary tree public Iterator levelOrder () by layer;} public class BinTreeNode implements Node {private Object data / / data field private BinTreeNode parent; / / parent node private BinTreeNode lChild; / / left child private BinTreeNode rChild; / / right child private int height; / / height private int size; of the subtree rooted at the node / / the number of descendants of the node (including the node itself)

Public BinTreeNode () {this (null);} public BinTreeNode (Object e) {data = e; parent = lChild = rChild = null; height = 0; size = 1;} / / get the data field public Object getData () {return data;} / / determine whether there is a father public boolean hasParent () {return parentchild null;} / determine whether there is a right child public boolean hasRChild () {return rChildchild null } / / determine whether it is the left child public boolean isLChild () {return (hasParent () & & this==parent.lChild);} / / determine whether it is the right child public boolean isRChild () {return (hasParent () & this==parent.rChild);} / / take the height of the node, that is, the height of the tree rooted at the node public void updateHeight () {return height;} / / update the height of the current node and its ancestors () {int newH = 0 / / the new height is initialized to 0, and the height is equal to the left and right subtree height plus 1 medium-large if (hasLChild ()) newH= Math.max (newH,1+getLChild (). GetHeight ()); if (hasRChild ()) newH= Math.max (newH,1+getRChild (). GetHeight ()); if the height of if (newH==height) return; / / does not change, directly return height = newH; / / otherwise update height if (hasParent ()) getParent (). UpdateHeight () / / Recursively update the height of ancestors}

This method of updating height is mainly used to add and remove nodes, and the idea of recursion makes the code particularly brief and beautiful here. If you do not understand, please combine the following getParent, getLChild, getRChild methods to see.

/ / take the number of public int getSize () {return size;} / / update the current node and the descendants of its ancestors public void updateSize () {size = 1; / / initialize to 1, and the node itself if (hasLChild ()) size + = getLChild (). GetSize (); / / plus the size of the left subtree if (hasRChild ()) size + = getRChild (). GetSize () / / add the size of the right subtree if (hasParent ()) getParent (). UpdateSize (); / / Recursive update ancestor size}

UpdateSize and updateHeight are two sibling methods.

/ / take the parent node public BinTreeNode getParent () {return parent;} / / break the relationship with the father public void sever () {if (! hasParent ()) return;// if there is no parent node, then directly end if (isLChild ()) parent.lChild = null;// if it is a left child, the left child of the parent node is set to nullelse parent.rChild = null;parent.updateHeight (); / / update the parent node and its ancestor height parent.updateSize () / / Update the parent node and its ancestor size parent = null;}

/ / take the left child public BinTreeNode getLChild () {return lChild;} / / set the left child of the current node, and return to the original left child public BinTreeNode setLChild (BinTreeNode lc) {BinTreeNode oldLC = this.lChild;if (hasLChild ()) {lChild.sever ();} / / disconnect the relationship between the current left child and the node if (lcchild parent null) {lc.sever (); / / disconnect the relationship between lc and its parent node this.lChild = lc / / determine the father-son relationship lc.parent = this;this.updateHeight (); / / update the current node and its ancestor height this.updateSize (); / / update the current node and its ancestor size} return oldLC; / / return to the original left child}

/ / take the right child public BinTreeNode getRChild () {return rChild;} / / set the right child of the current node, return to the original right child public BinTreeNode setRChild (BinTreeNode rc) {BinTreeNode oldRC = this.rChild;if (hasRChild ()) {rChild.sever ();} / / disconnect the relationship between the current right child and the node if (rclocknull) {rc.sever (); / / disconnect the relationship between lc and its parent node this.rChild = rc / / determine the father-son relationship rc.parent = this;this.updateHeight (); / / update the current node and its ancestor height this.updateSize (); / / update the current node and its ancestor size} return oldRC; / / return to the original right child}}

The method of setting the right child is similar to that of setting the left child, please refer to the setLChild method.

Package dsa.adt;public interface Node {/ / get node data field public Object getData (); / / set node data field public void setData (Object obj);} package dsa.strategy;public interface Strategy {/ / determine whether two data elements are equal public boolean equal (Object obj1, Object obj2); / * * compare the size of two data elements * if obj1

Obj2 returns 1 * / public int compare (Object obj1, Object obj2);} package dsa.strategy;public final class DefaultStrategy implements Strategy {public boolean equal (Object obj1, Object obj2) {return obj1.toString (). Equals (obj2.toString ());} public int compare (Object obj1, Object obj2) {int comp= obj1.toString (). CompareTo (obj2.toString ()); if (comp==0) return 0 (comp > 0) return 1 }} the above is how to implement a binary tree in Java. Have you learned any knowledge or skills? If you want to learn more skills or enrich your knowledge reserve, you are welcome to follow the industry information channel.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.