꒰˃͈꒵˂͈꒱ write in front ꒰˃͈꒵˂͈꒱
ʕ̯•͡˔•̯᷅ʔ大家好,我是xiaoxie.希望你看完之后,有不足之处请多多谅解,让我们一起共同进步૮₍❀ᴗ͈ . ᴗ͈ აxiaoxieʕ̯•͡˔•̯᷅ʔ—CSDN博客
本文由xiaoxieʕ̯•͡˔•̯᷅ʔ 原创 CSDN 如需转载还请通知˶⍤⃝˶
个人主页:xiaoxieʕ̯•͡˔•̯᷅ʔ—CSDN博客
系列专栏:xiaoxie的JAVA系列专栏——CSDN博客●'ᴗ'σσணღ*
我的目标:"团团等我💪( ◡̀_◡́ ҂)"( ⸝⸝⸝›ᴥ‹⸝⸝⸝ )欢迎各位→点赞👍 + 收藏⭐️ + 留言📝+关注(互三必回)!
一.树
1.概念(简单了解即可)
注意:树形结构中,子树之间不能有交集,否则就不是树形结构
2.树的基本术语
2.1需要重点记忆的
结点的度:一个结点含有子树的个数称为该结点的度; 如上图:A的度为3
2.2简单了解即可
3.树的代码表示形式(简单了解)
树结构相对线性表就比较复杂了,要存储表示起来就比较麻烦了,实际中树有很多种表示方式,如:双亲表示法,
class Node {
int value; // 树中存储的数据
Node firstChild; // 第一个孩子引用
Node nextBrother; // 下一个兄弟引用
}
二.二叉树(重点掌握)
1.概念
一棵二叉树是结点的一个有限集合,该集合:
![数据结构奇妙旅程之二叉树初阶,Java,数据结构,java](https://imgs.yssmx.com/Uploads/2024/01/803239-3.png)
1.1二叉树的基本形态
文章来源:https://www.toymoban.com/news/detail-803239.html
1.2两种特殊的二叉树
2.性质
3.基本操作
public class BinaryTree {
static class TreeNode {
public char val;
public TreeNode left;
public TreeNode right;
public TreeNode(char val) {
this.val = val;
}
}
//以穷举的方式 创建一棵二叉树出来
public TreeNode 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;
return 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 + " ");
}
// 获取二叉树中节点的个数
public int size(TreeNode root) {
if(root == null) {
return 0;
}
return size(root.left)+size(root.right)+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);
}
// 获取第K层节点的个数
public 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);
}
// 获取二叉树的高度
public int getHeight(TreeNode root) {
if(root == null) {
return 0;
}
int leftH = getHeight(root.left);
int rightH = getHeight(root.right);
return Math.max(leftH,rightH)+1;
}
// 检测值为value的元素是否存在
public boolean find(TreeNode root,char val) {
if(root == null) {
return false;
}
if(root.val == val) {
return true;
}
return find(root.left, val) || find(root.right, val);
}
//层序遍历使用队列来辅助
//当涉及到层序遍历时,通常情况下使用队列来实现会更为简单和高效
public void levelOrder(TreeNode root) {
if(root == null) {
return;
}
Queue<TreeNode> q = new LinkedList<>();
q.offer(root);
while (!q.isEmpty()) {
TreeNode cur = q.poll();
System.out.print(cur.val + " ");
if(cur.left != null) {
q.offer(cur.left);
}
if(cur.right != null) {
q.offer(cur.right);
}
}
}
// 判断一棵树是不是完全二叉树
public boolean isCompleteTree(TreeNode root) {
if (root == null) {
return true;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
boolean end = false;
while (!queue.isEmpty()) {
TreeNode current = queue.poll();
if (current == null) {
end = true;
} else {
if (end) {
return false; // 如果已经遇到空节点,再遇到非空节点,说明不是完全二叉树
}
queue.offer(current.left);
queue.offer(current.right);
}
}
return true;
}
}
三.说明
以上就是关于二叉树的一些基础问题了,如果你已经对这些比较基础的问题都大概了解,就可以开始尝试做题,你也可以移步到博主的下一篇关于二叉树面试题的文章,帮助你更好的掌握二叉树,感谢你的观看,愿你一天开心愉快文章来源地址https://www.toymoban.com/news/detail-803239.html
到了这里,关于数据结构奇妙旅程之二叉树初阶的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!