Two fork tree: each node has at most two subtrees.
Full two fork tree: the number of nodes in each layer is the largest node number.
Complete binary tree: Leaf nodes are in the last two layers; for any node, the depth of the left subtree is 1 or equal to the depth of the right subtree
Nature:
Two fork tree: layer I, at most there are 2^ (i-1) nodes.
Two fork tree: the depth of K two fork tree, at most there are (2^k) -1 nodes.
Full two fork tree: the number of nodes in the full two fork tree with a depth of K is (2^k) -1
Binary tree: any binary tree, degree 0 of the number of nodes n0, degree 1 of the number of nodes n1, degree 2 of the number of nodes relationship: N0 = N2 + 1, the total number of nodes n
Reason: N0 + N1 + N2 = n Except for the root node, there is one branch entering the number of branches n-1, branches are issued by degree 1 or degree 2 node N1 + 2 * N2 = n-1 according to these two formulas get n 0 = N2 + 1
Complete Binary Tree: Any complete Binary Tree with n nodes has a depth of log 2 as the bottom n to integer + 1
Complete two branch tree: any complete two fork tree is numbered by nodes.
i=1，The node is the root of a complete two binary tree.
i>1，The node is not a root, and the number of the parent of the node is i/2 down.
The number of a node is I. If 2*i is greater than n, it means that the node has no left child. Otherwise, the number of the left child is 2*i.
The number of a node is I. If 2*i+1 is greater than n, the node has no right child, otherwise, the right child is 2*i
storage
（1）Sequential storage
The binary tree is stored sequentially from top to bottom from left to right in a set of memory units with consecutive addresses. The binary tree is stored in the form of the corresponding complete binary tree (the node numbered I in the complete binary tree is stored in the component whose array subscript is i-1). If a node does not exist, the location is stored at 0.
The length of the array (2^k) -1 the depth of the two fork tree is k, and the space is wasted.
（2）Linked Storage
Data domain left child right child
Pointer fields are wasteful: a binary tree with n nodes has n + 1 null pointer fields, n nodes, 2 * n pointer fields, and N-1 branches, so there is n + 1 pointer waste
public class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int x) { val = x; } @Override public String toString() { return "TreeNode [val=" + val + ", left=" + left + ", right=" + right + "]"; } }
Two tree traversal
Preorder
public static void preOrder(TreeNode node){ //Preorder traversal, root left and right, recursive implementation//When each call is made, the parameter node is the root node of the current subtree. if(node == null){ //If the current node is null, go back directly. return; }else{ //If the current node is not null, output the value of the current node and then traverse the left and right subtree of the current node. System.out.print(node.val+" "); preOrder(node.left); preOrder(node.right); } } public static void preOrder2(TreeNode root){ //Preorder traversal, root around, with stack, non recursive implementation//If the root node is null, it indicates that it is an empty tree and returns directly. if(root == null){ return; }else{ //If the root node is not null, traversal Stack<TreeNode> stack = new Stack<TreeNode>(); //First root node into stack. stack.push(root); while(!stack.isEmpty()){//When the stack is empty, it indicates that it has been traversed.//The node stored on the top of the stack will traverse its left and right subtree. TreeNode node = stack.pop(); System.out.print(node.val+" "); //Since the stack is a first-in, second-out data structure, the root node of the right subtree of the current node is put on the stack, and then the root node of the left subtree of the current node is put on the stack. if(node.right != null){ stack.push(node.right); } if(node.left != null){ stack.push(node.left); } } } }
Middle order
public static void inOrder(TreeNode node){ //In order traversal, left root, right, recursive implementation if(node == null){ return; }else{ //When the current node is not null, first traverse the left subtree of the current node, then output the value of the current node, and finally traverse the right subtree of the current node inOrder(node.left); System.out.print(node.val+" "); inOrder(node.right); } } public static void inOrder2(TreeNode root){ //In order traversal, left root, right, recursive implementation if(root == null){ return; }else{ Stack<TreeNode> stack = new Stack<TreeNode>(); //On the left root, the first one should be the most left left node of the two fork tree.//Starting from the root node, we always look for the left node of the node until the most left left node. while(root!=null || !stack.isEmpty()){ while(root!=null){ stack.push(root); root = root.left; } //whileAfter the loop, the root value is null, and only if the current node cur has a right subtree, the root value becomes the root node of the right subtree//Now the top element of the stack is the lowest left node, the stack out of the node, output the value of the node, and then see if the node exists right node//If there is a right node, proceed from that right node and look for the left node of the node until the lowest left node TreeNode cur = stack.pop(); System.out.print(cur.val+" "); if(cur.right != null){ root = cur.right; } } } }
Post order
public static void postOrder(TreeNode node){ //Backward sequence traverses the left and right sides. if(node == null){ return; }else{ postOrder(node.left); postOrder(node.right); System.out.print(node.val+" "); } }
sequence
public static void layerOrder(TreeNode root){ //level traversal//Queue implementation if(root == null){ return; }else{ Queue<TreeNode> queue = new LinkedBlockingQueue<TreeNode>(); queue.add(root); while(!queue.isEmpty()){ TreeNode node = queue.remove(); System.out.print(node.val+" "); if(node.left != null){ queue.add(node.left); } if(node.right != null){ queue.add(node.right); } } } }
Two tree reconstruction