自己作图，深入理解二叉树、二叉树和完全二叉树，
目录一、背景
二.基本概念2.1节点
2.2二叉树2.2.1二叉树深度
2.3满是二叉树
2.4完全二叉树2.4.1完全二叉树的线性记忆
2.4.2完全二叉树的建立与遍历
一.背景
二叉树是数据结构中的关键，也是难点。 二叉树是非线性结构，与数组、堆栈、队列等线性结构相比复杂度较高。 要想心中有“树”，就需要用自己的手画画、观察、思考，领会其真谛。 此文结合图形，深入理解二叉树、满二叉树及完全二叉树的概念。
二.基本概念
2.1节点
节点是构成二叉树的最小单元。
-以图形方式显示
-用代码表示
//节点
class Node { (
e；
节点左，右；
节点(e ) {
this.e=e；
this.left=null；
this.right=null；
}
}
2.2二叉树
各节点的度(节点拥有的部分树的数量)为2以下的树称为二叉树
2.2.1二叉树深度
节点的最大层数称为树的深度或高度
2.3满是二叉树
指深度为k且具有2k-1个节点的二叉树。 这意味着所有分支节点都有左右子树，所有叶都在同一层。
下图的深度为4，24-1=15个节点，所有的叶子都在第四层。
2.4完全二叉树
是深度为k的二叉树，k层的节点都是连续靠左隔开的。 而且，1~k-1层的节点也用二叉树覆盖。 这样的二叉树叫做完全二叉树。
2.4.1完全二叉树的线性记忆
为了简单起见，完全二叉树通常使用数组进行线性存储
//*
*完全二叉树的线性记忆
*
* @author zhuhuix
* @date 2020-06-24
*/
公共类完全binarytree {
权限对象[ ] arr；
私有大小；
fullbinarytree(intcapacity ) {
this.arr=new Object[capacity 1]；
this.size=0；
}
公共获取(
return this.size；
}
公共布尔识别
return this.size==0；
}
公共void add (objecte，int index ) {
assert index=this.arr.length；
this.arr[index]=e；
this.size；
}
@Override
公共字符串
return 'FullBinaryTree{
' arr='Arrays.tostring(arr ) )。
'，size=' size
()；
}
publicstaticvoidmain (string [ ] args ) {
fullbinarytreefullbinarytree=newfullbinarytree (26；
//放入下标1到26个字符
for (角色c=' a ' )； c='Z '； c ) {
fullbinarytree.add(c，c - 'A' 1)；
}
system.out.println (fullbinarytree.tostring () )；
}
}
2.4.2完全二叉树的建立与遍历
//*
*创建和遍历完全二叉树
*
* @author zhuhuix
* @date 2020-06-24
*/
公共类二进制树{
//节点
私有节点根；
//节点数
私有大小；
//保存节点
私有阵列列表；
公共二进制树(
this.root=null；
this.size=0；
this.list=new ArrayList (；
}
publicvoidcreatetree (object [ ] array ) {
for(intI=0； I
nodenode=newnode(Array[I]；
list.add(node；
if (this.root==空值) {
this.root=node；
}
}
if(list.size ) )0) {
for(intI=0； I
if(2*I1
list.get(I ).left=list.get )2*I1 )；
}
if(2*I2 )
list.get(I ).right=list.get )2*I2 )；
}
}
}
}
//超前横移
公共void preorder (node root ) {
if (root==空) {
返回；
}
else{
system.out.println (root.get data ()；
}
reorder(root.left )；
reorder(root.right )；
}
公共节点获取根
返回根；
}
//专用内部类-树节点
私有类节点{
对象数据；
节点左，右；
node(objectdata ) {
this.data=data；
this.left=null；
this.right=null；
}
Object getData (
返回数据；
}
}
publicstaticvoidmain (string [ ] args ) {
binarytreebinarytree=newbinarytree (；
Character[] array={'A '、' b '、' c '、' d '、' e '、' f '、' g '、' h '、' I '、' j '、'、' k、' l，
' m '、n '、o '、p '、q '、r '、s '、t '、v '、w '、x '、y '、Z'}；
binarytree.createtree(Array；
binary tree.preorder (binary tree.get root ()；
}
}
相关文章还没有相关文章