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

This article mainly explains "what is the basic concept of binary tree in Java". The content of the explanation in this article is simple and clear, and it is easy to learn and understand. Please follow the editor's train of thought to study and learn "what is the basic concept of binary tree in Java".

1. Tree structure 1.1 concept

Tree is a kind of nonlinear data structure, which is a hierarchical set composed of n (n > = 0) finite nodes. It is called a tree because it looks like an upside-down tree, that is to say, it has roots up and leaves down.

1.2 Concepts (important)

a. Degree of node: the number of subtrees of the node; as shown in the figure above, the degree of An is 6 and the degree of J is 2.

b. Degree of the tree: in the tree, the degree of the largest node is the degree of the number. As shown in the figure above, the degree of the tree is 6.

c. Leaf node (terminal node): node with degree 0 (node without subtree)

d. Parent node / parent node: as shown above: d is the parent node of H

Child node / child node: as shown above: h is the child node of D.

e. Root node: a node without parents, as shown in the figure above: a

f. The hierarchy of nodes: defined from the root, the root is layer 1, the child node of the root is layer 2, and so on

g. Height or depth of the tree: the maximum level of nodes in the tree; as shown in the figure above: the height of the tree is 4

two。 Binary Tree (focus) 2.1 concept

Each node has at most two subtrees, the left subtree of the degree root-> the right subtree of the root.

/ / preorder traversal: public static void preOrder (TreeNode root) {if (root==null) {return;} System.out.print (root.val+ ""); preOrder (root.left); preOrder (root.right);}

2. LNR: mid-order traversal (Inorder Traversal)-- the left subtree of the root-- > the root node-- > the right subtree of the root.

/ / traversing public static void inOrder (TreeNode root) {if (root==null) {return;} preOrder (root.left); System.out.print (root.val+ ""); preOrder (root.right);}

3. LRN: post-order traversal (Postorder Traversal)-- the left subtree of the root-- > the right subtree of the root-> the root node.

/ / traverse public static void postOrder (TreeNode root) {if (root==null) {return;} preOrder (root.left); preOrder (root.right); System.out.print (root.val+ "");}

2.6.2 traversal of binary trees (iteration)

1. Preorder traversal

/ / method 2 (iterative) / / preorder traversal (iterative) public static void preOrderNonRecursion (TreeNode root) {if (root==null) {return;} Deque stack=new LinkedList (); stack.push (root); while (! stack.isEmpty ()) {TreeNode cur=stack.pop (); System.out.print (cur.val+ "") If (cur.rightlighting null) {stack.push (cur.right);} if (cur.leftbread null) {stack.push (cur.left);}

two。 Mid-order traversal

/ / method 2 (iterative) / / medium order traversal (iterative) public static void inorderTraversalNonRecursion (TreeNode root) {if (root==null) {return;} Deque stack=new LinkedList (); / / Node TreeNode cur=root currently reached While (! stack.isEmpty () | curving null) {/ / regardless of three, seven and twenty-one, go all the way to the root ~ while (cursive null) {stack.push (cur); cur=cur.left. } / / cur is empty at this time, indicating that when you reach null, the node cur=stack.pop (), System.out.print (cur.val+ ""), which is empty in the left tree, is stored at the top of the stack. / / continue to visit the right subtree cur=cur.right;}}.

3. Post-order traversal

/ / method 2 (iterative) / / Post-order traversal (iterative) public static void postOrderNonRecursion (TreeNode root) {if (root==null) {return;} Deque stack=new LinkedList (); TreeNode cur=root; TreeNode prev=null; while (! stack.isEmpty () | | cursive null) {while (cursive null) {stack.push (cur) Cur=cur.left;} cur=stack.pop (); if (cur.right==null | | prev==cur.right) {System.out.print (cur.val+ ""); prev=cur; cur=null;} else {stack.push (cur); cur=cur.right }}}

2.6.3 basic operation of binary tree

1. Count the number of nodes (recursion & iteration)

/ / method 1 (recursion) / / pass in the root node of a binary tree to count the total number of nodes in the current binary tree, and return the number of nodes / / the access at this time is no longer the output node value, but the counter + 1 operates public static int getNodes (TreeNode root) {if (root==null) {return 0;} return 1+getNodes (root.left) + getNodes (root.right) } / / method 2 (iterative) / / count the number of nodes in the current tree using sequence traversal public static int getNodesNoRecursion (TreeNode root) {if (root==null) {return 0;} int size=0; Deque queue=new LinkedList (); queue.offer (root); while (! queue.isEmpty ()) {TreeNode cur = queue.poll () Size++; if (cur.left! = null) {queue.offer (cur.left);} if (cur.right! = null) {queue.offer (cur.right);}} return size;}

two。 Calculate the number of leaf nodes (recursion & iteration)

/ / method 1 (recursion) / / pass in the root node of a binary tree and count the number of leaf nodes of the current binary tree public static int getLeafNodes (TreeNode root) {if (root==null) {return 0;} if (root.left==null & & root.right==null) {return 1;} return getLeafNodes (root.left) + getLeafNodes (root.right) } / / method 2 (iterative) / / count the number of leaf nodes public static int getLeafNodesNoRecursion (TreeNode root) {if (root==null) {return 0;} int size=0; Deque queue=new LinkedList (); queue.offer (root); while (! queue.isEmpty ()) {TreeNode cur=queue.poll () If (cur.left==null & & cur.right==null) {size++;} if (cur.leftbread null) {queue.offer (cur.left);} if (cur.rightlighting null) {queue.offer (cur.right);}} return size;}

3. Calculate the number of k-layer nodes

/ / find the number of nodes in the k layer of the binary tree with root as the root node public static int getKLevelNodes (TreeNode root,int k) {if (root==null | | k)

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.