二叉树的基本概念 _生活知道

大家好,今天小编来为大家解答以下的问题，关于二叉树的基本概念这个很多人还不知道，现在让我们一起来看看吧！
二叉树的定义：一种特殊的树形结构，它的特点是每一个节点至多有两颗子树（即二叉树中不存在度大于2的节点），并且二叉树的子树有左右之分，不能随便颠倒。几种特殊的二叉树：（1）满二叉树：一棵高度为h，且含有2^h – 1个节点的二叉树。（2）完全二叉树：对应相同高度的满二叉树缺失最下层最右侧的一些连续叶子结点。（3）二叉排序树：左子树上所有节点的关键字都小于根节点的关键字；右子树上所有节点的关键字都大于根节点的关键字；左子树和右子树又各是一棵二叉排序树。（左 < 根 < 右）（4）平衡二叉树：任一节点的左子树和右子树的深度之差不超过1的二叉排序树。二叉树的性质：（1）二叉树的第i层上至多有2^i-1^个节点；（2）深度为h的二叉树至多有2^k^ – 1个节点；（3）对任何一个二叉树，若其终端节点树为n0，度为2的节点树为n2，则n0 = n2 + 1;（4）具有n个节点的完全二叉树的深度为log~2~(n + 1)向上取整。（5）对完全二叉树按从上到下、从左到右的顺序顺次编号1,2,3，…，则有以下关系：a. 当i>1时，节点i的双亲的编号为i / 2；b. 当2i<=n时，节点i的左孩子编号为2i，否则无左孩子；c. 当2i+1<=n时，节点i的右孩子编号为2i+1，否则无右孩子；d.节点i所在层次为log~2~i + 1（向下取整）。
【二叉树的基本概念】关于“二叉树的基本概念”的内容，小编就分享到这里了，大家还有哪些需要补充的呢？无妨在评论区留言分享，让更多的朋友受益！您的每一个留言，和每一个赞，都是我前进的动力！喜欢的话记得收藏、分享给身旁的朋友。

二叉树的基本概念

猜你喜欢