二叉树是树结构的一种，一种一对多的逻辑关系，
基本概念：父节点有且最多只有两个子节点
树的名词解释：
根节点：二叉树的顶层节点有且只有一个，如图中的1节点
父节点：相比较的概念的，如：2是5和4的父节点，1是2的父节点
子节点：和父节点一样也相对的 如：对于8和9而言它是4的子节点，而对于4它是2的子节点……
层：它来判断树的高度，如图中有4层
权：指每个节点的存储的值(数据)，图中每个节点存储了数字这就是权
路径：指从当前节点到其他节点的路线，如：从2到5的路线就是路线，每个节点都有一个左右指向
叶子节点：没有子节点的节点，如：8，9，10，11，6，7都是叶子节点
子树：类比于一颗大树的树枝，如：2，4，5就叫一颗子树
树的高度：最大层数
------满二叉树和完全二叉树-------
满二叉树：所有的叶子节点都在最后一层，节点的总数=2^n-1(n为层数)
图中就是一个满二叉树，所有节点都在最后一层，它的节点总数=2^3-1为7个节点
完全二叉树：所有的叶子节点都在最后一层或者倒数第二层，最后一层向左连续，倒数第二层向右连续
假如5，6，7其中一个没有就不存在连续也就不完全二叉树
--------二叉树的实现-----------
在数据结构的分类中物理存储分两类：顺序存储和链式存储
在数据结构中每一个逻辑结构都依赖于物理存储结构，通过物理结构来实现逻辑结构
二叉数有两种实现方式，一种是链式存储二叉树，一个顺序存储二叉树(堆的实现依赖于顺序二叉树)
------------链式二叉树-------------
构建图中的二叉树：
public class chaintree {
public static void main(String[] args) {
//建立节点:定义6个节点
predata a=new predata(1);
predata b=new predata(2);
predata c=new predata(3);
predata d=new predata(4);
predata e=new predata(5);
predata f=new predata(6);
//给他们建立关系
//a点的左节点是b，a的右节点是c
a.setLife(b);
a.setRight(c);
//b的左节点是d，右节点是e
b.setLife(d);
b.setRight(e);
//c的右节点是f，没有左节点
c.setRight(f);
//将节点关系放进树里面
tree wql=new tree(a);
wql.front();//1，2，4，5，3，6
}
}
//定义树把节点类的节点联系放进树
class tree{
private predata treewql;
public tree(predata treewql){
this.treewql=treewql;
}
//从树类中调用遍历方法
//前序遍历
public void front(){
if(treewql==null){
System.out.println("树为空");
}else{
treewql.front();
}
}
//中序遍历
public void centre(){
if(treewql==null){
System.out.println("树为空");
}else{
treewql.centre();
}
}
//后序遍历
public void later(){
if(treewql==null){
System.out.println("树为空");
}else{
treewql.later();
}
}
}
//节点类
class predata{
private predata life;//定义左子节点
private predata right;//定义右子节点
private int val;//给我树一个权值
//初始化值
public predata(int val){
this.val=val;
}
//给当前节点设置它的左节点
public void setLife(predata life) {
this.life = life;
}
//给当前节点设置它左节点
public void setRight(predata right) {
this.right = right;
}
//toString方法
@Override
public String toString() {
return "predata{" +
"val=" + val +
'}';
}
//前序遍历:先输出父节点，再输出左子节点，最后是右子节点
public void front(){
System.out.println(this);//前序遍历首先输当前节点也就是父节点
if(this.life!=null){//输出左子节点，先判断左子节点是否为空，再递归输出左子节点
this.life.front();
}
if(this.right!=null){//输出右子节点，先判断右子节点是否为空，再递归输出右子节点
this.right.front();
}
}
//中序遍历:先输出左子节点，再输出父节，最后是右子节点
public void centre(){
//中序遍历首先输当前节点也就是父节点
if(this.life!=null){//输出左子节点，先判断左子节点是否为空，再递归输出左子节点
this.life.centre();
}
//中间输出父节点
System.out.println(this);
if(this.right!=null){//输出右子节点，先判断右子节点是否为空，再递归输出右子节点
this.right.centre();
}
}
//后序遍历:先输出左子节点，再输出右子节点，最后是父节点
public void later(){
//中序遍历首先输当前节点也就是父节点
if(this.life!=null){//输出左子节点，先判断左子节点是否为空，再递归输出左子节点
this.life.later();
}
//中间输出右子节点
if(this.right!=null){//输出右子节点，先判断右子节点是否为空，再递归输出右子节点
this.right.later();
}
//最后输出父节点
System.out.println(this);
}
}
前序遍历,中序遍历,后序遍历的区别在于父节点输出的位置,前序就是父节最先输出,以此类推
前序:父节点 -> 左子节点 -> 右子节点
中序:左子节点 ->父节点 -> 右子节点
后序:左子节点 ->右子节点 -> 父节点
----------顺序存储二叉树---------
顺序存储二叉树与链式存储二叉树不同,它的节点是数组的一个个区间,数组中存储的值就是树的权
树的左节点=2*当前节点在数组中的索引+1
树的右节点=2*当前节点在数组中的索引+2
通过索引来计算左右树
如图中:
a的左节点=2*0+1(索引)
c的右节点=2*2+2(索引)
public class ordertree {
public static void main(String[] args) {
int[] WQL=new int[]{1,2,3,4,5,6};
datawql a=new datawql(WQL);
a.alter1(0); //1,2,4,5,3,6
}
}
class datawql{
int[] datas;
public datawql(int[] datas){
this.datas=datas;
}
//前序遍历
public void front1(int index){//给出要遍历的起始节点的索引
if(datas[index]!=0 && index<datas.length) {
System.out.println(datas[index]);
}
if((index*2+1)<datas.length){
front1(index*2+1);
}
if((index*2+2)<datas.length){
front1(index*2+2);
}
}
//中序遍历
public void concre1(int index){//给出要遍历的起始节点的索引
if((index*2+1)<datas.length){
concre1(index*2+1);
}
if(datas[index]!=0 && index<datas.length) {
System.out.println(datas[index]);
}
if((index*2+2)<datas.length){
concre1(index*2+2);
} }
//中序遍历
public void alter1(int index){//给出要遍历的起始节点的索引
if((index*2+1)<datas.length){//index大于数组长度就声明不存在
alter1(index*2+1);
}
if(datas[index]!=0 && index<datas.length) {
System.out.println(datas[index]);
}
if((index*2+2)<datas.length){
alter1(index*2+2);
} }
}
-----------堆排序-----------
堆排序是利用堆这个数据结构而设计的一种排序算法(是一种不稳定排序)
堆是一个完全二叉树它有两个特性:
大顶堆:父节点比子节点大(不比较叶子节点的大小)
小定堆:父节点比子节点小(不比较叶子节点的大小)
public class heapsort {
public static void main(String[] args) {
int[] a=new int[]{2,3,1,6,4};
heap1 s=new heap1(a);
}
}
//将堆进行排序
class hea1sort{
heap1 c;
public hea1sort(heap1 c){
this.c=c;
}
public void sort(){
for(int a=c.a.length/2-1;a>=0;a--){
c.adjustheap(a);
}
}
}
//定义一个堆
class heap1{
int[] a;
public heap1(int[] a){
this.a=a;
}
//将数组的二叉树转化成一个堆
public void adjustheap(int i){//非叶子节点的索引
int[] n=a;
int temp=n[i];//保存当前节点的值
for(int i1=i*2+1; i1>=0; i1=i*2+1){
//接收当前节点得到左节点(i*2+1)，判断左节点是否比右节点大，如果比右节点小就把左节点的索引改成右索引
if(i1+1<n.length && n[i1+1] >n[i1]){
i1++;
}
//判断当前非叶子节点的根节点是是否比子节点大，如果小就把子节点的值赋给当前节点也就是a[i]
if(i1+1<n.length && n[i] < n[i1]){
n[i]=n[i1];
i=i1;//把i(当前的父节点索引)换成子节点索引
}else {
break;//这个方法只判断一个非叶子节点
}
n[i]=temp;//如果前后的if条件符号就把之前父节点的值再给子节点
}
}
}
Comments | NOTHING