Column website www.jiuzhang.com | | nine chapters algorithm
Tree concepts are very confusing, let’s take you through the concepts of trees!
About the Tree: full binary Tree: A binary Tree in which each node has exactly zero or two children.
Perfect binary tree: A binary tree with all leaf nodes at the same depth. All internal nodes have degree 2 [1]
Full binary tree: each node has 0 or 2 children.
The difference between Full Binary Tree and Complete Binary Tree: All The leaves have The same depth and all The inner nodes have 2 children. (1). a binary tree T is full if each node is either a leaf or possesses exactly two child nodes. (2). a binary tree T with n levels is complete if all levels except possibly the last are completely full, and the last level has all its nodes to the left side. [2]
The difference between full and complete binary trees:
Full binary tree: each node has either leaves or 2 children
Complete binary tree: Every level is complete except the last level, where all nodes are on the left. AVL Trees: AVL trees are self-balancing binary search trees. These trees are named after their two lair G.M. Adel ‘son-vel ‘skii and E.M. Landis. [3]
The height/depth of a tree:
The height of a node is the length of the longest downward path to a leaf from that node. The height of the root is the height of the tree.
The depth of a node is the length of the path to its root (i.e., (4) This is commonly needed in the manipulation of the various self-balancing trees, AVL Trees in particular. The root node has depth zero, leaf nodes have height zero, and a tree with only a single node (hence both a root and leaf) has depth and height zero. Conventionally, An empty tree (tree with no nodes, if such are allowed) has depth and height −1.[4]
The root depth is 0, and the leaf height is 0. Trees with only one node have a depth height of 0.
By convention, an empty tree has a depth and height of -1
References:
- Xlinux. Nist. Gov/dads / / HTML /…
- Courses.cs.vt.edu/~cs3114/Fal…
- Courses.csail.mit.edu/6.006/fall0…
- www.cs.cmu.edu/~adamchik/1…
Welcome to follow my wechat official account: Ninechapter.
Elite programmer exchange community, regular release of interview questions, interview skills, job information, etc
