优秀的设计网站,.net网站开发实训报告,如何创建一个企业,团购网站开发的可行性分析专栏#xff1a;数据结构(Java版) 个人主页#xff1a;手握风云 目录
一、树型结构
1.1. 树的定义
1.2. 树的基本概念
1.3. 树的表示形式
二、二叉树
2.1. 概念
2.2. 两种特殊的二叉树
2.3. 二叉树的性质
2.4. 二叉树的存储
三、二叉树的基本操作 一、树型结构
1.… 专栏数据结构(Java版) 个人主页手握风云 目录
一、树型结构
1.1. 树的定义
1.2. 树的基本概念
1.3. 树的表示形式
二、二叉树
2.1. 概念
2.2. 两种特殊的二叉树
2.3. 二叉树的性质
2.4. 二叉树的存储
三、二叉树的基本操作 一、树型结构
1.1. 树的定义 树是⼀种⾮线性的数据结构它是由nn0个有限结点组成⼀个具有层次关系的集合。把它叫做 树是因为它看起来像⼀棵倒挂的树也就是说它是根朝上⽽叶朝下的。它具有以下的特点
有⼀个特殊的结点称为根结点根结点没有前驱结点除根结点外其余结点被分成M(M 0)个互不相交的集合T1、T2、......、Tm其中每⼀个集合Ti (1 i m) ⼜是⼀棵与树类似的⼦树。每棵⼦树的根结点有且只有⼀个前驱可以有0个或多个后继树是递归定义的 注意在树型结构中子树与子树之间不能有交集否则就不是树型结构。
1.2. 树的基本概念 结点的度⼀个结点含有⼦树的个数称为该结点的度 如上图A的度为2
树的度⼀棵树中所有结点度的最⼤值称为树的度如上图树的度为3
叶子结点或终端结点度为0的结点称为叶结点如上图G、H、I、J都是叶结点
父结点若⼀个结点含有⼦结点则这个结点称为其⼦结点的⽗结点如上图A是B的父节点
子结点⼀个结点含有的⼦树的根结点称为该结点的⼦结点 如上图B是A的子结点
根结点⼀棵树中没有父结点的结点如上图A
结点的层次从根开始定义起根为第1层根的⼦结点为第2层以此类推
树的高度或深度树中结点的最大层次如上图树的高度是4
1.3. 树的表示形式 树结构相对线性表就比较复杂了要存储表示起来就⽐较麻烦了实际中树有很多种表示⽅式如双亲表示法孩子表示法、孩子双亲表示法、孩子兄弟表示法等等。我们这⾥就简单的了解其中最常用的孩子兄弟表示法。
class Node{int val;//树中储存的数据Node firstChild;//第一个孩子引用Node nextBrother;//下一个兄弟引用
} 二、二叉树
2.1. 概念 一棵二叉树是结点的一个有限集合该集合或者为空或者是由一个根节点加上两棵别称为左子树和右子树的⼆叉树组成。 从上图中可以看出⼆叉树不存在度⼤于2的结点⼆叉树的⼦树有左右之分次序不能颠倒因此⼆叉树是有序树。 注意对于任意的⼆叉树都是由以下⼏种情况复合⽽成的。 2.2. 两种特殊的二叉树
满二叉树如果一棵二叉树的层数为K且结点总数是 则它就是满⼆叉树。完全二叉树完全⼆叉树是由满⼆叉树⽽引出来的。对于深度 为K的有n个结点的⼆叉树当且仅当其每⼀个结点都与深度为K的满⼆叉树中编号从0⾄n-1的结点一一对应。满二叉树是一种特殊的完全二叉树。 2.3. 二叉树的性质
若规定根结点的层数为1则⼀棵⾮空⼆叉树的第i层上最多有(i0)个结点若规定只有根结点的⼆叉树的深度为1则深度为K的⼆叉树的最⼤结点数是(k0)对任何⼀棵⼆叉树, 如果其叶结点个数为 n0, 度为2的⾮叶结点个数为 n2,则有n0n21具有n个结点的完全⼆叉树的深度k为上取整
2.4. 二叉树的存储 二叉树的存储方式分为顺序结构和类似于链式的结构。我们这里主要介绍链式存储。⼆叉树的链式存储是通过⼀个⼀个的节点引⽤起来的。
//孩子表示法
class Node{int val;//数据域Node left;//左孩子引用Node right;//右孩子引用
}//孩子双亲表示法
class Node{int val;Node left;Node right;Node parent;//当前节点的根节点
}
三、二叉树的基本操作
我们可以自己创建一个二叉树我们可以参照之前创建链表、栈、队列的方式来手动创建二叉树。
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 class Test {public static void main(String[] args) {BinaryTree binaryTree new BinaryTree();BinaryTree.TreeNode root binaryTree.CreateTree();//因为是静态内部类System.out.println();}
} 我们在打印这一行大一个断点进行调试。先走完A结点再通过递归的方法去遍历左孩子结点B和右孩子结点C以此类推再去遍历B的左孩子结点E和右孩子结点F。 二叉树可以空树也可以是非空树。非空树由根节点的左子树、根节点的右子树组成的。从概念中可以看出⼆叉树定义是递归式的因此后序基本操作中基本都是按照该概念实现的。
