长沙建站,下载企业微信最新版,容易收录的网站,wordpress漫画站java数据结构-二叉树#xff08;上#xff09; 二叉树的概念二叉树的节点介绍 二叉树构造如何使用兄弟表示法构造二叉树两种特别的二叉树二叉树的基本性质#xff1a; 二叉树的存储二叉树的遍历#xff1a;前序遍历#xff1a;中序遍历#xff1a;后序遍历#xff1a;层… java数据结构-二叉树上 二叉树的概念二叉树的节点介绍 二叉树构造如何使用兄弟表示法构造二叉树两种特别的二叉树二叉树的基本性质 二叉树的存储二叉树的遍历前序遍历中序遍历后序遍历层序遍历 二叉树的基础操作 个人主页
努力学编程’ 内容管理
java数据结构 hello今天带大家学习数据结构中非常重要的一个知识点二叉树二叉树主体的实现使用的是递归的知识通过二叉树我们可以更好的理解递归的应用。今天就带大家学习一下二叉树的一些知识。 二叉树的概念 概念 树是一种非线性的数据结构它是由nn0个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树也就是说它是根朝上而叶朝下的。它具有以下的特点。 有一个特殊的结点称为根结点根结点没有前驱结点 除根结点外其余结点被分成M(M 0)个互不相交的集合T1、T2、…、Tm其中每一个集合Ti (1 i m) 又是一棵与树类似的子树。每棵子树的根结点有且只有一个前驱可以有0个或多个后继 树是递归定义的。 二叉树的节点介绍 结点的度一个结点含有子树的个数称为该结点的度 如上图A的度为6 树的度一棵树中所有结点度的最大值称为树的度 如上图树的度为6 叶子结点或终端结点度为0的结点称为叶结点 如上图B、C、H、I…等节点为叶结点 双亲结点或父结点若一个结点含有子结点则这个结点称为其子结点的父结点 如上图A是B的父结点 孩子结点或子结点一个结点含有的子树的根结点称为该结点的子结点 如上图B是A的孩子结点 根结点一棵树中没有双亲结点的结点如上图A 结点的层次从根开始定义起根为第1层根的子结点为第2层以此类推 树的高度或深度树中结点的最大层次 如上图树的高度为4 树的以下概念只需了解在看书时只要知道是什么意思即可 非终端结点或分支结点度不为0的结点 如上图D、E、F、G…等节点为分支结点 兄弟结点具有相同父结点的结点互称为兄弟结点 如上图B、C是兄弟结点 堂兄弟结点双亲在同一层的结点互为堂兄弟如上图H、I互为兄弟结点 结点的祖先从根到该结点所经分支上的所有结点如上图A是所有结点的祖先 子孙以某结点为根的子树中任一结点都称为该结点的子孙。如上图所有结点都是A的子孙 森林由mm0棵互不相交的树组成的集合称为森林.
二叉树构造 那么如何构造一个二叉树呢 实际中树有很多种表示方式如双亲表示法孩子表示法、孩子双亲表示法、孩子兄弟表示法 等等。我们这里就简单的了解其中最常用的孩子兄弟表示法 如何使用兄弟表示法构造二叉树 孩子兄弟法Child-Sibling Representation是一种用来表示树的方法其中每个节点都有两个子节点一个指向其第一个孩子节点另一个指向它的下一个兄弟节点。这种表示方法可以用来构造二叉树具体步骤如下 创建一个类和一个头结点结构中包含节点的值以及指向其第一个孩子节点和下一个兄弟节点的指针。为每个节点分配内存并设置节点的值。根据孩子兄弟法的规则构造二叉树 遍历树的每个节点对于每个节点找到它的第一个孩子节点和下一个兄弟节点。将第一个孩子节点作为其左子节点将下一个兄弟节点作为其右子节点。如果没有孩子节点或兄弟节点则相应的指针为空。 重复步骤3直到树的所有节点都处理完毕。
这里使用孩子兄弟法创建一个二叉树:
static class TreeNode {public char val;public TreeNode left;public TreeNode right;public TreeNode(char val) {this.val val;}}//建立一个简单的数public TreeNode creatTree(){TreeNode Anew TreeNode(A);TreeNode Bnew TreeNode(B);TreeNode Cnew TreeNode(C);TreeNode Dnew TreeNode(D);TreeNode Enew TreeNode(E);TreeNode Fnew TreeNode(F);TreeNode Gnew TreeNode(G);TreeNode Hnew TreeNode(H);A.leftB;A.rightC;B.leftD;B.rightE;C.leftF;C.rightG;E.rightH;return A;}好了我们之前在学习链表和顺序表的时候都涉及到它的基础操作遍历这个数据结构那么在二叉树中我们如何遍历这些节点呢
两种特别的二叉树
满二叉树 一棵二叉树如果每层的结点数都达到最大值则这棵二叉树就是满二叉树。也就是说如果一棵二叉树的层数为K且结点总数是2*k-1 则它就是满二叉树。 完全二叉树 完全二叉树是效率很高的数据结构完全二叉树是由满二叉树而引出来的。对于深度为K的有n个结点的二叉树当且仅当其每一个结点都与深度为K的满二叉树中编号从0至n-1的结点一一对应时称之为完 要注意的是满二叉树是一种特殊的完全二叉树。 二叉树的基本性质
若规定根结点的层数为1则一棵非空二叉树的第i层上最多有 (i0)个结点若规定只有根结点的二叉树的深度为1则深度为K的二叉树的最大结点数是 (k0)对任何一棵二叉树, 如果其叶结点个数为 n0, 度为2的非叶结点个数为 n2,则有n0n21具有n个结点的完全二叉树的深度k为log2(n1) 上取整对于具有n个结点的完全二叉树如果按照从上至下从左至右的顺序对所有节点从0开始编号则对于序号为i 的结点有 若i0双亲序号(i-1)/2i0i为根结点编号无双亲结点 若2i1n左孩子序号2i1否则无左孩子 若2i2n右孩子序号2i2否则无右孩子
二叉树的存储
通常二叉树的存储我们使用链式存储和顺序存储今天带大家使用类似于链表的结构实现二叉树。
// 孩子表示法
class Node {
int val; // 数据域
Node left; // 左孩子的引用常常代表左孩子为根的整棵左子树
Node right; // 右孩子的引用常常代表右孩子为根的整棵右子树
}二叉树的遍历
前序遍历 NLR前序遍历(Preorder Traversal 亦称先序遍历)——访问根结点—根的左子树—根的右子树 public void preOrder(TreeNode root){if(rootnull){return;}System.out.print(root.val );preOrder(root.left);preOrder(root.right);}中序遍历
LNR中序遍历(Inorder Traversal)——根的左子树—根节点—根的右子树。 //2.中序遍历public void inOrder(TreeNode root){if(rootnull){return;}inOrder(root.left);System.out.println(root.val);inOrder(root.right);}后序遍历
LRN后序遍历(Postorder Traversal)——根的左子树—根的右子树—根节点。
public void postOrder(TreeNode root){if(rootnull){return;}postOrder(root.left);postOrder(root.right);System.out.println(root.val);}前序遍历结果1 2 3 4 5 6中序遍历结果3 2 1 5 4 6后序遍历结果3 1 5 6 4 1
层序遍历
层序遍历除了先序遍历、中序遍历、后序遍历外还可以对二叉树进行层序遍历。设二叉树的根节点所在层数为1层序遍历就是从所在二叉树的根节点出发首先访问第一层的树根节点然后从左到右访问第2层 上的节点接着是第三层的节点以此类推自上而下自左至右逐层访问树的结点的过程就是层序遍历。
二叉树的基础操作 我们介绍了二叉树了一些基础知识如何构造如何遍历二叉树接着我们还要学习如何进行二叉树的基础操作。 // 获取树中节点的个数
int size(Node root);
// 获取叶子节点的个数
int getLeafNodeCount(Node root);
// 子问题思路-求叶子结点个数
// 获取第K层节点的个数
int getKLevelNodeCount(Node root,int k);
// 获取二叉树的高度
int getHeight(Node root);
// 检测值为value的元素是否存在
Node find(Node root, int val);
//层序遍历
void levelOrder(Node root);
这里的代码比较简单我们都使用递归实现递归的代码相对来说比较简单的去理解主要需要我们多多画图理解这个递归的整个过程。 我把自己实现的代码给大家有问题的话大家私信我哦~~~
public class TestBinaryTree {//建立一个二叉树的基本信息static class TreeNode {public char val;public TreeNode left;public TreeNode right;public TreeNode(char val) {this.val val;}}//建立一个简单的数public TreeNode creatTree(){TreeNode Anew TreeNode(A);TreeNode Bnew TreeNode(B);TreeNode Cnew TreeNode(C);TreeNode Dnew TreeNode(D);TreeNode Enew TreeNode(E);TreeNode Fnew TreeNode(F);TreeNode Gnew TreeNode(G);TreeNode Hnew TreeNode(H);A.leftB;A.rightC;B.leftD;B.rightE;C.leftF;C.rightG;E.rightH;return A;}//树的一些基本操作//1.前序遍历public void preOrder(TreeNode root){if(rootnull){return;}System.out.print(root.val );preOrder(root.left);preOrder(root.right);}//2.中序遍历public void inOrder(TreeNode root){if(rootnull){return;}inOrder(root.left);System.out.println(root.val);inOrder(root.right);}//3.后续排序public void postOrder(TreeNode root){if(rootnull){return;}postOrder(root.left);postOrder(root.right);System.out.println(root.val);}//获取数的节点个数public int size(TreeNode root){if(rootnull){return -1;}int retsize(root.left)size(root.right)1;return ret;}public static int nodeSize;public void size2(TreeNode root) {if (root null){return ;}nodeSize;size2(root.left);size2(root.right);}//求叶子节点的个数public int getLeafNodeCount(TreeNode root){if(rootnull){return -1;}if(root.rightnullroot.leftnull){return 1;}return getLeafNodeCount(root.right)getLeafNodeCount(root.left);}public int leafSize;public void getLeafNodeCount2(TreeNode root){if(rootnull){return;}if(root.leftnullroot.rightnull){leafSize;}getLeafNodeCount2(root.left);getLeafNodeCount2(root.right);}}
好了今天就带大家学习这么多下次带大家做几道二叉树的算法题让大家对二叉树有一个更深刻的认识。谢谢大家~~~
