首页 / 算法 / 【二叉树】二叉树的创建与遍历
【二叉树】二叉树的创建与遍历
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了【二叉树】二叉树的创建与遍历，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含3726字，纯文字阅读大概需要6分钟。
内容图文
一、定义
二叉树是一个连通的无环图，并且每一个顶点的度不大于3。有根二叉树还要满足根结点的度不大于2。有了根结点之后，每个顶点定义了唯一的父结点，和最多2个子结点。
二、性质
- 在非空二叉树中，第i层的结点总数不超过
, i>=1； - 深度为h的二叉树最多有
个结点(h>=1)，最少有h个结点； - 对于任意一棵二叉树，如果其叶结点数为N0，而度数为2的结点总数为N2，则N0=N2+1；
- 具有n个结点的完全二叉树的深度为
（注：[ ]表示向下取整） - 有N个结点的完全二叉树各结点如果用顺序方式存储，则结点之间有如下关系：
- 若I为结点编号则 如果I>1，则其父结点的编号为I/2；
- 如果2*I<=N，则其左孩子（即左子树的根结点）的编号为2*I；若2*I>N，则无左孩子；
- 如果2*I+1<=N，则其右孩子的结点编号为2*I+1；若2*I+1>N，则无右孩子。
- 给定N个结点，能构成h(N)种不同的二叉树。h(N)为卡特兰数的第N项。h(n)=C(2*n，n)/(n+1)；
- 设有i个枝点，I为所有枝点的道路长度总和，J为叶的道路长度总和J=I+2i。
三、二叉树的创建
@Setter
@Getter
@ToString
public
class
BinaryTree {
private Object data;//当前节点数据private BinaryTree lChild;//当前节点左孩子private BinaryTree rChild;//当前节点右孩子private BinaryTree root;//根节点
//构造函数public BinaryTree (Object data){
this.data = data;
}
//创建二叉树publicvoid creatBinaryTree (Object data[]){
//将数据转换为节点存储
List<BinaryTree> list = new ArrayList<BinaryTree>();
for (Object tmpdata:data){
list.add(new BinaryTree(tmpdata));
}
//第1个节点作为根节点
root = list.get(0);
//构建二叉树for (int i=0;i<list.size()/2;i++){
//父节点位置为i，左子节点位置为i*2+1if (i*2+1<list.size()){
list.get(i).setLChild(list.get(i*2+1));
}
//父节点位置为i，左子节点位置为i*2+2if (i*2+2<list.size()){
list.get(i).setRChild(list.get(i*2+2));
}
}
}
}
四、二叉树的遍历
1、前序遍历
//
前序遍历(递归)
public
void
preOrder_Recursive(BinaryTree root){
if (root!=null){
System.out.print(" "+root.getData());
preOrder_Recursive(root.getLChild());
preOrder_Recursive(root.getRChild());
}
}
2、中序遍历
//
中序遍历(递归)
public
void
inOrder_Recursive(BinaryTree root){
if (root!=null){
inOrder_Recursive(root.getLChild());
System.out.print(" "+root.getData());
inOrder_Recursive(root.getRChild());
}
}
3、后序遍历
//
后序遍历(递归)
public
void
postOrder_Recursive(BinaryTree root){
if (root!=null){
postOrder_Recursive(root.getLChild());
postOrder_Recursive(root.getRChild());
System.out.print(" "+root.getData());
}
}
4、层次遍历
//
层次遍历
public
void
levelOrder(BinaryTree root){
//
当前节点
BinaryTree current = null;
//创建队列用于临时存放节点
LinkedList<BinaryTree> queue = new LinkedList<BinaryTree>();
if (root!=null){
//根节点入队 queue.offer(root);
}
while(!queue.isEmpty()){
//出队队头节点
current = queue.poll();
System.out.print(" "+current.getData());
//若有左子节点，则将其入队if (current.getLChild()!=null){
queue.offer(current.getLChild());
}
//若有右子节点，则将其入队if (current.getRChild()!=null){
queue.offer(current.getRChild());
}
}
}
五、二叉树的视图
1、左视图
//
左视图
public
void
leftView(BinaryTree root){
//
当前节点
BinaryTree current = null;
//创建队列用于临时存放节点
LinkedList<BinaryTree> queue = new LinkedList<BinaryTree>();
if (root!=null){
//根节点入队 queue.offer(root);
System.out.print(" "+root.getData());
}
while(!queue.isEmpty()){
int size = queue.size();
while(size>0) {
//出队队头节点
current = queue.poll();
//若有左子节点，则将其入队if (current.getLChild() != null) {
queue.offer(current.getLChild());
}
//若有右子节点，则将其入队if (current.getRChild() != null) {
queue.offer(current.getRChild());
}
size--;
//size==0时，队列中第1个节点为下一层右边第1个节点if (size==0 && queue.size()>0){
System.out.print(" "+queue.getFirst().getData());
}
}
}
}
2、右视图
//
右视图
public
void
rightView(BinaryTree root){
//
当前节点
BinaryTree current = null;
//创建队列用于临时存放节点
LinkedList<BinaryTree> queue = new LinkedList<BinaryTree>();
if (root!=null){
//根节点入队 queue.offer(root);
System.out.print(" "+root.getData());
}
while(!queue.isEmpty()){
int size = queue.size();
while(size>0) {
//出队队头节点
current = queue.poll();
//若有右子节点，则将其入队if (current.getRChild() != null) {
queue.offer(current.getRChild());
}
//若有左子节点，则将其入队if (current.getLChild() != null) {
queue.offer(current.getLChild());
}
size--;
//size==0时，队列中第1个节点为下一层左边第1个节点if (size==0 && queue.size()>0){
System.out.print(" "+queue.getFirst().getData());
}
}
}
}
原文：https://www.cnblogs.com/6970-9192/p/11495725.html
内容总结
以上是互联网集市为您收集整理的【二叉树】二叉树的创建与遍历全部内容，希望文章能够帮你解决【二叉树】二叉树的创建与遍历所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。
来源：【匿名】