智慧团建网站链接,笔记本做系统哪个网站好,卖网站模板,论文答辩免费ppt模板下载文章大纲 引言一、哈希表1、哈希表概述2、哈希表的基本设计思想3、JDK中的哈希表的设计思想概述 二、树1、树的概述2、树的特点3、树的相关术语4、树的存储结构4.1、双亲表示法4.2、孩子兄弟表示法#xff1a;4.3、孩子表示法#xff1a;4.4、双亲孩子表示法 三、二叉树1、二… 文章大纲 引言一、哈希表1、哈希表概述2、哈希表的基本设计思想3、JDK中的哈希表的设计思想概述 二、树1、树的概述2、树的特点3、树的相关术语4、树的存储结构4.1、双亲表示法4.2、孩子兄弟表示法4.3、孩子表示法4.4、双亲孩子表示法 三、二叉树1、二叉树的性质3、二叉树的类型4、二叉树的存储结构5、二叉树的遍历5.1、先序遍历根结点 --- 左子树 --- 右子树5.2、中序遍历左子树 --- 根结点 --- 右子树5.3、后序遍历左子树 --- 右子树 --- 根结点 6、二叉树的链式实现 引言
前面介绍了线性表结构中的顺序存储结构寻址容易但是插入删除性能不好而链式结构插入删除性能较好寻址却欠佳那么有没有“鱼和熊掌兼可得”的结构呢
一、哈希表
1、哈希表概述
哈希表Hash table也叫散列表是根据关键码值(Key value)而直接进行访问的数据结构。即它通过把关键码值映射到表中一个位置来访问记录直接通过key来加快查找的速度这个映射函数叫做散列函数散列函数就是用于计算哈希值的存放记录的数组叫做散列表。
2、哈希表的基本设计思想
以一个实例简单分析下哈希表的设计思想首先我们有一组数据{14,19,5,7,21,1,13,0,18}需要存储暂且设计散列表长度为预存储数组的长度最后再设计一个映射公式即散列函数表达式f(x) x mod 13经过映射之后无论多大的数据都能确保经过散列函数计算之后在散列表下标范围内当然我们用的hashCode要比这复杂得多不过核心思想是一样的 当然以上是一种简单的哈希表基本设计思想适用于特定的场景比如说通讯录、QQ好友列表、微信好友列表、字典等有上限的且重复不多的数据存储。
3、JDK中的哈希表的设计思想概述
JDK中采用的是所谓的拉链法JDK1.7之前采用的是数组单链表的结构而在之后改成了数组单链表红黑树的结构基本思想是一致的区别在于解决哈希冲突的方案JDK1.7之前散列表中存储的元素上一个单链表当发生哈希冲突时直接把值添加到链表尾部这样就解决了哈希冲突但是为了避免单链表长度过长在JDK1.8之后设置来一个阈值当链表长度超过这个阈值时则自动转为红黑树进行存储。
二、树
1、树的概述
树是一种数据结构它是由nn1个有限结点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树不过它是根朝上而叶朝下的当n0时根结点是唯一的不可能存在多个根结点数据结构中的树只能有一个根结点.m0时子树的个数没有限制但它们一定是互不相交的。单个结点是一棵树树根就是该结点本身。
2、树的特点
每个结点有零个或多个子结点没有父结点的结点称为根结点每一个非根结点有且只有一个父结点除了根结点外每个子结点可以分为多个不相交的子树
3、树的相关术语
结点的度——一个结点含有的子树的个数称为该结点的度叶结点或终端结点——度为0的结点称为叶结点非终端结点或分支结点——度不为0的结点双亲结点或父结点——若一个结点含有子结点则这个结点称为其子结点的父结点孩子结点或子结点——一个结点含有的子树的根结点称为该结点的子结点兄弟结点——具有相同父结点的结点互称为兄弟结点树的度——一棵树中最大的结点的度称为树的度结点的层次——从根开始定义起根为第1层根的子结点为第2层以此类推树的高度或深度——树中结点的最大层次堂兄弟结点——双亲在同一层的结点互为堂兄弟结点的祖先——从根到该结点所经分支上的所有结点子孙——以某结点为根的子树中任一结点都称为该结点的子孙。森林——由mm0棵互不相交的树的集合称为森林 4、树的存储结构
树的存储结构有有四种双亲表示法、孩子兄弟表示法、孩子表示法、双亲孩子表示法
4.1、双亲表示法
把所有节点都村存在一组连续空间中同时在每个结点中附设一个指示器指示其双亲结点到链表中的位置。 节点结构为
data(数据域)parent(指针域)存储结点的数据信息存储该结点的双亲所在数组中的下标 根节点的指针域为-1根据结点的parent指针很容易找到它的双亲结点。所用时间复杂度为O(1)直到parent为-1时表示找到了树结点的根。 4.2、孩子兄弟表示法
任意一棵树它的结点的第一个孩子如果存在就是唯一的它的右兄弟如果存在也是唯一的。因此我们设置两个指针分别指向该结点的第一个孩子和此结点的右兄弟结点结构
data(数据域)firstchild指针域rightsib指针域data是数据域存储该结点的第一个孩子结点的存储地址存储该结点的右兄弟结点的存储地址
4.3、孩子表示法
把每个结点的孩子结点排列起来以单链表作存储结构则n个结点有n个孩子链表如果是叶子结点则此单链表为空然后n个头指针又组成一个线性表采用顺序存储结构存放进一个一维数组中。为此设计两种结点结构一种是孩子链表的孩子结点:
child(数据域)next(指针域)存储某个结点在表头数组中的下标存储指向某结点的下一个孩子结点的指针另一种是表头数组的表头结点:data(数据域)firstchild(头指针域)——存储某个结点的数据信息存储该结点的孩子链表的头指针 4.4、双亲孩子表示法 三、二叉树
二叉树是**每个结点最多有两个子树的树结构**通常子树被称作“左子树”left subtree和“右子树”right subtree。二叉树不是树的一种特殊情形尽管其与树有许多相似之处但树和二叉树有两个主要差别树中结点的最大度数没有限制而二叉树结点的最大度数为2 树的结点无左、右之分而二叉树的结点有左、右之分。
1、二叉树的性质
在非空二叉树中第i层的结点总数不超过2的i-1次方 , i1深度为h的二叉树最多有 2的h次方减1个结点(h1)最少有h个结点对于任意一棵二叉树如果其叶结点数为N0而度数为2的结点总数为N2则N0N21具有n个结点的完全二叉树的深度为 [log2 N]1 注[ ]表示向下取整有N个结点的完全二叉树各结点如果用顺序方式存储则结点之间有如下关系若I为结点编号则 如果I1则其父结点的编号为I/2如果2IN则其左孩子即左子树的根结点的编号为2I若2IN则无左孩子如果2I1N则其右孩子的结点编号为2I1若2I1N则无右孩子。给定N个节点能构成h(N)种不同的二叉树。h(N)为卡特兰数的第N项。h(n)C(2*nn)/(n1)。设有i个枝点I为所有枝点的道路长度总和J为叶的道路长度总和JI2i [2]
3、二叉树的类型
完全二叉树——若设二叉树的高度为h除第 h 层外其它各层 (1h-1) 的结点数都达到最大个数第h层有叶子结点并且叶子结点都是从左到右依次排布这就是完全二叉树。满二叉树——除了叶结点外每一个结点都有左右子叶且叶子结点都处在最底层的二叉树。平衡二叉树——平衡二叉树又被称为AVL树区别于AVL算法它是一棵二叉排序树且具有以下性质它是一棵空树或它的左右两个子树的高度差的绝对值不超过1并且左右两个子树都是一棵平衡二叉树。
4、二叉树的存储结构 5、二叉树的遍历
遍历是对树的一种最基本的运算所谓遍历二叉树就是按一定的规则和顺序走遍二叉树的所有结点使每一个结点都被访问一次而且只被访问一次。由于二叉树是非线性结构因此树的遍历实质上是将二叉树的各个结点转换成为一个线性序列来表示。假设L、D、R分别表示遍历左子树、访问根结点和遍历右子树 则对一棵二叉树的遍历有三种情况DLR称为先根次序遍历LDR称为中根次序遍历LRD 称为后根次序遍历。
5.1、先序遍历根结点 — 左子树 — 右子树
首先访问根再先序遍历左子树最后先序遍历右子树。
public void postOrderTraversal(TreeNode root) {if (root ! null) {return;}postOrderTraversa1(root.left);postOrderTraversa1(root.right);System.out.print(root.val );
}非递归版本
public void preOrderTraversval2(TreeNode root) {LinkedListTreeNode stack new LinkedList();TreeNode pNode root;while (pNode ! null || !stack.isEmpty()) {if (pNode ! null) {System.out.print(pNode.val );stack.push(pNode);pNode pNode.left;} else { //pNode null !stack.isEmpty()TreeNode node stack.pop();pNode node.right;}}}5.2、中序遍历左子树 — 根结点 — 右子树
首先中序遍历左子树再访问根最后中序遍历右子树
public void postOrderTraversal(TreeNode root) {if (root ! null) {return;}postOrderTraversa1(root.left);postOrderTraversa1(root.right);System.out.print(root.val );
}5.3、后序遍历左子树 — 右子树 — 根结点
首先后序遍历左子树再后序遍历右子树最后访问根即
public void postOrderTraversal(TreeNode root) {if (root ! null) {return;}postOrderTraversa1(root.left);postOrderTraversa1(root.right);System.out.print(root.val );
}6、二叉树的链式实现
package com.crazymo.ndk.tree;public class BinaryTreeE {public TreeNodeE root;public BinaryTree(E data){rootnew TreeNode(data,null,null);}public void createTree(){TreeNodeString nodeBnew TreeNodeString(B,null,null);TreeNodeString nodeCnew TreeNodeString(C,null,null);TreeNodeString nodeDnew TreeNodeString(D,null,null);TreeNodeString nodeEnew TreeNodeString(E,null,null);TreeNodeString nodeFnew TreeNodeString(F,null,null);TreeNodeString nodeGnew TreeNodeString(G,null,null);TreeNodeString nodeHnew TreeNodeString(H,null,null);TreeNodeString nodeJnew TreeNodeString(J,null,null);TreeNodeString nodeInew TreeNodeString(I,null,null);root.leftChild (TreeNodeE) nodeB;root.rightChild (TreeNodeE) nodeC;nodeB.leftChildnodeD;nodeC.leftChildnodeE;nodeC.rightChildnodeF;nodeD.leftChildnodeG;nodeD.rightChildnodeH;nodeE.rightChildnodeJ;nodeH.leftChildnodeI;}/*** 中序访问树的所有节点*/public void midOrderTraverse(TreeNodeE root){//逻辑if(rootnull){return;}midOrderTraverse(root.leftChild);//逻辑System.out.print(mid:root.data\t);//输出midOrderTraverse(root.rightChild);//逻辑}/*** 前序访问树的所有节点 Arrays.sort();*/public void preOrderTraverse(TreeNodeE root){if(rootnull){return;}System.out.print(pre:root.data\t);preOrderTraverse(root.leftChild);preOrderTraverse(root.rightChild);}/*** 后序访问树的所有节点*/public void postOrderTraverse(TreeNodeE root){if(rootnull){return;}postOrderTraverse(root.leftChild);postOrderTraverse(root.rightChild);System.out.print(post:root.data\t);}/***节点的数据结构* param E*/public class TreeNodeE {E data;TreeNodeE leftChild;TreeNodeE rightChild;public TreeNode(E data, TreeNodeE leftChild, TreeNodeE rightChild) {this.data data;this.leftChild leftChild;this.rightChild rightChild;}}
}
树的遍历 BinaryTree binarayTreenew BinaryTree(A);//构造简单二叉树binarayTree.createTree();binarayTree.midOrderTraverse(binarayTree.root);System.out.println();binarayTree.preOrderTraverse(binarayTree.root);System.out.println();binarayTree.postOrderTraverse(binarayTree.root);
