常见数据结构之二叉树

这就是一颗二叉树，假设binarytree[i]是二叉树的一个节点，那么它的左孩子节点 leftchild = binarytree[i*2+1]那么相应的右孩子节点 rightchild = binarytree[i*2+2]。这里可能会有的一个问题是：b有左右两个子节点分别为d和e，为什么右旋的时候要将右子节点e拿到a的左子节点而不是b的左子节点d。二叉树中的节点不是必须有两个子节点，它可以只有一个左子节点 或 一个 右子节点 ， 或者干脆没有子节点（这种情况也叫叶节点，像现实叶子一样，不能再产生分支了。

  二叉树的每个结点至多只有二棵子树(不存在度大于2的结点)，二叉树的子树有左右之分，次序不能颠倒。二叉树的第i层至多有2{i-1}个结点；深度为k的二叉树至多有2k-1个结点；对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1。

  满二叉树：一棵深度为k，且有2k-1个节点称之为满二叉树；

  完全二叉树：深度为k，有n个节点的二叉树，当且仅当其每一个节点都与深度为k的满二叉树中，序号为1至n的节点对应时，称之为完全二叉树。

  平衡二叉树：平衡二叉树又被称为AVL树（区别于AVL算法），它是一棵二叉排序树，且具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

二叉树.jpg

//先序遍历  
   public void theFirstTraversal(Node root) {  
        printNode(root);  
        if (root.getLeftNode() != null) {  //使用递归进行遍历左孩子  
            theFirstTraversal(root.getLeftNode());  
        }  
        if (root.getRightNode() != null) {  //递归遍历右孩子  
            theFirstTraversal(root.getRightNode());  
        }  
    }  
//中序遍历  
    public void theInOrderTraversal(Node root) { 
        if (root.getLeftNode() != null) {  
            theInOrderTraversal(root.getLeftNode());  
        }  
        printNode(root);  
        if (root.getRightNode() != null) {  
            theInOrderTraversal(root.getRightNode());  
        }  
    }
//后序遍历  
    public void thePostOrderTraversal(Node root) {  //后序遍历  
        if (root.getLeftNode() != null) {  
            thePostOrderTraversal(root.getLeftNode());  
        }  
        if(root.getRightNode() != null) {  
            thePostOrderTraversal(root.getRightNode());  
        }  
        printNode(root);  
    } 
//层次遍历
  public void levelIterator(BiTree root)  
  {  
      if(root == null)  
      {  
          return ;  
      }  
      LinkedList<BiTree> queue = new LinkedList<BiTree>();  
      BiTree current = null;  
      queue.offer(root);//将根节点入队  
      while(!queue.isEmpty())  
      {  
          current = queue.poll();//出队队头元素并访问  
          System.out.print(current.val +"-->");  
          if(current.left != null)//如果当前节点的左节点不为空入队  
          {  
              queue.offer(current.left);  
          }  
          if(current.right != null)//如果当前节点的右节点不为空，把右节点入队  
          {  
              queue.offer(current.right);  
          }  
      }  
        
  } 

二叉排序树的深度 b．二叉排序树的结点的个数c．被查找结点的度 d．二叉排序树的存储结构(19)在具有 n 个结点的二叉排序树中查找一个结点的过程的时间复杂度约为&mdash。常见的综合应用题考点包括：二叉树的遍历算法，遍历基础上针对二叉树的一些统计和操作(比如结点数统计、左右子树对换等等)，判断某棵二叉树是否二叉排序树，以上这些都要求能用递归的和非递归的算法解决，特别要重视非递归的算法，线索化后二叉树的遍历算法，如查找某结点线索化后的前驱或后继结点的算法以及给出huffman编码等等。我们知道在生成二叉树的过程是非常容易失衡的，最坏的情况就是一边倒（只有右/左子树），这样势必会导致二叉树的检索效率大大降低（o(n)），所以为了维持二叉树的平衡，大牛们提出了各种实现的算法，如：avl，sbt，伸展树，treap ，红黑树等等。

二叉排序树或者是一棵空树，或者是具有下列性质的二叉树：

  （1）若左子树不空二叉排序树 数据结构，则左子树上所有结点的值均小于或等于它的根结点的值；

  （2）若右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值；

  （3）左、右子树也分别为二叉排序树；

二叉排序树.gif

  （1）若根结点的关键字值等于查找的关键字，成功。

  （2）否则，若小于根结点的关键字值，递归查左子树。

  （3）若大于根结点的关键字值，递归查右子树。

  （4）若子树为空，查找不成功。

  （1）首先执行查找算法，找出被插结点的父亲结点。

  （2）判断被插结点是其父亲结点的左、右儿子。将被插结点作为叶子结点插入。

  （3）若二叉树为空。则首先单独生成根结点。

注意：新插入的结点总是叶子结点。

在二叉排序树删去一个结点，分三种情况讨论：

供选择的答案： a：①是特殊的树②不是树的特殊形式③是两棵树的总称④是只有二个根结点的树形结构 b：①左子结点②右子结点③左子结点或者没有右子结点 ④兄弟 c～d： ①最左子结点②最右子结点③最邻近的右兄弟④最邻近的左兄弟⑤最左的兄弟⑥最右的兄弟e：①o(n)②o(n)③o(log2n)④o(log2n) 15、每一棵树都能唯一地转换为它所对应的二叉树，树的这种二叉树表示对树的运算带来很大的好处。4．译码的思想是循环读入一串哈夫曼序列，读到“0”从根结点的左孩子继续读，读到“1”从右孩子继续，如果读到一个结点的左孩子和右孩子是否都为0，如果是说明已经读到了一个叶子（字符），翻译一个字符成功，把该叶子结点代表的字符存在一个存储翻译字符的数组中，然后继续从根结点开始读，直到读完这串哈夫曼序列，遇到结束符便退出翻译循环。用链式存储结构来表示二叉树，一个结点至少由3个域组成，即数据域、左子结点域和右子结点域（如图1所示）。

  2.若p结点只有左子树PL或右子树PR，此时只要令PL或PR直接成为其双亲结点f的左子树（当p是左子树）或右子树（当p是右子树）即可，作此修改也不破坏二叉排序树的特性。

(1) a、根结点无左子树的二叉树 b、根结点无右子树的二叉树c、只有根结点的二叉树或非叶子结点只有左子树的二叉树d、只有根结点的二叉树或非叶子结点只有右子树的二叉树(2) a、非叶子结点只有左子树的二叉树 b、只有根结点的二叉树 c、根结点无右子树的二叉树 d、非叶子结点只有右子树的二叉树 10、 假设一棵二叉树的后序遍历序列为 dgjhebifca，中序遍历序列为 dbgehjacif，则其前序遍历序列为 (10) 。 供选择的答案： a：①是特殊的树②不是树的特殊形式③是两棵树的总称④是只有二个根结点的树形结构 b：①左子结点②右子结点③左子结点或者没有右子结点 ④兄弟 c～d： ①最左子结点②最右子结点③最邻近的右兄弟④最邻近的左兄弟⑤最左的兄弟⑥最右的兄弟e：①o(n)②o(n)③o(log2n)④o(log2n) 15、每一棵树都能唯一地转换为它所对应的二叉树，树的这种二叉树表示对树的运算带来很大的好处。某一t结点a的左结点中必会包含比a结点中最 小元素小的最大元素，而a结点的右结点中必会包含比a结点中最大元素大的最小元素。

  其一是令p的左子树为f的左/右(依p是f的左子树还是右子树而定)子树，s为p左子树的最右下的结点，而p的右子树为s的右子树；

  其二是令p的直接前驱（或直接后继）替代p，然后再从二叉排序树中删去它的直接前驱（或直接后继）－即让f的左子树(如果有的话)成为p左子树的最左下结点(如果有的话)，再让f成为p的左右结点的父结点。

private void deleteNode(BinarySortTree p){
    //TODOAuto-generatedmethodstub
    if(p!=null)
    {
        //如果结点有左子树
        /*1。若p有左子树，找到其左子树的最右边的叶子结点r，用该叶子结点r来替代p，把r的左孩子
        作为r的父亲的右孩子。
        2。若p没有左子树，直接用p的右孩子取代它。
        */
        if(p.lChild!=null)
        {
            BinarySortTree r=p.lChild;
            BinarySortTree prev=p.lChild;
                while(r.rChild!=null)
               {
                    prev=r;
                    r=r.rChild;
                }
                p.data=r.data;
            //若r不是p的左子树,p的左子树不变，r的左子树作为r的父结点的右孩子结点
            if(prev!=r)
            {
                prev.rChild=r.lChild;
             }
            else
            {
             //若r是p的左子树，则p的左子树指向r的左子树
            p.lChild=r.lChild;
            }
        }
        else
        {
            p=p.rChild;
        }
    }
}

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-107068-1.html