什么是二叉树
二叉树是一种特殊的树，在二叉树中每个节点最多有两个子节点，一般称为左子节点和右子节点，并且二叉树的子树有左右之分，其次序不能任意颠倒。
二叉树的结构特点：
1.每个节点最多有两个子节点，分别称作左子节点和右子节点。
2.每个节点的左子节点的值比它小，右子节点的值比它大。
3.每个节点的左子树每个节点的值都比它小，右子树每个节点的值都比它大。
前面两点我理解，但是第三点是怎么做到的？
接下来介绍下二叉树是如何 “生长” 起来的
image.png
如上图所示，当加入一个新节点时，从根节点开始对它进行比较。如果它比根节点小，则放入根节点的左子树，如果比根节点大，则放入根节点的右子树。然后再进行下一级节点的比较，直到遇到最后一级节点，才将新节点加入为该节点的左或右子节点。
以第四幅图的节点 25 为例，它第一次会与根节点 10 比较，结果就是 25 应该放入 10 的右子树，这就排除了它放入左子树的可能，即 25 不可能放到 4 的下面。然后 25 再和节点 33 比较，结果是它比较小，所以应该放入 33 的左子树。因为 33 没有左子节点，那么 25 就直接作为 33 的左子节点。
通过这种生长方式，我们无论何时都能得到满足前面三个要素的二叉树。
两种特殊的二叉树
满二叉树
在一棵二叉树中，如果所有分支结点都有左子结点和右子结点，并且叶子结点都集中在二叉树的最下层，这样的树叫做满二叉树
完全二叉树
若二叉树中最多只有最下面两层的结点的度数可以小于2，并且最下面一层的叶子结点都是依次排列在该层最左边的位置上，则称为完全二叉树
image.png
创建一个满二叉树
截屏2021-05-28 14.54.06.png
如图Java创建一个满二叉树
1.新建一个TreeNode类
public class TreeNode {
private String value;//节点的权
private TreeNode leftNode;//左子节点
private TreeNode rightNode;//右子节点
public String getValue() {
return value;
}
public void setValue(String value) {
this.value = value;
}
public TreeNode getLeftNode() {
return leftNode;
}
public void setLeftNode(TreeNode leftNode) {
this.leftNode = leftNode;
}
public TreeNode getRightNode() {
return rightNode;
}
public void setRightNode(TreeNode rightNode) {
this.rightNode = rightNode;
}
public TreeNode(String value) {
this.value = value;
}
@Override
public String toString() {
return "Node [value=" + value + "]";
}
}
2.新建一个BinaryTree类 并添加一个insertNode方法
public class BinaryTree {
private TreeNode rootNode;//根节点
public TreeNode getRootNode() {
return rootNode;
}
@Override
public String toString() {
return "BinaryTree [rootNode=" + rootNode + "]";
}
/**
* 功能描述: 插入结点
*
* @param:
* @return:
* @auther: Destiny
* @date: 2021/5/28 下午2:42
*/
public void insertNode(TreeNode treeNode) {
if (rootNode == null) {
rootNode = treeNode;
rootNode.setLeftNode(null);
rootNode.setRightNode(null);
} else {
TreeNode currentNode = rootNode;
TreeNode parentNode;
// 有孩子继续循环，一直循环到最后一个节点 和插入的节点比较 大的放到右节点，小于放到左节点
while (true) {
parentNode = currentNode;
// 往右放
if (Integer.valueOf(treeNode.getValue()) > Integer.valueOf(currentNode.getValue())) {
currentNode = currentNode.getRightNode();
if (currentNode == null) {
parentNode.setRightNode(treeNode);
return;
}
} else {
// 往左放
currentNode = currentNode.getLeftNode();
if (currentNode == null) {
parentNode.setLeftNode(treeNode);
return;
}
}
}
}
}
}
测试代码
public static void testInsertNode() {
BinaryTree tree = new BinaryTree();
TreeNode node1 = new TreeNode("6");
TreeNode node2 = new TreeNode("5");
TreeNode node3 = new TreeNode("10");
TreeNode node4 = new TreeNode("4");
TreeNode node5 = new TreeNode("6");
TreeNode node6 = new TreeNode("7");
TreeNode node7 = new TreeNode("11");
tree.insertNode(node1);
tree.insertNode(node2);
tree.insertNode(node3);
tree.insertNode(node4);
tree.insertNode(node5);
tree.insertNode(node6);
tree.insertNode(node7);
System.out.println("根节点：" + tree.getRootNode());
System.out.println("根节点的左子节点：" + tree.getRootNode().getLeftNode());
System.out.println("根节点的右子节点：" + tree.getRootNode().getRightNode());
System.out.println("根节点的左子节点的左子节点：" + tree.getRootNode().getLeftNode().getLeftNode());
System.out.println("根节点的左子节点的右子节点：" + tree.getRootNode().getLeftNode().getRightNode());
System.out.println("根节点的右子节点的左子节点：" + tree.getRootNode().getRightNode().getLeftNode());
System.out.println("根节点的右子节点的右子节点：" + tree.getRootNode().getRightNode().getRightNode());
}
输出结果
根节点：Node [value=6]
根节点的左子节点：Node [value=5]
根节点的右子节点：Node [value=10]
根节点的左子节点的左子节点：Node [value=4]
根节点的左子节点的右子节点：Node [value=6]
根节点的右子节点的左子节点：Node [value=7]
根节点的右子节点的右子节点：Node [value=11]
先序/中序/后序 遍历
先序遍历
操作： 如果二叉树为空树，什么也不做；否则：
（1）、访问根节点。
（2）、先序遍历左子树。
（3）、先序遍历右子树。
/**
*
* 功能描述: 先序遍历
*
* @param:
* @return:
* @auther: Destiny
* @date: 2021/5/28 下午3:05
*/
public void beforeOrder(TreeNode treeNode) {
if (treeNode != null) {
System.out.print(" " + treeNode.getValue() + " ");
beforeOrder(treeNode.getLeftNode());
beforeOrder(treeNode.getRightNode());
}
}
结果
先序遍历
6 5 4 6 10 7 11
中序遍历
操作： 如果二叉树为空树，什么也不做；否则：
（1）、中序遍历左子树。
（2）、访问根节点。
（3）、中序遍历右子树。
/**
*
* 功能描述: 中序遍历
*
* @param:
* @return:
* @auther: Destiny
* @date: 2021/5/28 下午3:06
*/
public void inOrder(TreeNode treeNode) {
if (treeNode != null) {
inOrder(treeNode.getLeftNode());
System.out.print(" " + treeNode.getValue() + " ");
inOrder(treeNode.getRightNode());
}
}
结果
中序遍历
4 5 6 6 7 10 11
后序遍历
操作： 如果二叉树为空树，什么也不做；否则：
（1）、后序遍历左子树。
（2）、后序遍历右子树。
（3）、访问根节点。
/**
*
* 功能描述: 后序遍历
*
* @param:
* @return:
* @auther: Destiny
* @date: 2021/5/28 下午3:09
*/
public void afterOrder(TreeNode treeNode) {
if (treeNode != null) {
afterOrder(treeNode.getLeftNode());
afterOrder(treeNode.getRightNode());
System.out.print(" " + treeNode.getValue() + " ");
}
}
结果
后序遍历
4 6 5 7 11 10 6
测试类
public static void testOrder() {
BinaryTree tree = new BinaryTree();
TreeNode node1 = new TreeNode("6");
TreeNode node2 = new TreeNode("5");
TreeNode node3 = new TreeNode("10");
TreeNode node4 = new TreeNode("4");
TreeNode node5 = new TreeNode("6");
TreeNode node6 = new TreeNode("7");
TreeNode node7 = new TreeNode("11");
tree.insertNode(node1);
tree.insertNode(node2);
tree.insertNode(node3);
tree.insertNode(node4);
tree.insertNode(node5);
tree.insertNode(node6);
tree.insertNode(node7);
System.out.println("先序遍历");
tree.beforeOrder(tree.getRootNode());
System.out.println();
System.out.println("中序遍历");
tree.inOrder(tree.getRootNode());
System.out.println();
System.out.println("后序遍历");
tree.afterOrder(tree.getRootNode());
}
输出
先序遍历
6 5 4 6 10 7 11
中序遍历
4 5 6 6 7 10 11
后序遍历
4 6 5 7 11 10 6
二叉树深度
/**
*
* 功能描述: 二叉树深度
*
* @param:
* @return:
* @auther: Destiny
* @date: 2021/5/28 下午3:40
*/
public int maxBinaryTreeDepth(TreeNode root){
if(root == null) return 0;
int left = maxBinaryTreeDepth(root.getLeftNode());
int right = maxBinaryTreeDepth(root.getRightNode());
return (left>right)?(left+1):(right+1);
}
二叉树中节点的个数
/**
*
* 功能描述: 二叉树中节点的个数
*
* @param:
* @return:
* @auther: Destiny
* @date: 2021/5/28 下午3:45
*/
public int sumNode(TreeNode root){
if(root == null) return 0;
int left = sumNode(root.getLeftNode());
int right = sumNode(root.getRightNode());
return 1+left+right;
}
