Binary tree
每个节点至多有两个子节点
In computer science, a binary tree is a tree data structure in which each node has at most two children, which are referred to as the left child and the right child.
A recursive definition using just set theory notions is that a (non-empty) binary tree is a tuple (L, S, R), where L and R are binary trees or the empty set and S is a singleton set containing the root.
It is also possible to interpret a binary tree as an undirected, rather than a directed graph, in which case a binary tree is an ordered, rooted tree.
A binary tree is a special case of an ordered K-ary tree, where K is 2.
rooted
A rooted binary tree has a root node and every node has at most two children.
full
满二叉树
每个节点要么没有子节点,要么有2个子节点
A full binary tree (sometimes referred to as a proper or plane binary tree) is a tree in which every node has either 0 or 2 children.
Recursive definition, A full binary tree is either:
- A single vertex
- A tree whose root node has two subtrees, both of which are full binary trees.
perfect
完美二叉树
所有内部节点都有两个子节点
所有叶子节点处于同一深度
A perfect binary tree is a binary tree in which all interior nodes have two children and all leaves have the same depth or same level.
complete
完全二叉树
除了最后一层外,所有节点都是满的
最后一层的所有节点都靠向左边
完美二叉树一定是完全二叉树,完全二叉树却没必要是完美二叉树
A complte binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes at the last level are as far left as possible. It can have between 1 and (h power of 2) nodes at the last level h.
balanced
平衡二叉树
左右子树的高度相差不超过1
A balanced binary tree is a binary tree structure in which the left and right subtrees of every node differ in height by no more than 1.
degenerate
退化二叉树
每个父节点仅有一个子节点
类似于链表
A degenerate (or pathological) tree is where each parent node has only one associated child node.
This means the tree will behave like a linked list data structure.
properties of binary trees
Root
The root of a tree is the top most node of the tree that has no parent node. There is noly one root node in every tree.
Edge
Edge acts as a link between the parent node and the child node.
Leaf (external node)
A node that has no child is known as the leaf node.
Depth
Depth of the node is the distance of from the roof node to that particular node.
Height
The height of a node in a rooted tree is the number of edges in a longest path, going away from the root (i.e. its nodes have strictly increasing depth), that starts at that node and ends at a leaf. (节点高度)
The height of a rooted tree is the height of its root. That is, the height of a tree is the number of edges in a longest possible path, going away from the root, that starts at the root and ends at a leaf. (树高度)
- 一颗高为h的满树的节点树至少为2h+1, 至多为(h+1) power of 2 minus 1
- 一颗节点树为n的完美二叉树的叶子节点l = (n + 1) / 2
> 因为树高是l以2为底的对数,知道树高可以求得完美二叉树的节点树n, 可以验证上面公式
-
一颗满二叉树的叶子节点和完美二叉树的总节点树之间上述关系也成立(叶子节点比非叶子节点多1)
-
一颗平衡满二叉树高度等于叶子节点(l)以2为底的对数+1
-
完美满二叉树叶子节点l = 树高h power of 2, 总节点树n=h+1 power of 2, 再减1
-
一颗n个节点的二叉树的null links(参见Notes笔记)个数为 n + 1
-
一颗节点树为n的完全二叉树的内部节点为n/2向下取整,参见Notes笔记
-
一颗叶子节点树为n0, degree为2的节点树为n2非空二叉树,有 n0 = n2 + 1(参见Notes笔记)
CommonOperations
insertion
In binary trees, a node that is inserted is specified as to whose child it will be.
References
Degress of a node
The degress of a node of a tree is the number of subtrees having this node as a root. In other words, the degree is the number of descendants of a node. If the degree if zero, it is called a terminal or leaf node of a tree.