数据结构与算法 树
引言
- 顺序查找
哨兵的方式
public int findValueIndex(Element k,Element[] data)
{
list[0]=k;//设置哨兵
if(int i=data.size()-1;k!=list[i];i--)
return i;//如果返回0，则没有查找到
}
时间复杂度为O(N)
-
二分查找
查找树的形式
我们需要按照从小到大顺序排序
public int findValueIndex(Element[] data,Element k){
int left;
int right;
int mid;
left=0;
right=data.size()-1;
while(left<=right)
{
mid=(left+right)/2;
if(data[mid]<k)//如果中心小于查找值，则k应该在mid到right中间
{
left=mid+1;
}else if(data[mid]>k){//如果中心大于于查找值，则k应该在mid到left中间
right=mid-1;
}else{
return mid;
}
}
return -1;
}
从二分查找中我们可以画出一个树的结构，这个就是查找树。
定义
什么是树？
对于树的定义是n个节点的集合，对于n=0则为空树，如果n>1,则有以下特征
1. 树有个特殊的结点，我们叫做根节点
2. 其余节点可分为m个互不相交的集合，每个集合又是个树，它们是原来树的子树。
3. 子树是互不相交的
4. 每个节点只有一个父节点
5. N个节点则有N-1条边
特殊的树
二叉树
所有的节点都最多只有两个子节点的树，我们称之为二叉树。
1.完美二叉树，深度为n的二叉树，1到n-1层的节点只有两个子节点，n层都是叶节点，则称为完美二叉树。
2.设二叉树的深度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树。
二叉树的性质
n0 n1 n2，分别代表，0个子节点，1个子节点，2个子节点。
1. 每层的最大节点数为2^(k-1),树的最大节点数为2^k-1
2. 我们知道二叉树的边是 0*n0+1*n1+2*n2或则等于n0+n1+n2-1则我们可以推算出2n2=n0+n2-1
则no=n2+1；也就是说二叉树的的叶节点数的等于两个子节点的节点＋1。
遍历
先序遍历
public void printAll(Tree tree)//递归调用
{
if(tree!=null)
{
print tree.Value;//先序
printAll(tree.left);
printAll(tree.right);
}
}
public void printAll(Tree rootTree，Stack stack)//堆栈
{
if(rootTree!=null){
Tree t=rootTree;
stack.push(t);
while((t=stack.pop())!=null)
{
print t.value;
if(t.right!=null)
{
stack.push(t.right);
}
if(t.left!=null)
{
stack.push(t.left);
}
}
}
}
中序遍历
public void printAll(Tree tree)//递归调用
{
if(tree!=null)
{
printAll(tree.left);
print tree.Value;//中序
printAll(tree.right);
}
}
//首先要将节点的左子节点压入栈中，循环压入，当最后一个压入的节点没有左子节点时，则退出压入循环，然后开始弹出节点，并将右子节点作为一个新的节点，开始新的一轮大循环
public void printMidAll(Tree rootTree, Stack<Tree> stack) {
Tree tree=rootTree;
while(tree!=null||!stack.isEmpty())
{
while (tree!=null) {
// System.out.println(tree.value);
stack.push(tree);
tree=tree.left;
}
if (!stack.isEmpty()) {
tree=stack.pop();
System.out.println(tree.value);//中序
tree=tree.right;
}
}
后序遍历
public void printAll(Tree tree)//递归调用
{
if(tree!=null)
{
printAll(tree.left);
printAll(tree.right);
print tree.Value;//后序
}
}
层序遍历
public void printByFloor(Tree rootTree,Queue<Tree> queue){
queue.add(rootTree);
while (!queue.isEmpty()) {
Tree tree=queue.poll();
System.out.println(tree.value);
if (tree.left!=null) {
queue.add(tree.left);
}
if (tree.right!=null) {
queue.add(tree.right);
}
}
}
