🤦‍♂️二叉树的存储结构

🧟‍♀️二叉树的顺序结构
实现一般是按满（完全）二叉树的结点编号，依次存放二叉树中的数据元素。

如果不是完全二叉树呢？
先转化为完全二叉树。

缺点：浪费空间

二叉树的链式结构

二叉链表结点类定义：

class BiNode{
T data;
BiNode lchild,rchild; //左右孩子指针
public BiNode(T data,BiNode left,BiNode right){

this.data = data;     this.lchild = left;
this.rchild = right;  }

public BiNode(T data){ this(data ,null,null);}
public String toString(){return this.data.toString();}
public boolean isLeaf(){

return lchild==null && rchild==null; }

二叉树类定义：

public class BiTree{
BiNode root;
public BiTree(){

this.root = null; //初始化空二叉树    

}
public boolean isEmpty(){

return this.root==null;

}

…… //其他操作

}
在n个结点的二叉链表中，有 n+1 个空指针域。
分析：
n个结点必有2n个链域。
除根结点外，每个结点有且仅有一个双亲，所以只会有n－1个结点的链域存放指针，指向非空子女结点。