什么是二叉树
通俗的讲就是树上每一个节点最多有两个子节点
官方的递归定义是:
- 要么二叉树没有根节点,是一颗空树
- 要么二叉树由根结点、左子树、右子树组成,且左右子树也都是二叉树
这里有两种特殊的二叉树。
- 满二叉树:每一层的结点个数都达到了当层能达到的最大结点数
- 完全二叉树:除了最下面一层,其他层的节点个数都达到了当曾能达到的最大结点数,且最下面一层只从左到右连续存在若干个结点,而这些连续结点的右边的结点全部不存在
这里再介绍几个常用的概念
孩子结点:与该结点相连的下一层结点
父亲结点:与该结点相连的上一层结点
兄弟结点:拥有同一父亲结点的结点
祖先结点:该结点的父结点到根结点连线上的所有结点
子孙结点:该结点以下的所有结点
注意自己既是自己的祖先结点也是自己的子孙结点
二叉树的存储结构和基本操作
1.二叉树的存储结构
二叉树是以链表的形式来存储的,每个结点由地址域,数据域和两个指针域构成。
创建二叉树的结点类,由于java没有引用,所以需要比C++多增加一个父结点
public class BinaryNode{
int data;
BinaryNode lchild;
BinaryNode rchild;
BinaryNode pnode;
public BinaryNode(int data) {
this.data = data;
}
public BinaryNode(){
}
}
2.二叉树的建立查找和修改
创建新结点
new BinaryNode(data)
查找结点
public static void search(BinaryNode root,int data,int newdata ){
if(root==null){
return ;
}
if(root.data==data){
root.data=newdata;
}
search(root.lchild,data,newdata);
search(root.rchild,data,newdata);
}
插入结点
方法一:这里需要定义一个全局变量,因为java中没有引用,没办法将改变后的地址往上传,所以用一个全局变量记录递归上一层的地址
private static BinaryNode tree;
public static void insert(BinaryNode root,int x){
if(root==null){
BinaryNode node=newNode(x);
node.pnode=tree;
if(tree.data<=x){
tree.rchild=node;
}else{
tree.lchild=node;
}
return;
}
tree=root;
if(root.data<=x){
insert(root.rchild,x);
}else{
insert(root.lchild,x);
}
}
方法二:这个比上面一个方法简单了很多,并且不用定义全局变量,也不用pnode属性,这是因为这个方法在递归前已经判断子节点存不存在,就不用考虑引用的问题了(推荐)
public static void insert(BinaryNode root,int x){
if(root.data<=x&&root.rchild!=null){
insert(root.rchild,x);
}else if(root.data>x&&root.lchild!=null){
insert(root.lchild,x);
}else if(root.data<=x){
root.rchild=new BinaryNode(x);
return;
}else{
root.lchild=new BinaryNode(x);
return;
}
}
建立二叉树
BinaryNode BinaryNode = newNode(3);
insert(BinaryNode,2);
insert(BinaryNode,5);
insert(BinaryNode,7);
insert(BinaryNode,4);
insert(BinaryNode,1);
insert(BinaryNode,9);
二叉树的遍历
先序遍历
public void preOrder(BinaryNode root){
if(root==null){
return ;
}
System.out.println(root.data);
preOrder(root.lchild);
preOrder(root.rchild);
}
中序遍历
public void inorder(BinaryNode root){
if(root==null) {
return;
}
preOrder(root.lchild);
System.out.println(root.data);
preOrder(root.rchild);
}
后序遍历
public void postorder(BinaryNode root){
if(root==null) {
return;
}
preOrder(root.lchild);
preOrder(root.rchild);
System.out.println(root.data);
}
层序遍历,Queue是一个接口,LinkedList实现了该接口,使用poll,peek,offer方法
public void layerOrder(BinaryNode root){
Queue<BinaryNode> queue = new LinkedList<>();
queue.offer(root);
while(!queue.isEmpty()){
BinaryNode peek=queue.peek();
System.out.println(peek.data);
if(peek.lchild!=null) queue.offer(peek.lchild);
if(peek.rchild!=null) queue.offer(peek.rchild);
queue.poll();
}
}
最后一个问题经常考虑的就是给定一棵二叉树的先序和中序,重建这颗二叉树,只有有中序排列的二叉树才能重建
BinaryNode create(int preL,int preR,int inL,int inR,int[] pre,int[] in){
if(preL>preR){
return null;
}
BinaryNode root=new BinaryNode();
root.data=pre[preL];
int k;
for(k=inL;k<=inR;k++){
if(in[k]==pre[preL]){
break;
}
}
int numLeft=k-inL;
root.lchild=create(preL+1,preL+numLeft,inL,k-1,pre,in);
root.rchild=create(preL+numLeft+2,preR,k+1,inR,pre,in);
return root;
}
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)