精华内容
下载资源
问答
  • //完全二叉树 void swap(int tree[],int i,int max) //存在更大的结点值 (使此时最大结点的值与当前最大结点的值交换 { int temp; temp=tree[i]; tree[i]=tree[max]; tree[max]=temp; } void...

    构建大顶堆:

     

    #include<bits/stdc++.h> 
    //堆是完全二叉树 
    void swap(int tree[],int i,int max) //存在更大的结点值 (使此时最大结点的值与当前最大结点的值交换
    {
    	int temp;
    	temp=tree[i];
    	tree[i]=tree[max];
    	tree[max]=temp;		
    }
    void heapify(int tree[],int n,int i){  //构建堆 buildHeap和heapify分开写更加灵活 
    	if(i>=n){
    		return;
    	}
    	int c1=2*i+1;
    	int c2=2*i+2;
    	int max=i;
    	if(c1<n&&tree[max]<tree[c1]){
    		max=c1; //这里的max为最大值的下标(索引位置)
    	}
    	if(c2<n&&tree[max]<tree[c2]){
    		max=c2; //这里的max为最大值的下标
    	}
    	if(max!=i){     
    		swap(tree,i,max); //交换结点tree[i], tree[max]
    		heapify(tree,n,max);//交换了结点后, 左右子树被交换结点的子树需要重新构建堆
    	}
    	
    }
    void buildHeap(int tree[],int n){ // 	从最后一个元素构建堆 传入的n是tree数组中的最后一个元素为了保证
    	int lastnode=n-1;				 //保证每个子结点的树都是堆 
    	int parentId=(lastnode-1)/2;         //从最后一个不是叶节点的点开始往前做heapify操作的 
    	for(int i=parentId;i>=0;i--){
    		heapify(tree,n,i);
    	}
    }
    
    void heapSort(int tree[],int n){//完成堆排序 
    	buildHeap(tree,n);//此时使树中子结点都满足堆排序 
    	for(int i=n-1;i>=0;i--){
    		swap(tree,0,i);   
    		heapify(tree,i,0);//重新构成堆,因为除了首节点外,其余的点
    						  //都已经是堆结构了,所以不用buildHeap倒叙重新构建堆了 
    	}
    }
    int main(){
    	int tree[]={4,10,3,5,1,2};
    	int n=6;
    //	buildHeap(tree,6);
    	heapSort(tree,n);
    	for(int i=0;i<n;i++)   //此时是树中子结点都满足子堆 						   //但是不规则的堆就不能用 
    		printf("%d\n",tree[i]);	
    	
    	return 0;
    }
    展开全文
  • 堆排序是基于完全二叉树实现的,在将一个数组调整成一个堆的时候,关键之一的是确定最后一个非叶子节点的序号,这个序号为n/2-1,n为数组的长度。但是为什么呢? 可以分两种情形考虑: ①堆的最后一个非叶子节点若...

    堆排序是基于完全二叉树实现的,在将一个数组调整成一个堆的时候,关键之一的是确定最后一个非叶子节点的序号,这个序号为n/2-1,n为数组的长度。但是为什么呢?

    可以分两种情形考虑:

    ①堆的最后一个非叶子节点若只有左孩子

    ②堆的最后一个非叶子节点有左右两个孩子

    完全二叉树的性质之一是:如果节点序号为i,在它的左孩子序号为2*i+1,右孩子序号为2*i+2。

     

    对于①左孩子的序号为n-1,则n-1=2*i-1,推出i=n/2-1;

     

    对于②左孩子的序号为n-2,在n-2=2*i-1,推出i=(n-1)/2-1;右孩子的序号为n-1,则n-1=2*i+2,推出i=(n-1)/2-1;

    很显然,当完全二叉树最后一个节点是其父节点的左孩子时,树的节点数为偶数;当完全二叉树最后一个节点是其父节点的右孩子时,树的节点数为奇数。

    根据java语法的特征,整数除不尽时向下取整,则若n为奇数时(n-1)/2-1=n/2-1。

    因此对于②最后一个非叶子节点的序号也是n/2-1。

    得证。

    显然序号是从0开始的。

    展开全文
  • 堆排序: 创建一棵完全二叉树。 利用完全二叉树进行堆排序

    堆排序

    注:堆是一种完全二叉树;
    大根堆即根节点的值>=其左右子树根节点的值;
    小根堆即根节点的值<=其左右子树根节点的值。

    第一步:创建一棵完全二叉树

    分析:

    完全二叉树特点:

    1. 单分支结点的个数为0或1;
    2. 共有n层,则前n-1层共有2^(n-1)-1个结点。即总是从最后一层的最右边连续缺失结点。(个人理解)

    创建一棵完全二叉树即按层创建一棵二叉树,不可用递归创建。

    创建完全二叉树代码如下

    :`
    typedef struct node{
    int data;
    struct node *left,*right;
    }HeapNode;
    //创建完全二叉树
    HeapNode *CreatTree(int *Data,int n,HeapNode **Q)
    {
    //队列初始化(0号不用)
    int front,rear,pa,i;
    HeapNode *root;
    front=0;
    rear=0;
    pa=1;
    //创建并初始化根节点
    root=(HeapNode *)malloc(sizeof(HeapNode));
    root->data=Data[0];
    root->left=NULL;
    root->right=NULL;
    Q[++rear]=root;
    //遍历数据集合建树
    for(i=1;i

    第二步:通过不断将完全二叉树调节为大根堆进行堆排序

    代码如下

    typedef struct node{
        int data;
        struct node *left,*right;
    }HeapNode;
    //堆排序
    void HeapSort(HeapNode *root,HeapNode **Q,int n)
    {
        int rear=n;//尾指针等于数据域Q的元素个数
        int pa;
        int tag;
        int temp;
        int i;
        //利用循环对除根节点之外的结点排序
        while(rear>1)
        {
            //利用死循环将二叉树调成一个大根堆
            while(1)
            {
                //利用循环把二叉树调节一次!!!!!
                for(tag=0,pa=rear/2;pa>0;pa--)
                {
    
                    if(Q[pa]->data<Q[pa]->left->data)
                    {
                        temp=Q[pa]->data;
                        Q[pa]->data=Q[pa]->left->data;
                        Q[pa]->left->data=temp;
                        tag=1;
                    }
                    if(Q[pa]->right&&Q[pa]->data<Q[pa]->right->data)
                    {
                        temp=Q[pa]->data;
                        Q[pa]->data=Q[pa]->right->data;
                        Q[pa]->right->data=temp;
                        tag=1;
                    }
                }
                if(tag==0)
                    break;
            }
            //交换大根堆中最后一个结点与根结点的数值
            temp=Q[rear]->data;
            Q[rear]->data=Q[1]->data;
            Q[1]->data=temp;
            //在树上将最后一个结点断链删去
            //可以利用rear的奇偶性判断最后一个结点是其双亲的左子女还是右子女
            //也可以直接用双亲的左是否为空来判断
            if(rear%2)
                Q[rear/2]->right=NULL;
            else
                Q[rear/2]->left=NULL;
    
            //在数组中将利用尾指针将当前最后一个元素排除在下次排序之外
            rear--;
        }
        /*输出利用大根堆排序的结果---降序排列。需要逆序输出数组Q对应的结点的数据*/
        printf("The result of HeapSort is:\n");
        for(i=n;i>0;i--)
        {
            printf("%5d",Q[i]->data);
        }
    
    }
    int main(void)
    {
        HeapNode *root;
        HeapNode **Q;
        int *Data;
        int n,i;
        printf("Please input the number of the data");
        scanf("%d",&n);
        Data=(int *)malloc(n*sizeof(int));
        for(i=0;i<n;i++)
        {
            scanf("%d",&Data[i]);
        }
        //队列创建
        Q=(HeapNode **)malloc((n+1)*sizeof(HeapNode *));
        //创建完全二叉树
        root=CreatTree(Data,n,Q);
        OutPrintTree(root,0);
        //堆排序
        HeapSort(root,Q,n);
        return 0;
    }

    代码优化方法:
    不用完全二叉树,直接用舍弃0号单元数组存值,利用数组下标即可判断值在完全二叉树中的位置。

    展开全文
  • P36-4.9常用排序算法之堆排序 P37-4.10线索二叉树的概述 P38-4.11线索二叉树代码实现 1、TestThreadedBinaryTree.java 2、ThreadedBinaryTree.java 3、ThreadedNode.java P39-4.12线索二叉树的遍历

    学习地址:【数据结构与算法基础-java版】                  🚀数据结构--Java专栏🚀

    目   录

    P34-4.7顺序存储的二叉树的概述

    P35-4.8顺序存储的二叉树的遍历

    P36-4.9常用排序算法之堆排序

    P37-4.10线索二叉树的概述

    P38-4.11线索二叉树代码实现

    1、TestThreadedBinaryTree.java

    2、ThreadedBinaryTree.java

    3、ThreadedNode.java

    P39-4.12线索二叉树的遍历


    P34-4.7顺序存储的二叉树的概述

    二叉树数组的转换

    顺序存储的二叉树通常情况,只考虑完全二叉树

    第n个元素的左子节点是:2*n+1;
    第n个元素的右子节点是:2*n+2;
    第n个元素的父节点是:(n-1)/2;

    P35-4.8顺序存储的二叉树的遍历

    将 数组 看成 完全二叉树!以数组的方式遍历二叉树!

     

    因为 根节点的左子节点 也会有 左子节点,所以需要递归。

    P36-4.9常用排序算法之堆排序

    大顶堆:父节点永远大于子节点!数值大的 在 上面!

    大顶堆 是 从大到小,小顶堆 是 从小到大!

    升序排序 使用 大顶堆;降序排序 使用 小顶堆。

    package demo4;
    
    import java.util.Arrays;
    
    public class HeapSort {
    
    	public static void main(String[] args) {
    		int[] arr = new int[] { 9, 6, 8, 7, 0, 1, 10, 4, 2 };
    		heapSort(arr);
    		System.out.println(Arrays.toString(arr));
    	}
    
    	public static void heapSort(int[] arr) {
    		// 开始位置是最后一个非叶子节点,即最后一个节点的父节点
    		int start = (arr.length - 1) / 2;
    		// 调整为大顶堆
    		for (int i = start; i >= 0; i--) {
    			maxHeap(arr, arr.length, i);
    		}
    		// 先把数组中的第0个和堆中的最后一个数交换位置,再把前面的处理为大顶堆
    		for (int i = arr.length - 1; i > 0; i--) {
    			int temp = arr[0];
    			arr[0] = arr[i];
    			arr[i] = temp;
    			maxHeap(arr, i, 0);
    		}
    	}
    
    	public static void maxHeap(int[] arr, int size, int index) {
    		// 左子节点
    		int leftNode = 2 * index + 1;
    		// 右子节点
    		int rightNode = 2 * index + 2;
    		int max = index;
    		// 和两个子节点分别对比,找出最大的节点
    		if (leftNode < size && arr[leftNode] > arr[max]) {
    			max = leftNode;
    		}
    		if (rightNode < size && arr[rightNode] > arr[max]) {
    			max = rightNode;
    		}
    		// 交换位置
    		if (max != index) {
    			int temp = arr[index];
    			arr[index] = arr[max];
    			arr[max] = temp;
    			// 交换位置以后,可能会破坏之前排好的堆,所以,之前的排好的堆需要重新调整
    			maxHeap(arr, size, max);
    		}
    	}
    
    }

    P37-4.10线索二叉树的概述

    左右指针,如果没有存东西,则 可以 将 该节点的指针 指向 该节点的前一个节点 或 后一个节点。

    找一个标记 区分 左(右子树)、前(后节点)。

    线索化二叉树时,一个节点的一个节点,叫前驱节点;
    线索化二叉树时,一个节点的一个节点,叫后继节点。

    P38-4.11线索二叉树代码实现

    1、TestThreadedBinaryTree.java

    package demo7;
    
    public class TestThreadedBinaryTree {
    
    	public static void main(String[] args) {
    		// 创建一颗树
    		ThreadedBinaryTree binTree = new ThreadedBinaryTree();
    		// 创建一个根节点
    		ThreadedNode root = new ThreadedNode(1);
    		// 把根节点赋给树
    		binTree.setRoot(root);
    		// 创建一个左节点
    		ThreadedNode rootL = new ThreadedNode(2);
    		// 把新创建的节点设置为根节点的子节点
    		root.setLeftNode(rootL);
    		// 创建一个右节点
    		ThreadedNode rootR = new ThreadedNode(3);
    		// 把新创建的节点设置为根节点的子节点
    		root.setRightNode(rootR);
    		// 为第二层的左节点创建两个子节点
    		rootL.setLeftNode(new ThreadedNode(4));
    		
    		ThreadedNode fiveNode = new ThreadedNode(5);
    		
    		rootL.setRightNode(fiveNode);
    		// 为第二层的右节点创建两个子节点
    		rootR.setLeftNode(new ThreadedNode(6));
    		rootR.setRightNode(new ThreadedNode(7));
    		
    		// 中序遍历树
    		binTree.midShow();
    		System.out.println("\n===============");
    		
    		// 中序线索化二叉树
    		binTree.threadNodes();
    		ThreadedNode afterFive = fiveNode.rightNode;
    		System.out.println(afterFive.value);
    	}
    
    }

    2、ThreadedBinaryTree.java

    package demo7;
    
    public class ThreadedBinaryTree {
    
    	ThreadedNode root;
    
    	// 用于临时存储前驱节点
    	// 每次调用threadNodes()函数-临时节点都会改变
    	ThreadedNode pre = null;
    
    	// 遍历线索二叉树
    	public void threadIterate() {
    		// 用于临时存储当前遍历节点
    		ThreadedNode node = root;
    		while (node != null) {
    			// 循环找到最开始的节点
    			while (node.leftType == 0) {
    				node = node.leftNode;
    			}
    			// 打印当前节点的值
    			System.out.println(node.value);
    			// 如果当前节点的右指针指向的是后继节点,
    			// 可能后继节点还有后继节点、
    			while (node.rightType == 1) {
    				node = node.rightNode;
    				System.out.println(node.value);
    			}
    			// 替换遍历的节点
    			node = node.rightNode;
    		}
    	}
    
    	// 设置根节点
    	public void setRoot(ThreadedNode root) {
    		this.root = root;
    	}
    
    	// 中序线索化二叉树-递归遍历-节点
    	public void threadNodes() {
    		threadNodes(root);
    	}
    
    	// 中序线索化二叉树-递归遍历-根据root节点不断递归
    	public void threadNodes(ThreadedNode node) {
    		// 当前节点如果为null,直接返回
    		if (node == null) {
    			return;
    		}
    		// 处理左子树---左子树为空,指针指向前驱节点
    		threadNodes(node.leftNode);
    		// 处理前驱节点
    		if (node.leftNode == null) {
    			// 让当前节点的左指针指向前驱节点
    			node.leftNode = pre;
    			// 改变当前节点左指针的类型
    			node.leftType = 1;// 指向前驱节点
    		}
    		// 处理前驱的右指针,如果前驱节点的右指针是null(没有指向右子树)
    		if (pre != null && pre.rightNode == null) {
    			// 让前驱节点的右指针指向当前节点
    			pre.rightNode = node;
    			// 改变前驱节点的右指针类型
    			pre.rightType = 1;
    		}
    		// 每处理一个节点,当前节点是下一个节点的前驱节点
    		pre = node;
    		// 处理右子树
    		threadNodes(node.rightNode);
    	}
    
    	// 获取根节点
    	public ThreadedNode getRoot() {
    		return root;
    	}
    
    	// 前序遍历
    	public void frontShow() {
    		if (root != null) {
    			root.frontShow();
    		}
    	}
    
    	// 中序遍历
    	public void midShow() {
    		if (root != null) {
    			root.midShow();
    		}
    	}
    
    	// 后序遍历
    	public void afterShow() {
    		if (root != null) {
    			root.afterShow();
    		}
    	}
    
    	// 前序查找
    	public ThreadedNode frontSearch(int i) {
    		return root.frontSearch(i);
    	}
    
    	// 删除子树
    	public void delete(int i) {
    		if (root.value == i) {
    			root = null;
    		} else {
    			root.delete(i);
    		}
    	}
    
    }

    3、ThreadedNode.java

    package demo7;
    
    public class ThreadedNode {
    
    	int value;// 节点的权
    	ThreadedNode leftNode;// 左儿子
    	ThreadedNode rightNode;// 右儿子
    
    	// 标识指针类型-默认值为0,指向左右子树
    	int leftType;
    	int rightType;
    
    	public ThreadedNode(int value) {
    		this.value = value;
    	}
    
    	// 设置左儿子
    	public void setLeftNode(ThreadedNode leftNode) {
    		this.leftNode = leftNode;
    	}
    
    	// 设置右儿子
    	public void setRightNode(ThreadedNode rightNode) {
    		this.rightNode = rightNode;
    	}
    
    	// 前序遍历
    	public void frontShow() {
    		// 先遍历当前节点的内容
    		System.out.println(value);
    		// 左节点
    		if (leftNode != null) {
    			leftNode.frontShow();
    		}
    		// 右节点
    		if (rightNode != null) {
    			rightNode.frontShow();
    		}
    	}
    
    	// 中序遍历
    	public void midShow() {
    		// 左子节点
    		if (leftNode != null) {
    			leftNode.midShow();
    		}
    		// 当前节点
    		System.out.print(value + "、");
    		// 右子节点
    		if (rightNode != null) {
    			rightNode.midShow();
    		}
    	}
    
    	// 后序遍历
    	public void afterShow() {
    		// 左子节点
    		if (leftNode != null) {
    			leftNode.afterShow();
    		}
    		// 右子节点
    		if (rightNode != null) {
    			rightNode.afterShow();
    		}
    		// 当前节点
    		System.out.println(value);
    	}
    
    	// 前序查找
    	public ThreadedNode frontSearch(int i) {
    		ThreadedNode target = null;
    		// 对比当前节点的值
    		if (this.value == i) {
    			return this;
    			// 当前节点的值不是要查找的节点
    		} else {
    			// 查找左儿子
    			if (leftNode != null) {
    				// 有可能可以查到,也可以查不到,查不到的话,target还是一个null
    				target = leftNode.frontSearch(i);
    			}
    			// 如果不为空,说明在左儿子中已经找到
    			if (target != null) {
    				return target;
    			}
    			// 查找右儿子
    			if (rightNode != null) {
    				target = rightNode.frontSearch(i);
    			}
    		}
    		return target;
    	}
    
    	// 删除一个子树
    	public void delete(int i) {
    		ThreadedNode parent = this;
    		// 判断左儿子
    		if (parent.leftNode != null && parent.leftNode.value == i) {
    			parent.leftNode = null;
    			return;
    		}
    		// 判断右儿子
    		if (parent.rightNode != null && parent.rightNode.value == i) {
    			parent.rightNode = null;
    			return;
    		}
    
    		// 递归检查并删除左儿子
    		parent = leftNode;
    		if (parent != null) {
    			parent.delete(i);
    		}
    
    		// 递归检查并删除右儿子
    		parent = rightNode;
    		if (parent != null) {
    			parent.delete(i);
    		}
    	}
    
    }

    P39-4.12线索二叉树的遍历

    不需要 使用 递归!!!

    展开全文
  • 完全二叉树 1、定义:对树中结点从上到下从左到右顺序进行编号,且编号为i的结点与完美二叉树中编号为i的结点在二叉树中位置相同。 2、完全二叉树的特点: (1) 叶结点只能出现在下层和次下层且最下层的叶子...
  • 完全二叉树堆排序

    千次阅读 2013-04-09 09:48:23
    堆排序算法复杂度虽然也是O(nlgn),但其常数因子较大,而且在实际测试中发现和快速排序、二路归并排序相比速度会慢不少,但堆有其独特的优势: (1) 堆排序仅需要O(1)的空间,这是其他O(nlgn) 排序算法所没有的特点...
  • 堆排序二叉树

    2019-03-24 16:28:29
    闲来无事,在网上看了一两个算法,感觉涨见识了,一个是快速排序,一个是堆排序。快速排序很好理解,看完感觉到了算法的魅力,然后是堆排序,我简单看了下的时候,感觉也很有魅力,但是之间的步骤的来由有点迷糊,...
  • 堆排序 二叉树排序 关键路径 Dijkstra算法,C语言,已实现
  • 八大排序算法 之 堆排序二叉树排序)

    万次阅读 多人点赞 2016-05-07 10:03:43
    2,堆排序是对普通选择排序的一种优化:如果是一个稳定堆,每次在选择最大值时,只用沿着二叉树其中一个分叉去交换即可,其他分叉符合堆得特性(因是排好的稳定堆),可以看作是稳定的,不用重排交换,省去了
  • 堆排序 由于本人过于懒惰, 文字性描述之后再更新 public static void heapSort(int[] arr) { if (arr == null || arr.length &amp;amp;amp;amp;amp;amp;amp;lt; 2) { return; } for (int i = 0; i &...
  • 二叉树堆排序

    千次阅读 多人点赞 2016-11-12 23:26:14
    堆排序
  • 二叉树学习之堆排序

    千次阅读 2014-11-04 15:32:36
    认识堆是从堆排序开始的 二叉堆是完全二叉树或者是近似完全二叉树,堆存储在数组中: 根结点下标为0时,下标为n的元素的子结点下标分别为2*n+1,2*n+2,其父结点下标为(n-1)/2 二叉堆的特性: 1、父结点的键值总是>=...
  • //自底向上完全二叉树 父节点的关键值大于等于子节点关键值 void fixUp(Item a[],int k){ //k表示破坏规则的位置 while(k>1 && a[k/2].data [k].data){ swap(a[k],a[k/2]); k = k/2; } } //自顶向下...
  • 主要介绍了java 实现最小二叉树堆排序的实例的相关资料,希望通过本文能帮助到大家,需要的朋友可以参考下
  • 是一个数组A, 它可以被看成一个近似的完全二叉树 以(a)二叉树和(b)数组形式展现的是一个最大. 结点上方的数字是它在数组中相应的下标. 若一个结点下标为iii, 可以得到它的父结点, 左孩子和右孩子的下标: ...
  • 主要介绍了Python实现基于二叉树存储结构的堆排序算法,结合实例形式分析了Python二叉树的定义、遍历及堆排序算法相关实现技巧,需要的朋友可以参考下
  • 》》堆排序是一种树形选择排序方法,它的特点是:在排序过程中,将 L[1...n]看成是一棵完全二叉树 的顺序存储结构,利用完全二叉树中双亲结点和孩子结点之间的内在关系,在当前无序区中选择关 键字最大(或最小...
  • 二叉树堆排序

    千次阅读 2014-12-16 11:16:05
    二叉树常被用作二叉查找树和二叉或是二叉排序树。二叉树的每个结点至多只有二棵子树(不存在出度大于2的结点),二叉树的子树有左右之分,次序不能颠倒。 二、二叉树的性质 二叉树具有以下重
  • 完全二叉树

    千次阅读 2018-10-28 22:52:47
    这是从最小生成树过来的,其中提到了大根,以前学的内容忘的一干二净,写博客不知道从哪里写,还是先把基础码一下。 参考了课本和三篇博文: 第一篇的排版引起极度不适,并且名词很多,顺了一遍之后看着舒坦了...
  • 二叉树堆排序

    2018-04-13 14:03:00
    树与二叉树简介: 树是一种数据结构,比如目录结构,树是一种可以递归定义的数据结构 树是由n个节点组成的集合,如果n=0,那么这是一颗空树,如果n>0,那存在一个节点作为树的根节点,其他节点可以分为m个子树...
  • 堆排序算法(图解详细流程)

    万次阅读 多人点赞 2018-08-04 11:21:17
    堆排序的时间复杂度O(N*logN),额外空间复杂度O(1),是一个不...堆的结构可以分为大根堆和小根堆,是一个完全二叉树,而堆排序是根据堆的这种数据结构设计的一种排序,下面先来看看什么是大根堆和小根堆 1.1 大根...
  • js代码-堆排序(将比较结果保存下来) 完全二叉树 双亲节点 i / 2 双亲子女的关系: 2i 和 2i + 1

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 67,840
精华内容 27,136
关键字:

堆排序是完全二叉树吗