数据结构与算法 树

引言

1. 顺序查找

​ 哨兵的方式

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)

2. 二分查找

   查找树的形式

   我们需要按照从小到大顺序排序

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);
            }
        }
        
    }