二叉树
2023-08-18 11:40:04
发布于：广东
3阅读
0回复
0点赞
由@意大利西兰花上课 手打，@意大利西兰花上课 手打，@意大利西兰花上课 手打
树的定义
树的度：结点拥有的子树的数量为结点的度，度为0的结点为叶子结点，度不为0的结点为分支节点，树的度定义为树的所有结点中度的最大值。
注意：n个结点的树，有且只有n-1条边
二叉树
二叉树是一种度数最大为2的树形结构，即二叉树的每个结点，每个结点的字结点严格区分左结点和右结点，它的两棵子树成为左子树、右子树。
完全二叉树
若某一二叉树深k层外，其他层的结点总数达到最大值，即第i（i<k）层结点为2的i-1。且第k层结点树小于第2的k-1并靠左侧连续，这种特殊形态的二叉树，称之为完全二叉树。
性质：
—性质1：
在二叉树的第i层上最多有2的i-1个结点（i>=1）。第1层最多1个结点，第二层最多两个结点，第3层最多4个结点…
—性质2：
深度为k的二叉树至多有(2的k) -1个结点（k>=1)
—性质3：
任意一颗二叉树，若其叶子结点的数量为n的0，度为2的结点数量为n的2，则：n的0与n的2一定满足n的0=n的2+1。
—性质4：
具有n（n>=0）个结点的完全二叉树的深度为[log2(n)]+1。[]表示下取整.。
—性质5：
若将一棵有n个结点的完全二叉树自顶向下，同一层自左向右连续给节点编号1，2，...,n则：
1、若结点编号i=1，则结点i为根，无父结点。
2、则i>1,则i的父结点编号为i/2
3、针对编号为i的结点：
——3、1其左孩子编号为2 * i（2 * i <= n）
——3、2其右孩子编号为2 * i + 1(2 * i + 1<=n)
这里空空如也
有帮助，赞一个