js二叉树

二叉树

二叉树(Binary Tree)是一种树形结构，它的特点是每个节点最多只有两个分支节点，一棵二叉树通常由根节点，分支节点，叶子节点组成。而每个分支节点也常常被称作为一棵子树。

• 根节点：二叉树最顶层的节点

• 分支节点：除了根节点以外且拥有叶子节点

• 叶子节点：除了自身，没有其他子节点

常用术语

在二叉树中，我们常常还会用父节点和子节点来描述，比如图中2为6和3的父节点，反之6和3是2子节点

二叉树的三个性质

1. 在二叉树的第i层上，至多有2^i-1个节点

   • i=1时，只有一个根节点，2^(i-1) = 2^0 = 1
     2.. *深度为k的二叉树至多有2^k-1个节点

   • i=2时，2^k-1 = 2^2 - 1 = 3个节点

2. 对任何一棵二叉树T，如果总结点数为n0，度为2(子树数目为2)的节点数为n2,则n0=n2+1

树和二叉树的三个主要差别

• 树的节点个数至少为1，而二叉树的节点个数可以为0
• 树中节点的最大度数(节点数量)没有限制,而二叉树的节点的最大度数为2
• js二叉树树的节点没有左右之分，而二叉树的节点有左右之分

二叉树分类

二叉树分为完全二叉树(complete binary tree)和满二叉树(full binary tree)

• 满二叉树：一棵深度为k且有2^k - 1个节点的二叉树称为满二叉树完全二叉树：
• 完全二叉树是指最后一层左边是满的，右边可能满也可能不满，然后其余层都是满的二叉树称为完全二叉树(满二叉树也是一种完全二叉树)

二叉搜索树

二叉搜索树满足以下的几个性质：

• 若任意节点的左子树不空，则左子树上所有节点的值均小于它的根节点的值；
• 若任意节点的右子树不空，则右子树上所有节点的值均大于它的根节点的值；
• 任意节点的左、右子树也需要满足左边小右边大的性质

我们来举个例子来深入理解以下

一组数据：12,4,18,1,8,16,20
由下图可以看出，左边的图满足了二叉树的性质，它的每个左子节点都小于父节点，右子节点大于其父节点，同时左子树的节点都小于根节点，右子树的节点都大于根节点

遍历

• 中序遍历(inorder)：

先遍历左节点，再遍历自己，最后遍历右节点，输出的刚好是有序的列表

• 前序遍历(preorder)：

先自己，再遍历左节点，最后遍历右节点

• 后序遍历(postorder)：

先左节点，再右节点，最后自己

原文：https://www.cnblogs.com/hff-syt/p/12422770.html