目录
1.前言
二叉树是数据结构中比较难的数据结构之一,树在计算机中的应用也是非常广泛,例如文件系统、数据库查询、图形处理等。树结构的优点是:可以用来表示关系,可以用来存储和查询大量数据,可以用来实现文件管理和数据库管理等功能。接下来,让我们一起去认识并学习树和二叉树!
2.树
2.1树的概念
有一个特殊的结点,称为 根结点,根结点没有前驱结点 ;除根结点外,其余结点被分成 M(M > 0) 个互不相交的集合 T1 、 T2 、 ...... 、 Tm ,其中每一个集合 Ti (1 <= i <= m) 又是一棵与树类似的子树。每 棵子树的根结点有且只有一个前驱 ,可以有 0 个或多个后继;树是 递归 定义的。
注意:树形结构中,子树之间不能有交集,否则就不是树形结构 。
2.2树中的重要概念
- 结点的度:一个结点含有子树的个数称为该结点的度; 如上图:A的度为6。
- 树的度:一棵树中,所有结点度的最大值称为树的度; 如上图:树的度为6。
- 叶子结点或终端结点:度为0的结点称为叶结点; 如上图:B、C、H、I...等节点为叶结点。
- 双亲结点或父结点:若一个结点含有子结点,则这个结点称为其子结点的父结点; 如上图:A是B的父结点。
- 孩子结点或子结点:一个结点含有的子树的根结点称为该结点的子结点; 如上图:B是A的孩子结点。
- 根结点:一棵树中,没有双亲结点的结点;如上图:A。
- 结点的层次:从根开始定义起,根为第1层,根的子结点为第2层,以此类推。
- 树的高度或深度:树中结点的最大层次; 如上图:树的高度为4。
2.3树的表示形式
class Node {
int value; // 树中存储的数据
Node firstChild; // 第一个孩子引用
Node nextBrother; // 下一个兄弟引用
}
2.4树的应用
树的应用非常广泛,比如文件系统管理(目录和文件)。
3.二叉树
3.1概念
一棵二叉树是结点的一个有限集合,该集合:1. 或者为空2. 或者是由 一个根节 点加上两棵别称为 左子树 和 右子树 的二叉树组成。
从上图可以看出:
1. 二叉树不存在度大于2的结点
2.二叉树的子树有左右之分,次序不能颠倒,因此二叉树是有序树
![](https://i-blog.csdnimg.cn/direct/23d57d72f8cb416fb7954e38e8f3c8c3.png)
3.2两种特殊的二叉树
1. 满二叉树:一棵二叉树,如果每层的结点数都达到最大值,则这棵二叉树就是满二叉树。也就是说,如果一棵二叉树的层数为K,且结点总数是2^k -1,则它就是满二叉树。
2. 完全二叉树 : 完全二叉树是效率很高的数据结构,完全二叉树是由满二叉树而引出来的。对于深度为 K 的,有 n个结点的二叉树,当且仅当其每一个结点都与深度为K 的满二叉树中编号从 0 至 n-1的结点一一对应时称之为完全二叉树。要注意的是 满二叉树是一种特殊的完全二叉树 。
3.3二叉树的性质
1. 若规定根结点的层数为1,则一棵非空二叉树的第i层上最多有2^(i-1) 个节点(i > 0)。2.若规定只有根节点的二叉树的深度为1,则深度为K的二叉树的最大节点数是2^k - 1(k >= 0)
3.对任何一棵二叉树,如果其叶节点个数为n0,度为2的非叶节点个数为n2,则有n0 = n2 +1
4.具有n个节点的完全二叉树的深度k为log₂(n + 1)向上取整
5.对于具有n个节点的完全二叉树,如果按照从上至下从左至右的顺序对所有节点从0开始编号,则对于序号为i的节点有:
- 若i>0,双亲序号:(i-1)/2;i=0,i为根结点编号,无双亲结点
- 若2i+1<n,左孩子序号:2i+1,否则无左孩子
- 若2i+2<n,右孩子序号:2i+2,否则无右孩子
下面给大家来几道例题牛刀小试一下。
1. 某二叉树共有 399 个结点,其中有 199 个度为 2 的结点,则该二叉树中的叶子结点数为( )
A 不存在这样的二叉树
B 200
C 198
D 1992.在具有 2n 个结点的完全二叉树中,叶子结点个数为( )
A n
B n+1
C n-1
D n/23.一个具有767个节点的完全二叉树,其叶子节点个数为()
A 383
B 384
C 385
D 3864.一棵完全二叉树的节点数为531个,那么这棵树的高度为( )
A 11
B 10
C 8
D 12答案:
1.B (199+1)
2.A 2n = n0 + n1 + n2,n0 = n2 + 1,n1 = 1,因此 n0 = n
3.B n0 + 0 + n0 - 1 = 767 可得n0 = 384
4.B log₂(531 + 1) 解出h = 10
3.4二叉树的存储
//孩子表示法
class Node {
int val; //数据域
Node left; //左孩子的引用,常常代表左孩子为根的整棵左子树
Node right; //右孩子的引用,常常代表右孩子为根的整棵右子树
}
//孩子双亲表示法
class Node {
int val; //数据域
Node left; //左孩子的引用,常常代表左孩子为根的整棵左子树
Node right; //右孩子的引用,常常代表右孩子为根的整棵右子树
Node parent; //当前节点的根节点
}
本文后面主要采用孩子表示法创建二叉树。
3.5二叉树的遍历方式
3.5.1创建二叉树
public class BinaryTree {
public class TreeNode {
TreeNode left;
TreeNode right;
int val;
public TreeNode(int val) {
this.val = val;
}
}
public TreeNode createTree() {
TreeNode node1 = new TreeNode(1);
TreeNode node2 = new TreeNode(2);
TreeNode node3 = new TreeNode(3);
TreeNode node4 = new TreeNode(4);
TreeNode node5 = new TreeNode(5);
TreeNode node6 = new TreeNode(6);
node1.left = node2;
node1.right = node3;
node2.left = node4;
node2.right = node5;
node3.left = node6;
return node1;
}
}
3.5.2二叉树的遍历
![](https://i-blog.csdnimg.cn/direct/361538617d8549e0935ff9f1f354c4a4.png)
前序遍历 : 访问根结点—— > 根的左子树—— > 根的右子树。中序遍历:根的左子树——>根节点—— >根的右子树。后序遍历:根的左子树——>根的右子树—— >根节点。
- 前序遍历
代码实现如下:
//前序遍历
public void preOrder(TreeNode root) {
//如果是空树则不需要遍历
if (root == null) {
return;
}
System.out.print(root.val + " ");//访问根节点
preOrder(root.leftNode);//前序遍历左子树
preOrder(root.rightNode);//前序遍历右子树
}
- 中序遍历
代码实现如下:
//中序遍历
public void inOrder(TreeNode root) {
//如果是空树则不需要遍历
if (root == null) {
return;
}
inOrder(root.leftNode);//中序遍历左子树
System.out.print(root.val + " ");//访问根节点
inOrder(root.rightNode);//中序遍历右子树
}
- 后序遍历
代码实现如下:
//后序遍历
public void postOrder(TreeNode root) {
//如果是空树则不需要遍历
if (root == null) {
return;
}
postOrder(root.leftNode);//后序遍历左子树
postOrder(root.rightNode);//后序遍历右子树
System.out.print(root.val + " ");//访问根节点
}
下面简单举个例子:
public class Test {
public static void main(String[] args) {
BinaryTree binaryTree = new BinaryTree();
BinaryTree.TreeNode root =binaryTree.createTree();
System.out.println("前序遍历:");//前序遍历结果:1 2 4 5 3 6
binaryTree.preOrder(root);
System.out.println();
System.out.println("中序遍历:");//中序遍历结果:4 2 5 1 6 3
binaryTree.inOrder(root);
System.out.println();
System.out.println("后序遍历:");//后序遍历结果:4 5 2 6 3 1
binaryTree.postOrder(root);
}
}
运行结果如下:
上面所创建出来的二叉树画出来就是下面这样子。
2.层序遍历
![](https://i-blog.csdnimg.cn/direct/c2030b25205042ae8048fd8a779bfe31.png)
public void levelOrder(TreeNode root) {
Queue<TreeNode> queue = new LinkedList<>();
if (root == null) {
return;
}
queue.offer(root);
while (!queue.isEmpty()) {
TreeNode cur = queue.poll();
System.out.print(cur.val + " ");
if (cur.left != null) {
queue.offer(cur.left);
}
if (cur.right != null) {
queue.offer(cur.right);
}
}
System.out.println();
}
我们通过队列实现层序遍历的功能,只要队列不为空,就把获取到的队头元素给cur,并且同时将这个元素打印出来,在把cur的左右两边代进去,如果左右两边为空的则不能代进去,只有非空才能代入里面。
1. 某完全二叉树按层次输出(同一层从左到右)的序列为 ABCDEFGH 。该完全二叉树的前序序列为 ()A: ABDHECFG B: ABCDEFGH C: HDBEAFCG D: HDEBFGCA2. 二叉树的先序遍历和中序遍历如下:先序遍历: EFHIGJK; 中序遍历: HFIEJKG. 则二叉树根结点为 ()A: E B: F C: G D: H3. 设一课二叉树的中序遍历序列: badce ,后序遍历序列: bdeca ,则二叉树前序遍历序列为 ()A: adbce B: decab C: debac D: abcde4. 某二叉树的后序遍历序列与中序遍历序列相同,均为 ABCDEF ,则按层次输出 ( 同一层从左到右 ) 的序列为 ()A: FEDCBA B: CBAFED C: DEFCBA D: ABCDEF答案:1.A 2.A 3.D 4.A
3.6二叉树的基本操作
1.获取树中节点的个数
//获取树的节点个数
//方法1:递归
public int size(TreeNode root) {
if (root == null) {
return 0;
}
int ret = size(root.left) + size(root.right) + 1;
return ret;
}
//方法2:遍历
public static int nodeSize;
public void size1(TreeNode root) {
if (root == null) {
return;
}
nodeSize++;
size1(root.left);
size1(root.right);
}
public class Test {
//二叉树的基本操作
public static void main(String[] args) {
BinaryTree binaryTree = new BinaryTree();
BinaryTree.TreeNode root = binaryTree.createNode();
binaryTree.preOrder(root);
System.out.println();
binaryTree.inOrder(root);
System.out.println();
binaryTree.postOrder(root);
System.out.println();
System.out.print("树的节点个数:");
System.out.println(binaryTree.size(root));
}
}
运行结果如下:
2.获取叶子节点的个数
//获取叶子节点的个数
//方法1
public int getLeafNodeCount(TreeNode root) {
if (root == null) {
return 0;
}
if (root.left == null && root.right == null) {
return 1;
}
return getLeafNodeCount(root.left) + getLeafNodeCount(root.right);
}
//方法2:遍历
public int leafSize;
public void getLeafNodeCount1(TreeNode root) {
if (root == null) {
return;
}
if (root.left == null && root.right == null) {
leafSize++;
}
getLeafNodeCount1(root.left);
getLeafNodeCount1(root.right);
}
3. 获取第K层节点的个数
//第K层有多少个结点
public int getKLeaveNodeCount(TreeNode root, int k) {
if (root == null) {
return 0;
}
if (k == 1) {
return 1;
}
return getKLeaveNodeCount(root.left, k - 1)
+ getKLeaveNodeCount(root.right, k - 1);
}
4.获取二叉树的高度
//求二叉树的高度
//时间复杂度:O(N)
public int getHeight(TreeNode root) {
if (root == null) {
return 0;
}
int leafHeight = getHeight(root.left);
int rightHeight = getHeight(root.right);
return leafHeight > rightHeight ?
leafHeight + 1 : rightHeight + 1;
}
5.检测值为value的元素是否存在
// 检测值为value的元素是否存在
public TreeNode find(TreeNode root, int val) {
if (root == null) {
return null;
}
if (root.val == val) {
return root;
}
TreeNode ret = find(root.left, val);
if (ret != null) {
return ret;
}
ret = find(root.right, val);
if (ret != null) {
return ret;
}
return null;
}
6.判断一棵树是不是完全二叉树
//判断一棵树是不是完全二叉树
public boolean isCompleteTree(TreeNode root) {
Queue<TreeNode> queue = new LinkedList<>();
if (root == null) {
return true;
}
queue.offer(root);
while (!queue.isEmpty()) {
TreeNode cur = queue.poll();
if (cur == null) {
break;
}
queue.offer(cur.left);
queue.offer(cur.right);
}
while (!queue.isEmpty()) {
TreeNode node = queue.peek();
if (node != null) {
return false;
} else {
queue.poll();
}
}
return true;
}
4.总结
本文的重点是树中的重要概念和二叉树的性质、遍历方式以及基本操作,小伙伴们在学习有关二叉树的内容,一定要画出二叉树,能够帮助我们更好地理解,再去编写代码。