Akagi201
9/7/2014 - 1:09 PM

binary-tree.md

What

  • 在计算机科学中, 一个二叉树是一种树的数据结构, 每个节点(node)至多包含2个孩子(左孩子(left child)和右孩子(right child)).
  • 在二叉树中, 每个节点(node)的度数(degree)至多为2.
  • 二叉树被用来实现二叉搜索树(binary search tree)和二叉堆(binary heaps), 并且用于高效低搜索和排序.
  • 二叉树是k元树(k-ary tree)的一种特例, 这里的k=2.

Types

  • rooted binary tree
  • full binary tree(2-tree / strictly binary tree)
  • proper binary tree
  • perfect binary tree
  • complete binary tree
  • infinite complete binary tree
  • balanced binary tree
  • degenerate(pathological) tree

Properties

Refs