- 概念
- 基本概念
- 满二叉树
- 完全二叉树
- 树的表示形式
- 孩子兄弟表示法
- 孩子表示法
- 树的性质
- 二叉树的基本操作实现
和链表与顺序表不同,二叉树不是线性的.之所以称之为二叉树,是因为它看起来像倒着的树.
- 节点的度:含有子树的个数
- 树的度:所有节点中最大的度
- 叶子结点/终端节点:度为0的节点
- 双亲节点/父节点:含有子节点的节点
- 孩子节点/子节点:含有子树的根节点的节点
- 根节点:没有双亲节点的节点
- 节点的层次:一般来说,根为第一层,根的孩子节点为第二层,以此类推
- 非终端节点/分支节点:度不为0的节点
- 兄弟节点:含有相同的父亲节点的节点
- 堂兄弟节点:父亲节点在同一层的节点
- 节点的祖先:从根到该节点的所有节点
- 森林:多个不相交的树的集合
每层的节点个数都达到最大值
完全二叉树每个节点都和满二叉树从0到n的编号的节点一一对应的二叉树
也就是说,最后一层从最右面省略若干个节点的二叉树就是完全二叉树
class Node {
int value; // 数据
Node firstChild; // 第一个孩子引用
Node nextBrother; // 下一个兄弟引用
}
孩子表示法
class Node {
int value; // 数据
Node left; // 左子树
Node right; // 右子树
}
树的性质
- 若根节点为第一层,则第i层最多有2^(i-1)个节点
- 若根节点的深度为1,则深度为k的二叉树最多有2^k - 1个节点
- 若叶节点的个数是n0,度为2的个数为n2,则 n0 = n2 + 1
- n个节点的二叉树的深度为log2 (n + 1)取整
- 若根节点的编号是0,则一个节点的双亲结点的编号是(i - 1)/2,左孩子是2i + 1,右孩子为2i + 2
BinaryTree.java
package BinaryTree;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
public class BinaryTree {
static class TreeNode {
public char val;
public TreeNode left;
public TreeNode right;
public TreeNode(char val){
this.val = val;
}
@Override
public String toString() {
return "TreeNode{" +
"val=" + val +
'}';
}
}
public TreeNode root;
public void createTree() {
TreeNode A = new TreeNode('A');
TreeNode B = new TreeNode('B');
TreeNode C = new TreeNode('C');
TreeNode D = new TreeNode('D');
TreeNode E = new TreeNode('E');
TreeNode F = new TreeNode('F');
TreeNode G = new TreeNode('G');
TreeNode H = new TreeNode('H');
A.left = B;
A.right = C;
B.left = D;
B.right = E;
C.left = F;
C.right = G;
E.right = H;
this.root = A;
}
public void preOrder(TreeNode root){
if(root == null){
return;
}
System.out.print(root.val + " ");
preOrder(root.left);
preOrder(root.right);
}
public void inOrder(TreeNode root){
if(root == null) {
return;
}
inOrder(root.left);
System.out.print(root.val + " ");
inOrder(root.right);
}
public void postOrder(TreeNode root){
if(root == null){
return;
}
postOrder(root.left);
postOrder(root.right);
System.out.print(root.val + " ");
}
// 获取树中节点的个数
int size(TreeNode root){
if(root == null){
return 0;
}
return size(root.left) + size(root.right) + 1;
}
// 获取叶子节点的个数
int getLeafNodeCount(TreeNode root){
if(root == null){
return 0;
}
if(root.right == null && root.left == null){
return 1;
}
return getLeafNodeCount(root.left) + getLeafNodeCount(root.right);
}
// 获取第K层节点的个数
int getKLevelNodeCount(TreeNode root,int k){
if(root == null){
return 0;
}
if(k == 1){
return 1;
}
return getKLevelNodeCount(root.left,k - 1) + getKLevelNodeCount(root.right,k - 1);
}
// 获取二叉树的高度
int getHeight(TreeNode root){
if(root == null){
return 0;
}
int left = getHeight(root.left);
int right = getHeight(root.right);
return left > right ? left + 1 : right + 1;
}
// 检测值为value的元素是否存在
TreeNode find(TreeNode root, char val){
if(root == null){
return null;
}
if(root.val == val){
return root;
}
TreeNode left = find(root.left,val);
if(left != null){
return left;
}
TreeNode right = find(root.right,val);
if(right != null){
return right;
}
return null;
}
//层序遍历
void levelOrder(TreeNode root){
Queue q = new LinkedList<>();
q.add(root);
TreeNode cur = root;
while(!q.isEmpty()){
cur = q.poll();
if(cur.left != null){
q.add(cur.left);
}
if(cur.right != null){
q.add(cur.right);
}
System.out.println(cur);
}
}
// 判断一棵树是不是完全二叉树
boolean isCompleteTree(TreeNode root){
Queue q = new LinkedList<>();
q.add(root);
TreeNode cur = root;
while(!q.isEmpty()){
cur = q.poll();
if(cur == null){
break;
}
q.add(cur.left);
q.add(cur.right);
}
while(!q.isEmpty()){
if(q.peek() != null){
return false;
}
q.poll();
}
return true;
}
}
TestDemo.java
package BinaryTree;
import BinaryTree.BinaryTree;
public class TestDemo {
public static void main(String[] args) {
BinaryTree binaryTree = new BinaryTree();
binaryTree.createTree();
binaryTree.preOrder(binaryTree.root);
System.out.println();
System.out.println(binaryTree.size(binaryTree.root));
System.out.println(binaryTree.getLeafNodeCount(binaryTree.root));
System.out.println(binaryTree.getKLevelNodeCount(binaryTree.root, 4));
System.out.println(binaryTree.getHeight(binaryTree.root));
BinaryTree.TreeNode node = binaryTree.find(binaryTree.root,'a');
if(node != null){
System.out.println(node.toString());
} else {
System.out.println("null");
}
binaryTree.levelOrder(binaryTree.root);
System.out.println(binaryTree.isCompleteTree(binaryTree.root));
}
}
