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

Binary tree degree: the node has the number of subtrees the leaf node: the depth of the node tree without child nodes: the number of layers of the node, and the root node defaults to the first layer. Order: the left and right position of the tree cannot be changed.

Binary trees are often used as binary search trees and binary heaps

Property 1: there are at most 2 ^ {imur1} nodes in the I layer of a non-empty binary tree property 2: a binary tree with depth k has at most 2 ^ k-1 nodes property 3: for any binary tree T, if the number of terminal nodes is n 0 and the number of nodes with degree 2 is n 2, then n 0 = n 2 + 1 (n 0 represents the total number of nodes with degree 0, n 2 represents the total number of nodes with degree 2) property 4: in a complete binary tree A complete binary tree with n nodes has a depth of [log2n] + 1, where [log2n] + 1 is rounded down. Property 5: if a complete binary tree with n nodes is numbered from top to bottom and from left to right, then for any node numbered I in the complete binary tree: (1) if itree 1, then the node is the root of the binary tree and has no parents, otherwise, the node numbered [ijump 2] is its parent node. (2) if 2i > n, the node has no left child, otherwise, the node numbered 2i is its left child node. (3) if 2i+1 > n, the node has no right child node, otherwise, the node numbered 2i+1 is its right child node. Except for the leaf node, every node of the full binary tree has the left and right cotyledons and the leaf node is at the bottom of the binary tree. A binary tree with a depth of k and 2 ^ k-1 nodes is called a full binary tree, and the leaf nodes of the complete binary tree can only appear in the lowest and lower layers. and the bottom layer of the nodes are concentrated in the leftmost positions of the binary tree is a very efficient data structure, the heap is a kind of complete binary tree or nearly complete binary tree, so the efficiency is very high. For example, the commonly used sorting algorithm, Dijkstra algorithm and Prim algorithm can only be optimized by heap, and the efficiency of the binary sort tree which is tested almost every time also needs to be improved with the help of balance, which is based on the complete binary tree. The leaf node can only appear on the largest two layers. For any node, if the maximum level of the offspring under the right branch is L, then the maximum level of the offspring under the left branch must be L or Lao1. The depth of a complete binary tree with n nodes is int (log2n) + 1.

For simplicity, complete binary trees are usually stored in arrays rather than linked lists:

(1) if I is odd and I > 1, then the left brother of tree is tree [I-1]; (2) if I is even and the father node of i1 div tree is tree [I div 2]; (4) if 2i

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.