关键词：
1. 二叉树的逻辑结构
a) 定义：二叉树是一种非线性结构，是n个有限元素的集合，由一个根节点与两个不相交的左子树和右子树组成，当集合为空又称为空二叉树，一个元素也成为一个节点。二叉树是有序的。
b) 基本概念
i. 节点的度：节点下子树的个数，范围为0-2
ii. 叶节点：度为0的节点
iii. 分支节点：度不为0的节点
iv. 路径、路径长度：设n(i+1)是n(i)的父节点，则n(1)…n(k)称为一条路径，路径长度为k-1
v. 节点层数：从根节点开始到叶节点，每个节点层数等于其父节点的节点层数+1，根节点的节点层数位1
vi. 数的深度：叶节点的最大节点层数
vii. 数的度：各节点度的最大值，数的度最大位2
viii. 满二叉树：所有分支节点都有左子树和右子树且叶节点都在同一层的二叉树
ix. 完全二叉树：一棵深度为k有n个节点的二叉树，对树中的节点按照从上到下，从左到右的顺序进行编号，树中编号为i的节点与满二叉树编号为i的节点位置相同则称为完全二叉树。特点是：叶子节点只能出现在最下层和次下层，且最下层的叶子节点集中在左边。（可以理解为在一棵深度为k满二叉树的第k层（共有2^(k-1)个节点）的最右边第一个节点开始向左去掉0或(2^(k-1))或0-2^(k-1)之间的奇数个节点）
c) 主要性质
i. 非空二叉树的第k层最多有2^(k-1)个节点
ii. 一棵深度为k的二叉树最有有2^k-1个节点
iii. 对于一棵非空二叉树：叶子节点数=度为2的节点数+1
iv. 具有n个节点的满二叉树的深度为log(n+1)，具有n个节点的完全二叉树的深度为log(n)+1
v. 对于具有n个节点的完全二叉树，按照从上到下从左到右的顺序进行排序，对于序号为i的节点
[1] 若i>1，则双亲的序号为i/2的整数部分，i=1，则该节点是树的根节点；
[2] 若2i<n，则i的左孩子为2i，若2i>n，则该节点无左孩子
[3] 若2i+1<n，则i的右孩子为2i+1，若2i+1>n，则该节点无右孩子
d) 二叉树的抽象数据类型
i. 数据元素：具有相同类型的数据集合
ii. 数据结构：除根节点外，每个节点都有一个直接前驱，除叶节点外，每个节点都有1-2个直接后驱
iii. 数据操作：一般二叉树的操作定义在IBiTree接口中
publicinterface IBiTree<E> {
//返回根节点
TreeNode<E> getRoot();
//返回fnode的左子树
TreeNode<E> getLeftChild(TreeNode<E> fnode);
//返回fnode的右子树
TreeNode<E> getRightChild(TreeNode<E> fnode);
//向fnode左子树添加节点
void insertLeftChild(TreeNode<E> lcnode,TreeNode<E> fnode);
//向fnode的右子树添加节点
void insertRightChild(TreeNode<E> rcnode,TreeNode<E> fnode);
//删除fnode的左子树
TreeNode<E> deleteLeftChild(TreeNode<E> fnode);
//删除fnode的右子树
TreeNode<E> deleteRightChild(TreeNode<E> fnode);
//查找指定节点
TreeNode<E> find(TreeNode<E> target);
//以第前序方式遍历二叉树
void pretraverse(TreeNode<E> root);
//以中序方式遍历二叉树
void intraverse(TreeNode<E> root);
//以后序遍历二叉树
void posttraverse(TreeNode<E> root);
//以层序方式遍历二叉树
void leveltraverse();
}
2. 二叉树的实现之顺序存储
a) 顺序存储结构：用一组连续的数组来存储二叉树数据，通常按照从左到右、从上到下的顺序进行存储，对于一般的二叉树存储在数组中，下标不能很好的反映二叉树中的节点逻辑关系，需要在数组中添加空节点，这样比较浪费存储空间。因此，一般用数组存储满二叉树或者完全二叉树比较合适。
3. 二叉树的实现之链式存储
a) 链式存储结构
i. 二叉链式存储结构：每个节点包括存储数据的元素，指向左子树的left和指向右子树的right，当左子树或右子树不存在时，将left或者right设置为null
ii. 三叉链式存储结构：相比二叉链式存储结构增加了指向父节点的parent，最常用的时二叉链式存储结构
b) 代码实现
//定义树节点，包括数据，权值，左子树，右子树
publicclass TreeNode<E> {
private E e;
privateintweight;
private TreeNode<E> left;
private TreeNode<E> right;
//不带权值的构造方法
public TreeNode(E e) {
super();
this.e = e;
this.weight=0;
this.left = null;
this.right = null;
}
//带权值的构造方法
public TreeNode(E e, intweight) {
super();
this.e = e;
this.weight = weight;
}
public E getE() {
returne;
}
publicvoid setE(E e) {
this.e = e;
}
public TreeNode<E> getLeft() {
returnleft;
}
publicvoid setLeft(TreeNode<E> left) {
this.left = left;
}
public TreeNode<E> getRight() {
returnright;
}
publicvoid setRight(TreeNode<E> right) {
this.right = right;
}
}
//创建普通二叉树类
publicclass MyLinkTree<E> implements IBiTree<E> {
private TreeNode<E> root;
//初始化二叉树
public MyLinkTree(TreeNode<E> root) {
super();
this.root = root;
}
//返回树的根节点
@Override
public TreeNode<E> getRoot() {
returnthis.root;
}
//返回指定节点的左孩子
@Override
public TreeNode<E> getLeftChild(TreeNode<E> fnode) {
TreeNode<E> temp=find(fnode);
returntemp.getLeft();
}
//返回指定节点的右孩子
@Override
public TreeNode<E> getRightChild(TreeNode<E> fnode) {
TreeNode<E> temp=find(fnode);
returntemp.getRight();
}
//在指定节点插入左孩子，如过其左孩子已经存在，将原近年来的左孩子作为新建左孩子的左子树
@Override
publicvoid insertLeftChild(TreeNode<E> lcnode, TreeNode<E> fnode) {
TreeNode<E> temp=find(fnode);
if(temp.getLeft()!=null) {
TreeNode<E> left=temp.getLeft();
temp.setLeft(lcnode);
lcnode.setLeft(left);
}
else
temp.setLeft(lcnode);
}
//在指定节点插入右孩子，如果其右孩子存在，将其原来的右孩子作为新建右孩子的右子树
@Override
publicvoid insertRightChild(TreeNode<E> rcnode, TreeNode<E> fnode) {
TreeNode<E> temp=find(fnode); //找到指定节点
if(temp.getRight()!=null) {
TreeNode<E> right=temp.getRight();
temp.setRight(rcnode);
rcnode.setRight(right);
}
else
temp.setRight(rcnode);
}
//删除指定节点的左子树（将其左子树下的所有节点删除）
@Override
public TreeNode<E> deleteLeftChild(TreeNode<E> fnode) {
TreeNode<E> temp=find(fnode);
TreeNode<E> lcnode=temp.getLeft();
temp.setLeft(null);
returnlcnode;
}
//删除指定节点的右子树（将其右子树下的所有节点删除）
@Override
public TreeNode<E> deleteRightChild(TreeNode<E> fnode) {
TreeNode<E> temp=find(fnode);
TreeNode<E> rcnode=temp.getRight();
temp.setRight(null);
returnrcnode;
}
//利用层序遍历找到指定节点
public TreeNode<E> find(TreeNode<E> target){
TreeNode<E> temp=this.root;
IQueue<TreeNode> queue=new MylinkQueue<>();
queue.enqueue(temp);
while(!queue.isEmpty()) {
temp=queue.dequeue();
if(temp==target)
returntemp;
if(temp.getLeft()!=null)
queue.enqueue(temp.getLeft());
if(temp.getRight()!=null)
queue.enqueue(temp.getRight());
}
returnnull;
}
//前序遍历
@Override
publicvoid pretraverse(TreeNode<E> root) {
if(root!=null) {
System.out.println(root.getE());
pretraverse(root.getLeft());
pretraverse(root.getRight());
}
}
//中序遍历
@Override
publicvoid intraverse(TreeNode<E> root) {
if(root!=null) {
intraverse(root.getLeft());
System.out.println(root.getE());
intraverse(root.getRight());
}
}
//后续遍历
@Override
publicvoid posttraverse(TreeNode<E> root) {
if(root!=null) {
posttraverse(root.getLeft());
posttraverse(root.getRight());
System.out.println(root.getE());
}
}
//层序遍历
@Override
publicvoid leveltraverse() {
IQueue<TreeNode<E>> queue=new MylinkQueue<>();
TreeNode<E> temp=this.root;
queue.enqueue(temp);
while(!queue.isEmpty()) {
temp=queue.dequeue();
System.out.println(temp.getE());
if(temp.getLeft()!=null)
queue.enqueue(temp.getLeft());
if(temp.getRight()!=null)
queue.enqueue(temp.getRight());
}
}
}
4. 二叉排序树（二叉查找树）
a) 性质：左子树的值要小于其根节点的值，右子树的值要大于其根节点值
b) 代码实现如下
//创建二叉查找树,一般二叉查找树的数据元素类型都是Integer
publicclass MyBinaryTree {
private TreeNode<Integer> root;
//初始化二叉查找树
public MyBinaryTree(inte) {
super();
this.root = new TreeNode<Integer>(e);
}
//返回树的根节点
public TreeNode<Integer> getRoot() {
returnthis.root;
}
//将数据插入到二叉查找树的指定位置
publicvoid insert(inte) {
TreeNode<Integer> temp=this.root;
TreeNode<Integer> node=new TreeNode<Integer>(e);
while(temp!=null) {
//先比较数值与节点大小，比节点值大向节点的右子树搜索，比节点小向左子树搜索
if(e>temp.getE()) {
//如果节点的右子树为空，则在该节点将新建节点插入作为右子树并返回
if(temp.getRight()==null) {
temp.setRight(node);
return;
}
else
temp=temp.getRight();
}
else {
//如果节点的左子树为空，则在该节点将新建节点插入作为左子树并返回
if(temp.getLeft()==null) {
temp.setLeft(node);
return;
}
else
temp=temp.getLeft();
}
}
}
//先序遍历
publicvoid pretraverse(TreeNode<Integer> root) {
if(root!=null) {
System.out.println(root.getE());
pretraverse(root.getLeft());
pretraverse(root.getRight());
}
}
//中序遍历
publicvoid intraverse(TreeNode<Integer> root) {
if(root!=null) {
intraverse(root.getLeft());
System.out.println(root.getE());
intraverse(root.getRight());
}
}
//后续遍历
publicvoid posttraverse(TreeNode<Integer> root) {
if(root!=null) {
posttraverse(root.getLeft());
posttraverse(root.getRight());
System.out.println(root.getE());
}
}
//层序遍历
publicvoid leveltraverse() {
IQueue<TreeNode<Integer>> queue=new MylinkQueue<>();
TreeNode<Integer> temp=this.root;
queue.enqueue(temp);
while(!queue.isEmpty()) {
temp=queue.dequeue();
System.out.println(temp.getE());
if(temp.getLeft()!=null)
queue.enqueue(temp.getLeft());
if(temp.getRight()!=null)
queue.enqueue(temp.getRight());
}
}
}
5. 哈夫曼树
a) 概念：也叫最优二叉树，指由根节点到各个节点的路径长度乘以节点的权值，使得带权路径之和最小。
b) 要使得带权路径之和最小，则应该使权值大的节点离根节点近，权值小的节点离根节点远
c) 步骤：
i. 首先以每一个节点为根节点建立一棵树，形成一个集合
ii. 选出这些树中根节点权值最小的和次最小的两棵树作为左子树和右子树，两棵子树权值和为根节点形成一棵新的树
iii. 在原集合中删除作为左右子树的两棵树，并将新的树加入集合
iv. 重复ii,iii直到集合中只剩下一棵树
v. 假设每棵左子树到其父节点的边为0，右子树到其父节点的边1，按照先序遍历或者层序遍历求根节点到每个节点边的序列作为字符编码
1. 二叉树的逻辑结构
a) 定义：二叉树是一种非线性结构，是n个有限元素的集合，由一个根节点与两个不相交的左子树和右子树组成，当集合为空又称为空二叉树，一个元素也成为一个节点。二叉树是有序的。
b) 基本概念
i. 节点的度：节点下子树的个数，范围为0-2
ii. 叶节点：度为0的节点
iii. 分支节点：度不为0的节点
iv. 路径、路径长度：设n(i+1)是n(i)的父节点，则n(1)…n(k)称为一条路径，路径长度为k-1
v. 节点层数：从根节点开始到叶节点，每个节点层数等于其父节点的节点层数+1，根节点的节点层数位1
vi. 数的深度：叶节点的最大节点层数
vii. 数的度：各节点度的最大值，数的度最大位2
viii. 满二叉树：所有分支节点都有左子树和右子树且叶节点都在同一层的二叉树
ix. 完全二叉树：一棵深度为k有n个节点的二叉树，对树中的节点按照从上到下，从左到右的顺序进行编号，树中编号为i的节点与满二叉树编号为i的节点位置相同则称为完全二叉树。特点是：叶子节点只能出现在最下层和次下层，且最下层的叶子节点集中在左边。（可以理解为在一棵深度为k满二叉树的第k层（共有2^(k-1)个节点）的最右边第一个节点开始向左去掉0或(2^(k-1))或0-2^(k-1)之间的奇数个节点）
c) 主要性质
i. 非空二叉树的第k层最多有2^(k-1)个节点
ii. 一棵深度为k的二叉树最有有2^k-1个节点
iii. 对于一棵非空二叉树：叶子节点数=度为2的节点数+1
iv. 具有n个节点的满二叉树的深度为log(n+1)，具有n个节点的完全二叉树的深度为log(n)+1
v. 对于具有n个节点的完全二叉树，按照从上到下从左到右的顺序进行排序，对于序号为i的节点
[1] 若i>1，则双亲的序号为i/2的整数部分，i=1，则该节点是树的根节点；
[2] 若2i<n，则i的左孩子为2i，若2i>n，则该节点无左孩子
[3] 若2i+1<n，则i的右孩子为2i+1，若2i+1>n，则该节点无右孩子
d) 二叉树的抽象数据类型
i. 数据元素：具有相同类型的数据集合
ii. 数据结构：除根节点外，每个节点都有一个直接前驱，除叶节点外，每个节点都有1-2个直接后驱
iii. 数据操作：一般二叉树的操作定义在IBiTree接口中
publicinterface IBiTree<E> {
//返回根节点
TreeNode<E> getRoot();
//返回fnode的左子树
TreeNode<E> getLeftChild(TreeNode<E> fnode);
//返回fnode的右子树
TreeNode<E> getRightChild(TreeNode<E> fnode);
//向fnode左子树添加节点
void insertLeftChild(TreeNode<E> lcnode,TreeNode<E> fnode);
//向fnode的右子树添加节点
void insertRightChild(TreeNode<E> rcnode,TreeNode<E> fnode);
//删除fnode的左子树
TreeNode<E> deleteLeftChild(TreeNode<E> fnode);
//删除fnode的右子树
TreeNode<E> deleteRightChild(TreeNode<E> fnode);
//查找指定节点
TreeNode<E> find(TreeNode<E> target);
//以第前序方式遍历二叉树
void pretraverse(TreeNode<E> root);
//以中序方式遍历二叉树
void intraverse(TreeNode<E> root);
//以后序遍历二叉树
void posttraverse(TreeNode<E> root);
//以层序方式遍历二叉树
void leveltraverse();
}
2. 二叉树的实现之顺序存储
a) 顺序存储结构：用一组连续的数组来存储二叉树数据，通常按照从左到右、从上到下的顺序进行存储，对于一般的二叉树存储在数组中，下标不能很好的反映二叉树中的节点逻辑关系，需要在数组中添加空节点，这样比较浪费存储空间。因此，一般用数组存储满二叉树或者完全二叉树比较合适。
3. 二叉树的实现之链式存储
a) 链式存储结构
i. 二叉链式存储结构：每个节点包括存储数据的元素，指向左子树的left和指向右子树的right，当左子树或右子树不存在时，将left或者right设置为null
ii. 三叉链式存储结构：相比二叉链式存储结构增加了指向父节点的parent，最常用的时二叉链式存储结构
b) 代码实现
//定义树节点，包括数据，权值，左子树，右子树
publicclass TreeNode<E> {
private E e;
privateintweight;
private TreeNode<E> left;
private TreeNode<E> right;
//不带权值的构造方法
public TreeNode(E e) {
super();
this.e = e;
this.weight=0;
this.left = null;
this.right = null;
}
//带权值的构造方法
public TreeNode(E e, intweight) {
super();
this.e = e;
this.weight = weight;
}
public E getE() {
returne;
}
publicvoid setE(E e) {
this.e = e;
}
public TreeNode<E> getLeft() {
returnleft;
}
publicvoid setLeft(TreeNode<E> left) {
this.left = left;
}
public TreeNode<E> getRight() {
returnright;
}
publicvoid setRight(TreeNode<E> right) {
this.right = right;
}
}
//创建普通二叉树类
publicclass MyLinkTree<E> implements IBiTree<E> {
private TreeNode<E> root;
//初始化二叉树
public MyLinkTree(TreeNode<E> root) {
super();
this.root = root;
}
//返回树的根节点
@Override
public TreeNode<E> getRoot() {
returnthis.root;
}
//返回指定节点的左孩子
@Override
public TreeNode<E> getLeftChild(TreeNode<E> fnode) {
TreeNode<E> temp=find(fnode);
returntemp.getLeft();
}
//返回指定节点的右孩子
@Override
public TreeNode<E> getRightChild(TreeNode<E> fnode) {
TreeNode<E> temp=find(fnode);
returntemp.getRight();
}
//在指定节点插入左孩子，如过其左孩子已经存在，将原近年来的左孩子作为新建左孩子的左子树
@Override
publicvoid insertLeftChild(TreeNode<E> lcnode, TreeNode<E> fnode) {
TreeNode<E> temp=find(fnode);
if(temp.getLeft()!=null) {
TreeNode<E> left=temp.getLeft();
temp.setLeft(lcnode);
lcnode.setLeft(left);
}
else
temp.setLeft(lcnode);
}
//在指定节点插入右孩子，如果其右孩子存在，将其原来的右孩子作为新建右孩子的右子树
@Override
publicvoid insertRightChild(TreeNode<E> rcnode, TreeNode<E> fnode) {
TreeNode<E> temp=find(fnode);//找到指定节点
if(temp.getRight()!=null) {
TreeNode<E> right=temp.getRight();
temp.setRight(rcnode);
rcnode.setRight(right);
}
else
temp.setRight(rcnode);
}
//删除指定节点的左子树（将其左子树下的所有节点删除）
@Override
public TreeNode<E> deleteLeftChild(TreeNode<E> fnode) {
TreeNode<E> temp=find(fnode);
TreeNode<E> lcnode=temp.getLeft();
temp.setLeft(null);
returnlcnode;
}
//删除指定节点的右子树（将其右子树下的所有节点删除）
@Override
public TreeNode<E> deleteRightChild(TreeNode<E> fnode) {
TreeNode<E> temp=find(fnode);
TreeNode<E> rcnode=temp.getRight();
temp.setRight(null);
returnrcnode;
}
//利用层序遍历找到指定节点
public TreeNode<E> find(TreeNode<E> target){
TreeNode<E> temp=this.root;
IQueue<TreeNode> queue=new MylinkQueue<>();
queue.enqueue(temp);
while(!queue.isEmpty()) {
temp=queue.dequeue();
if(temp==target)
returntemp;
if(temp.getLeft()!=null)
queue.enqueue(temp.getLeft());
if(temp.getRight()!=null)
queue.enqueue(temp.getRight());
}
returnnull;
}
//前序遍历
@Override
publicvoid pretraverse(TreeNode<E> root) {
if(root!=null) {
System.out.println(root.getE());
pretraverse(root.getLeft());
pretraverse(root.getRight());
}
}
//中序遍历
@Override
publicvoid intraverse(TreeNode<E> root) {
if(root!=null) {
intraverse(root.getLeft());
System.out.println(root.getE());
intraverse(root.getRight());
}
}
//后续遍历
@Override
publicvoid posttraverse(TreeNode<E> root) {
if(root!=null) {
posttraverse(root.getLeft());
posttraverse(root.getRight());
System.out.println(root.getE());
}
}
//层序遍历
@Override
publicvoid leveltraverse() {
IQueue<TreeNode<E>> queue=new MylinkQueue<>();
TreeNode<E> temp=this.root;
queue.enqueue(temp);
while(!queue.isEmpty()) {
temp=queue.dequeue();
System.out.println(temp.getE());
if(temp.getLeft()!=null)
queue.enqueue(temp.getLeft());
if(temp.getRight()!=null)
queue.enqueue(temp.getRight());
}
}
}
4. 二叉排序树（二叉查找树）
a) 性质：左子树的值要小于其根节点的值，右子树的值要大于其根节点值
b) 代码实现如下
//创建二叉查找树,一般二叉查找树的数据元素类型都是Integer
publicclass MyBinaryTree {
private TreeNode<Integer> root;
//初始化二叉查找树
public MyBinaryTree(inte) {
super();
this.root = new TreeNode<Integer>(e);
}
//返回树的根节点
public TreeNode<Integer> getRoot() {
returnthis.root;
}
//将数据插入到二叉查找树的指定位置
publicvoid insert(inte) {
TreeNode<Integer> temp=this.root;
TreeNode<Integer> node=new TreeNode<Integer>(e);
while(temp!=null) {
//先比较数值与节点大小，比节点值大向节点的右子树搜索，比节点小向左子树搜索
if(e>temp.getE()) {
//如果节点的右子树为空，则在该节点将新建节点插入作为右子树并返回
if(temp.getRight()==null) {
temp.setRight(node);
return;
}
else
temp=temp.getRight();
}
else {
//如果节点的左子树为空，则在该节点将新建节点插入作为左子树并返回
if(temp.getLeft()==null) {
temp.setLeft(node);
return;
}
else
temp=temp.getLeft();
}
}
}
//先序遍历
publicvoid pretraverse(TreeNode<Integer> root) {
if(root!=null) {
System.out.println(root.getE());
pretraverse(root.getLeft());
pretraverse(root.getRight());
}
}
//中序遍历
publicvoid intraverse(TreeNode<Integer> root) {
if(root!=null) {
intraverse(root.getLeft());
System.out.println(root.getE());
intraverse(root.getRight());
}
}
//后续遍历
publicvoid posttraverse(TreeNode<Integer> root) {
if(root!=null) {
posttraverse(root.getLeft());
posttraverse(root.getRight());
System.out.println(root.getE());
}
}
//层序遍历
publicvoid leveltraverse() {
IQueue<TreeNode<Integer>> queue=new MylinkQueue<>();
TreeNode<Integer> temp=this.root;
queue.enqueue(temp);
while(!queue.isEmpty()) {
temp=queue.dequeue();
System.out.println(temp.getE());
if(temp.getLeft()!=null)
queue.enqueue(temp.getLeft());
if(temp.getRight()!=null)
queue.enqueue(temp.getRight());
}
}
}
5. 哈夫曼树
a) 概念：也叫最优二叉树，指由根节点到各个节点的路径长度乘以节点的权值，使得带权路径之和最小。
b) 要使得带权路径之和最小，则应该使权值大的节点离根节点近，权值小的节点离根节点远
c) 步骤：
i. 首先以每一个节点为根节点建立一棵树，形成一个集合
ii. 选出这些树中根节点权值最小的和次最小的两棵树作为左子树和右子树，两棵子树权值和为根节点形成一棵新的树
iii. 在原集合中删除作为左右子树的两棵树，并将新的树加入集合
iv. 重复ii,iii直到集合中只剩下一棵树
v. 假设每棵左子树到其父节点的边为0，右子树到其父节点的边1，按照先序遍历或者层序遍历求根节点到每个节点边的序列作为字符编码
数据结构（java描述）之二叉树
基础概念 二叉树(binarytree)是一棵树，其中每个结点都不能有多于两个儿子。 二叉排序树或者是一棵空树，或者是具有下列性质的二叉树： （1）若左子树不空，则左子树上所有结点的值均小于或等于它的根... 查看详情
java数据结构与算法之二叉树
二叉树树存储方式的分析能提高数据存储，读取的效率,比如利用二叉排序树(BinarySortTree)，既可以保证数据的检索速度，同时也可以保证数据的插入，删除，修改的速度。树示意图:二叉树遍历的说明1)前序遍历:先输出父节点，再... 查看详情
java数据结构之二叉树(代码片段)
1、二叉树各功能模块介绍 1.1、创建二叉树 二叉树数据输入是广义表输入形式：A(B(C),D(E(F,G),H(,I)))。创建该二叉树使用的是非递归方式。整个流程为：A是根元素，B、D为A的子节点，所以输入A时&#x... 查看详情
第四节：java集合框架之二叉树
文章目录一：树基本概念（1）树的定义（2）结点分类（3）结点关系（相关术语）（4）常用性质二：二叉树基本概念（1）二叉树定义（2）二叉树五种形态（3）特殊的二叉树（4）二叉树常考性质（5）二叉树存储结构——二叉链... 查看详情
第四节：java集合框架之二叉树
文章目录一：树基本概念（1）树的定义（2）结点分类（3）结点关系（相关术语）（4）常用性质二：二叉树基本概念（1）二叉树定义（2）二叉树五种形态（3）特殊的二叉树（4）二叉树常考性质（5）二叉树存储结构——二叉链... 查看详情
树之二叉树
刚学数据结构的时候，一直不明白数据结构到底有什么用，直到对高级编程语言——Java有了进一步的认识之后，才发现数据结构的重要性，Java中的TreeMap,TreeSet等集合中包含了设计精美的数据结构，正如书中所说的那样，树是“... 查看详情
《数据结构》复习之二叉树
...性质1满二叉树和完全二叉树2二叉树的主要性质二叉树的数据结构二叉树的算法补充总结1.二叉树的性质1.1满二叉树和完全二叉树 在一棵二叉树中，如果所有的分支节点都有左孩子和右孩子，并且叶子节点都集中在二叉树的... 查看详情
sdut3341数据结构实验之二叉树二：遍历二叉树
数据结构实验之二叉树二：遍历二叉树TimeLimit: 1000MS MemoryLimit: 65536KBSubmit StatisticProblemDescription已知二叉树的一个按先序遍历输入的字符序列，如abc,,de,g,,f,,, (其中,表示空结点)。请建立二叉树并按中序和后序的... 查看详情
sdut3343数据结构实验之二叉树四：还原二叉树
数据结构实验之二叉树四：还原二叉树TimeLimit: 1000MS MemoryLimit: 65536KBSubmit StatisticProblemDescription给定一棵二叉树的先序遍历序列和中序遍历序列，要求计算该二叉树的高度。Input输入数据有多组，每组数据第一行输... 查看详情
数据结构之二叉树
满二叉树：每一个结点要么左右结点都是空的，要么左右结点都是存在的。完全二叉树：若一个树的高度为N，那么除了第N-1层外，每层都是满的，且最后一层的数据是从左往右排列的。若一个二叉树只有一个根结点，那么根结... 查看详情
数据结构之二叉树(代码片段)
简述：二叉树是十分重要的数据结构，主要用来存放数据，并且方便查找等操作，在很多地方有广泛的应用。二叉树有很多种类，比如线索二叉树，二叉排序树，平衡二叉树等，本文写的是最基础最简单的二叉树。思路：二叉树... 查看详情
sdut3341数据结构实验之二叉树二：遍历二叉树(代码片段)
数据结构实验之二叉树二：遍历二叉树TimeLimit: 1000ms MemoryLimit: 65536KiBProblemDescription已知二叉树的一个按先序遍历输入的字符序列，如abc,,de,g,,f,,, (其中,表示空结点)。请建立二叉树并按中序和后序的方式遍历该... 查看详情
数据结构之二叉树
参考博客：https://blog.csdn.net/qq_40772692/article/details/79343914 一、二叉树的常用性质<1>.在二叉树的第i层上最多有2 i-1 个节点。（i>=1）<2>.二叉树中如果深度为k(有k层),那么最多有2k-1个节点。(k>=1）<3>.若二... 查看详情
数据结构之二叉树(代码片段)
概要参考《大话数据结构》，把常用的基本数据结构梳理一下。本节介绍二叉树。?定义??二叉树（BinaryTree）是\(n\)（\(n\geqslant0\)）个结点的有限集合，该集合或者为空集（称为空二叉树），或者由一个根结点和两棵互不相交的、... 查看详情
数据结构之二叉树的实现(代码片段)
二叉树的实现文章目录二叉树的实现二叉链表结构：建立节点之间的关系二叉树的遍历前序遍历中序遍历后序遍历层序遍历节点个数以及高度二叉树结点个数二叉树叶子节点个数二叉树第k层节点个数二叉树的深度二叉树查找... 查看详情
数据结构之二叉树
基础概念 二叉树(binarytree)是一棵树，其中每个结点都不能有多于两个儿子。 二叉排序树或者是一棵空树，或者是具有下列性质的二叉树： （1）若左子树不空，则左子树上所有结点的值均小于或等于它的根... 查看详情
剑指offer之二叉树
0.科普队列(queue)是一种常用的数据结构，可以将队列看做是一种特殊的线性表，该结构遵循的先进先出原则。Java中，LinkedList实现了Queue接口,因为LinkedList进行插入、删除操作效率较高相关常用方法：booleanoffer(Ee):将元素追加到队... 查看详情
数据结构之二叉树(代码片段)
1.二叉树的基本概念 二叉树是一种非常常见并实用的数据结构，它结合了有序数组和链表的优点，在二叉树中查找数据与在数组中查找数据一样快，在二叉树中添加删除数据的速度与在链表中一样高效。 二叉树也称为二... 查看详情