重学数据结构（六、树和二叉树） (2)

若一棵二叉树至多只有最下面的两层结点的度数可以小于 2, 并且最下一层上的结点都集中在该层最左边的若干位置上， 则此二叉树称为完全二叉树。如图4所示：

图4：完全二叉树

由定义及示例可以看出满二叉树是完全二叉树， 但完全二叉树不一定是满二叉树。

性质4 具有 个结点的完全二叉树(包括满二叉树）的高度为 [log~2~n]+1(或者[log~2~(n+1)])。

性质5 满二叉树原理非空满二叉树的叶结点数等于其分支结点数加1。

性质6 —棵非空二叉树空子树的数目等于其结点数目加 1。

2、二叉树实现
2.1、二叉树存储结构

顺序存储

和线性表类似，二叉树的存储结构也可采用顺序存储和链式存储两种方式。

顺序存储是将二叉树所有元素编号，存入到一维数组的对应位置。顺序存储比较适合完全二叉树，只要从根起按层序存储即可，依次自上而下、自左至右存储结点元素， 即将完全二叉树上编号为i 的结点元素存储在如 上定义的一维数组中下标为i-1的数组元素中。

对于非完全二叉树，存在空间的浪费。

图5：二叉树顺序存储示意图

链式存储

由于采用顺序存储结构存储一般二叉树造成大量存储空间的浪费， 因此， 一般二叉树的存储结构更多地采用链接的方式。

在链式存储结构里，我们需要对节点进行定义，每个节点包含数据、左孩子、右孩子。

图6：二叉树链式存储节点示意图

左孩子指向节点的左孩子，右节点指向节点的右孩子。

图7：二叉树的二叉链表表示

下面来看一看链式存储结构的具体实现。

2.2、二叉树链式存储及常见操作实现 2.2.1、节点类

这里添加了一个父节点的属性，方便后面的一些操作

/** * @Author 三分恶 * @Date 2020/10/8 * @Description 二叉树节点 */ public class BinaryTreeNode { private Object data; //数据 private BinaryTreeNode leftChild; //左孩子 private BinaryTreeNode rightChild; //右孩子 private BinaryTreeNode parent; //父节点 //省略getter、setter /** * 重写equals方法，这里设置为数据相等即认为是同一节点（这个规则不合理，待改进） * @param obj * @return */ @Override public boolean equals(Object obj) { //比较对象为BinaryTreeNode类实例 if (obj instanceof BinaryTreeNode){ BinaryTreeNode compareNode= (BinaryTreeNode) obj; //设置为数据相同即相同 if (compareNode.getData().equals(this.getData())){ return true; } } return false; } }
2.2.2、创建 /** * @Author 三分恶 * @Date 2020/10/8 * @Description 二叉树-链式 */ public class BinaryTree { private BinaryTreeNode root; //根节点 public BinaryTree() { } public BinaryTree(BinaryTreeNode root) { this.root = root; } public BinaryTreeNode getRoot() { return root; } public void setRoot(BinaryTreeNode root) { this.root = root; } }
2.2.2、清空 /** * 二叉树的清空 * 递归清空某个节点的子树 * @param node */ public void clear(BinaryTreeNode node){ if (node!=null){ //递归清空左子树 clear(node.getLeftChild()); //递归清空右子树 clear(node.getRightChild()); //将该节点置为null node=null; } } /** * 清空二叉树 */ public void clear(){ clear(root); }
2.2.3、判空

判断根节点是否存在。

/** * 判断二叉树是否为空 * @return */ public boolean isEmpty(){ return root==null; }
2.2.4、获取二叉树的高度

首先需要一种获取以某个节点为子树的高度方法，使用递归实现。如果一个节点为空，那么这个节点肯定是一颗空树，高度为0；如果不为空，则遍历地比较它的左右子树高度，高的一个为这颗子树的最大高度，然后加上自身的高度即可。

/** * 获取指定节点的子树的高度 * @param node * @return */ public int height(BinaryTreeNode node){ if (node==null){ return 0; } //递归获取左子树高度 int l=height(node.getLeftChild()); //递归获取右子树高度 int r=height(node.getRightChild()); //子树高度+1，因为还有节点这一层 return l>=r? (l=1):(r=1); } /** * 获取二叉树的高度 * @return */ public int height(){ return height(root); }
2.2.5、获取节点个数

获取二叉树节点数，需要获取以某个节点为根的子树的节点数实现。