二叉树
2025-01-08 10:34:20
发布于：北京
26阅读
0回复
0点赞
一，介绍
二叉树（Binary Tree,简称BT（跟变态无关））是一种度数最大为
二的树形结构，即二叉树的每个节点最多有两个子
节点。
二，五大性质
1，在二叉树的第i层上最多有2^i-1个节点（i>=1）。
2，深度为k的二叉树至多有(2^k)-1个节点（k>
=1)。
3，任意一颗二叉树，若其叶子节点（度为0节点）的
数量为n0，度为2的节点数量为n2，则：n0与n2一
定满足：n0=n2+1
//n0+n1+n2=n(式一）
//n1+2*n2+1=n(式2）
注：若某二叉树深k层，除第k层外其他层的节点总数达
最大值，且第k层节点数小于等于2^(k-1)并靠左侧连续
，这种特殊形态的二叉树，称为完全二叉树。
4，具有n(n>=0)个节点的完全二叉树的深度为floor(log2(n))+1。
5，若将一棵有n个节点的完全二叉树自顶向下，同一层自左向右连续給节点编号1，2，3，4，5，6，……n-2,n-1,n,则：
1.若节点编号i=1，则节点i为跟，无父结点
2.若i>1,则i的父节点编号为i/2。
3.针对编号为i的节点：
3.1 其左孩子编号为2i（2i<=n);
3.1 其右孩子编号为2i+1（2i+1<=n);
三，遍历：
先序遍历（根左右）
中序遍历（左根右）
后序遍历（左右根）
有帮助，赞一个