2016.10.05
快速排序(Quicksort)是对冒泡排序的一种改进。
设要排序的数组是A[0]……A[N-1],首先任意选取一个数据(通常选用数组的第一个数)作为关键数据,然后将所有比它小的数都放到它前面,所有比它大的数都放到它后面,这个过程称为一趟快速排序。值得注意的是,快速排序不是一种稳定的排序算法,也就是说,多个相同的值的相对位置也许会在算法结束时产生变动。
一趟快速排序的算法是:
1)设置两个变量i、j,排序开始的时候:i=0,j=N-1;
2)以第一个数组元素作为关键数据,赋值给key,即key=A[0];
3)从j开始向前搜索,即由后开始向前搜索(j--),找到第一个小于key的值A[j],将A[j]和A[i]互换;
4)从i开始向后搜索,即由前开始向后搜索(i++),找到第一个大于key的A[i],将A[i]和A[j]互换;
5)重复第3、4步,直到i=j; (3,4步中,没找到符合条件的值,即3中A[j]不小于key,4中A[i]不大于key的时候改变j、i的值,使得j=j-1,i=i+1,直至找到为止。找到符合条件的值,进行交换的时候i, j指针位置不变。另外,i==j这一过程一定正好是i+或j-完成的时候,此时令循环结束)。
如图:
class Quick { public void sort(int arr[],int low,int high) { int l=low; int h=high; int povit=arr[low]; while(l<h) { while(l<h&&arr[h]>=povit) h--; if(l<h){ int temp=arr[h]; arr[h]=arr[l]; arr[l]=temp; l++; } while(l<h&&arr[l]<=povit) l++; if(l<h){ int temp=arr[h]; arr[h]=arr[l]; arr[l]=temp; h--; } } print(arr); System.out.print("l="+(l+1)+"h="+(h+1)+"povit="+povit+"\n"); if(l>low)sort(arr,low,l-1); if(h<high)sort(arr,l+1,high); } }面试题:二叉树的深度
题目:输入一课二叉数的根节点,求该数的深度。从根节点到叶子结点一次经过的结点形成的一条路径,最长路径的长度为树的深度。根结点的深度为1.
解体思路:
1.如果根节点为空,则深度为0,返回0,递归的出口
2.如果根节点不为空,那么深度至少为1,然后我们求他们左右子树的深度,
3.比较左右子树深度值,返回较大的那一个
4.通过递归调用
代码实现:
#include<iostream>
#include<stdlib.h>
using namespace std;
struct BinaryTreeNode
{
int m_nValue;
BinaryTreeNode* m_pLeft;
BinaryTreeNode* m_pRight;
};
//创建二叉树结点
BinaryTreeNode* CreateBinaryTreeNode(int value)
{
BinaryTreeNode* pNode=new BinaryTreeNode();
pNode->m_nValue=value;
pNode->m_pLeft=NULL;
pNode->m_pRight=NULL;
return pNode;
}
//连接二叉树结点
void ConnectTreeNodes(BinaryTreeNode* pParent,BinaryTreeNode* pLeft,BinaryTreeNode* pRight)
{
if(pParent!=NULL)
{
pParent->m_pLeft=pLeft;
pParent->m_pRight=pRight;
}
}
//求二叉树深度
int TreeDepth(BinaryTreeNode* pRoot)//计算二叉树深度
{
if(pRoot==NULL)//如果pRoot为NULL,则深度为0,这也是递归的返回条件
return 0;
//如果pRoot不为NULL,那么深度至少为1,所以left和right=1
int left=1;
int right=1;
left+=TreeDepth(pRoot->m_pLeft);//求出左子树的深度
right+=TreeDepth(pRoot->m_pRight);//求出右子树深度
return left>right?left:right;//返回深度较大的那一个
}
void main()
{
// 1
// / \
// 2 3
// /\ \
// 4 5 6
// /
// 7
//创建树结点
BinaryTreeNode* pNode1 = CreateBinaryTreeNode(1);
BinaryTreeNode* pNode2 = CreateBinaryTreeNode(2);
BinaryTreeNode* pNode3 = CreateBinaryTreeNode(3);
BinaryTreeNode* pNode4 = CreateBinaryTreeNode(4);
BinaryTreeNode* pNode5 = CreateBinaryTreeNode(5);
BinaryTreeNode* pNode6 = CreateBinaryTreeNode(6);
BinaryTreeNode* pNode7 = CreateBinaryTreeNode(7);
//连接树结点
ConnectTreeNodes(pNode1, pNode2, pNode3);
ConnectTreeNodes(pNode2, pNode4, pNode5);
ConnectTreeNodes(pNode3, NULL, pNode6);
ConnectTreeNodes(pNode5, pNode7, NULL );
int depth=TreeDepth(pNode1);
cout<<depth<<endl;
system("pause");
}
相关推荐
求二叉树最大宽度 数据结构 求二叉树最大宽度 数据结构
数据结构中求二叉树的高度和宽度C++代码,比较适合初学者
二叉树的高度和宽度,有详细注释,数据结构课设时做的。
解决二叉树初始化,宽度,高度,最大节点,是否为完全二叉树的判断
武汉理工大学数据结构课程设计计算二叉树的宽度
二叉树高度 二叉树高度 二叉树高度 二叉树高度 二叉树高度
二叉树的建立,前序、中序、后序、层序遍历,求二叉树的宽度
以二叉链表作存储结构,设计求二叉树高度的算法。
二叉树的创建遍历以及求二叉树的高度程序源码 先序创建 前序遍历 树的层次
设二叉树的宽度定义为具有结点数最多的那一层上的结点个数。试设计算法求二叉树的宽度,并输出各结点的高度。(与另一份源码不同)
设二叉树的宽度定义为具有结点数最多的那一层上的结点个数。试设计算法求二叉树的宽度,并输出各结点的高度。(包含提高)
对于二叉树的基本的运算,查找孩子结点,查看叶子节点到根节点的路径~ 二叉树的宽度。
这个二叉树与满二叉树(full binary tree)结构相同,但一些节点为空。 每一层的宽度被定义为两个端点(该层最左和最右的非空节点,两端点间的null节点也计入长度)之间的长度。 示例 1: 输入: 1 / \ 3 2 / \ \ ...
主要介绍了C语言中计算二叉树的宽度的两种方式的相关资料,需要的朋友可以参考下
(1)输入字符序列,建立二叉链表 (2)中序遍历二叉树:递归 (3)中序遍历二叉树:非递归 (3)二叉树高度
二叉树遍历问题二叉树遍历问题二叉树遍历问题二叉树遍历问题二叉树遍历问题二叉树遍历问题二叉树遍历问题二叉树遍历问题二叉树遍历问题二叉树遍历问题二叉树遍历问题二叉树遍历问题二叉树遍历问题二叉树遍历问题...
求二叉树的高度。。。。。。。。。。。。。。。。。。。。。。。。。。。
每棵子树又都是二叉树,所以构造一棵子树的过程与构造整棵二叉树的过程完全相同(采用递归形式直到叶子结点为止)。 2) 先序序列的输入:从键盘输入任意一棵二叉树的先序序列,用#代表空指针,如下图所示的二叉树,...
根据给定的二叉树,求二叉树的高度;求给定结点的所有祖先。 要求:(1)根据性质5 建立二叉树的二叉链表; (2)遍历算法必须采用非递归算法。
支持输入空节点,统计输入的二叉树的高度。