`

二叉树及其遍历

    博客分类:
  • java
 
阅读更多

转自:http://www.iteye.com/topic/561141

一、数据结构分类

(一)按逻辑结构

  1. 集合(无辑关系)
  2. 线性结构(线性表):数组、链表、栈、队列
  3. 非线性结构:树、图、多维数组

(二)按存储结构

顺序(数组)储结构、链式储结构、索引储结构、散列储结构

二、二叉树相关性质

  • 结点的度:一个结点的子树的个数记为该结点的度.
  • 树的度:所有节点中度数最大的结节的度数,叶子节点的度为零。
  • 树的高度:一棵树的最大层次数记为树的高度(或深度)。
  • 有序(无序)树:若将树中结点的各子树看成是从左到右具有次序的,即不能交换,则称该树为有序树。否则称为无序树。
  • 二叉树第i层(i≥1)上至多有2^(i-1)个节点。
  • 深度为k的二叉树至多有2^k-1个节点(k≥1)。
  • 对任何一棵二叉,若叶子节点数为n0,度为2的节点数为n2,则n0=n2+1。
  • 具有n个节点的完全二叉树的深度为 (㏒2^n)(向下取整)+1。
  • 对一棵有n个节点的完全二叉树的节点按层次从上到下,自左至右进行编号,则对任一节点 i(1≤i≤n)有:若 i=1,则节点i是二叉树的根,无双亲;若 i>1,则其双亲为 i/2(向下取整)。若2i>n,则节点i没有孩子节点,否则其左孩子为2i。若2i+1>n,则节点i没有右孩子,否则其右孩子为 2i+1。
  • 若深度为k的二叉树有2^k-1个节点,则称其为满二叉树。满二叉树是一棵完全二叉树。

  • 对于完全二叉树中,度为1的节点个数只可能为1个或0个。
  • 对于二叉树,如果叶子节点数为n0,度为1的节点数为n1,度为2的节点数为n2,则节点总数n = n0 + n1 + n2。
  • 对于任意树,总节点数 = 每个节点度数和 + 1
  • 二叉树的高度等于根与最远叶节点(具有最多祖先的节点)之间分支数目。空树的高度是-1。只有单个元素的二叉树,其高度为0。

.

三、二叉树的遍历

遍历是按某种策略访问树中的每个节点,且仅访问一次。

(一) 二叉树结构实现

Java代码  收藏代码
  1. package  tree.bintree;  
  2.   
  3. /**  
  4.  * 创建 非完全二叉树、完全二叉树、满二叉树  
  5.  *  
  6.  * 由于二叉树的节点增加没有什么规则,所以这里只是简单的使用了递一  
  7.  * 次性把整棵树创建出来,而没有设计出一个一个添加节点的方法与删除  
  8.  *   
  9.  * @author jzj  
  10.  * @date 2009-12-23  
  11.  */   
  12. public   class  BinTree { // Bin=Binary(二进位的, 二元的)   
  13.   
  14.     protected  Entry root; //根   
  15.     private   int  size; //树的节点数   
  16.   
  17.     /**  
  18.      * 树的节点结构  
  19.      * @author jzj  
  20.      * @date 2009-12-23  
  21.      */   
  22.     protected   static   class  Entry {  
  23.         int  elem; //数据域,这里我们作为编号   
  24.         Entry left;//左子树   
  25.         Entry right;//右子树   
  26.   
  27.         public  Entry( int  elem) {  
  28.             this .elem = elem;  
  29.         }  
  30.   
  31.         public  String toString() {  
  32.             return   " number="  + elem;  
  33.         }  
  34.     }  
  35.   
  36.     /**  
  37.      * 根据给定的节点数创建一个完全二叉树或是满二叉树  
  38.      * @param nodeCount 要创建节点总数  
  39.      */   
  40.     public   void  createFullBiTree( int  nodeCount) {  
  41.         root = recurCreateFullBiTree(1 , nodeCount);  
  42.     }  
  43.   
  44.     /**  
  45.      * 递归创建完全二叉树  
  46.      * @param num 节点编号  
  47.      * @param nodeCount 节点总数  
  48.      * @return TreeNode 返回创建的节点  
  49.      */   
  50.     private  Entry recurCreateFullBiTree( int  num,  int  nodeCount) {  
  51.         size++;  
  52.         Entry rootNode = new  Entry(num); //根节点   
  53.         //如果有左子树则创建左子树   
  54.         if  (num *  2  <= nodeCount) {  
  55.             rootNode.left = recurCreateFullBiTree(num * 2 , nodeCount);  
  56.             //如果还可以创建右子树,则创建   
  57.             if  (num *  2  +  1  <= nodeCount) {  
  58.                 rootNode.right = recurCreateFullBiTree(num * 2  +  1 , nodeCount);  
  59.             }  
  60.         }  
  61.         return  (Entry) rootNode;  
  62.     }  
  63.   
  64.     /**  
  65.      * 根据给定的数组创建一棵树,这个棵树可以是完全二叉树也可是普通二叉树  
  66.      * 数组中为0的表示不创建该位置上的节点  
  67.      * @param nums 数组中指定了要创建的节点的编号,如果为0,表示不创建  
  68.      */   
  69.     public   void  createBinTree( int [] nums) {  
  70.         root = recurCreateBinTree(nums, 0 );  
  71.     }  
  72.   
  73.     /**  
  74.      * 递归创建二叉树  
  75.      * @param nums 数组中指定了要创建的节点的编号,如果为0,表示不创建  
  76.      * @param index 需要使用数组中的哪个元素创建节点,如果为元素为0,则不创建  
  77.      * @return TreeNode 返回创建的节点,最终会返回树的根节点  
  78.      */   
  79.     private  Entry recurCreateBinTree( int [] nums,  int  index) {  
  80.         //指定索引上的编号不为零上才需创建节点   
  81.         if  (nums[index] !=  0 ) {  
  82.             size++;  
  83.             Entry rootNode = new  Entry(nums[index]); //根节点   
  84.             //如果有左子树则创建左子树   
  85.             if  ((index +  1 ) *  2  <= nums.length) {  
  86.                 rootNode.left = (Entry) recurCreateBinTree(nums, (index + 1 ) *  2  -  1 );  
  87.                 //如果还可以创建右子树,则创建   
  88.                 if  ((index +  1 ) *  2  +  1  <= nums.length) {  
  89.                     rootNode.right = (Entry) recurCreateBinTree(nums, (index + 1 ) *  2 );  
  90.                 }  
  91.             }  
  92.             return  (Entry) rootNode;  
  93.         }  
  94.         return   null ;  
  95.   
  96.     }  
  97.   
  98.     public   int  size() {  
  99.         return  size;  
  100.     }  
  101.   
  102.     //取树的最左边的节点   
  103.     public   int  getLast() {  
  104.         Entry e = root;  
  105.         while  (e.right !=  null ) {  
  106.             e = e.right;  
  107.         }  
  108.         return  e.elem;  
  109.     }  
  110.   
  111.     //测试   
  112.     public   static   void  main(String[] args) {  
  113.   
  114.         //创建一个满二叉树   
  115.         BinTree binTree = new  BinTree();  
  116.         binTree.createFullBiTree(15 );  
  117.         System.out.println(binTree.size());//15   
  118.         System.out.println(binTree.getLast());//15   
  119.   
  120.         //创建一个完全二叉树   
  121.         binTree = new  BinTree();  
  122.         binTree.createFullBiTree(14 );  
  123.         System.out.println(binTree.size());//14   
  124.         System.out.println(binTree.getLast());//7   
  125.   
  126.         //创建一棵非完全二叉树   
  127.         binTree = new  BinTree();  
  128.         int [] nums =  new   int [] {  1 2 3 4 0 0 5 0 6 0 0 0 0 7 8  };  
  129.         binTree.createBinTree(nums);  
  130.         System.out.println(binTree.size());//8   
  131.         System.out.println(binTree.getLast());//8   
  132.   
  133.     }  
  134. }   

(二)利用二叉树本身特点进行递归遍历(属内部遍历)

由于二叉树所具有的递归性质,一棵非空的二叉树可以看作是由根节点、左子树和右 子树3部分构成,因为若能依次遍历这3部分的信息,也就遍历了整个二叉树。按照左子树的遍历在右子树的遍历之前进行的约定,根据访问根节点位置的不同,可 以得到二叉的前序、中序、后序3种遍历方法。

Java代码  收藏代码
  1. package  tree.bintree;  
  2.   
  3. /**  
  4.  * 二叉树的三种 内部 遍历:前序、中序、后序  
  5.  * 但不管是哪种方式,左子树的遍历在右子树的遍历之前遍历是这有三种遍历方式都  
  6.  * 必须遵循的约定  
  7.  * @author jzj  
  8.  * @date 2009-12-23  
  9.  */   
  10. public   class  BinTreeInOrder  extends  BinTree {  
  11.   
  12.     /**  
  13.      * 节点访问者,可根据需要重写visit方法  
  14.      */   
  15.     static   abstract   class  Visitor {  
  16.         void  visit(Object ele) {  
  17.             System.out.print(ele + " " );  
  18.         }  
  19.     }  
  20.   
  21.     public   void  preOrder(Visitor v) {  
  22.         preOrder(v, root);  
  23.     }  
  24.   
  25.     /**  
  26.      * 树的前序递归遍历 pre=prefix(前缀)  
  27.      * @param node 要遍历的节点  
  28.      */   
  29.     private   void  preOrder(Visitor v, Entry node) {  
  30.         //如果传进来的节点不为空,则遍历,注,叶子节点的子节点为null   
  31.         if  (node !=  null ) {  
  32.             v.visit(node.elem);//先遍历父节点   
  33.             preOrder(v, node.left);//再遍历左节点   
  34.             preOrder(v, node.right);//最后遍历右节点   
  35.         }  
  36.     }  
  37.   
  38.     public   void  inOrder(Visitor v) {  
  39.         inOrder(v, root);  
  40.     }  
  41.   
  42.     /**  
  43.      * 树的中序递归遍历 in=infix(中缀)  
  44.      * @param node 要遍历的节点  
  45.      */   
  46.     private   void  inOrder(Visitor v, Entry node) {  
  47.         //如果传进来的节点不为空,则遍历,注,叶子节点的子节点为null   
  48.         if  (node !=  null ) {  
  49.             inOrder(v, node.left);//先遍历左节点   
  50.             v.visit(node.elem);//再遍历父节点   
  51.             inOrder(v, node.right);//最后遍历右节点   
  52.         }  
  53.     }  
  54.   
  55.     public   void  postOrder(Visitor v) {  
  56.         postOrder(v, root);  
  57.     }  
  58.   
  59.     /**  
  60.      * 树的后序递归遍历 post=postfix(后缀)  
  61.      * @param node 要遍历的节点  
  62.      */   
  63.     private   void  postOrder(Visitor v, Entry node) {  
  64.         //如果传进来的节点不为空,则遍历,注,叶子节点的子节点为null   
  65.         if  (node !=  null ) {  
  66.             postOrder(v, node.left);//先遍历左节点   
  67.             postOrder(v, node.right);//再遍历右节点   
  68.             v.visit(node.elem);//最后遍历父节点   
  69.         }  
  70.     }  
  71.   
  72.     //测试   
  73.     public   static   void  main(String[] args) {  
  74.   
  75.         //创建二叉树   
  76.         int [] nums =  new   int [] {  1 2 3 4 0 0 5 0 6 0 0 0 0 7 8  };  
  77.         BinTreeInOrder treeOrder = new  BinTreeInOrder();  
  78.         treeOrder.createBinTree(nums);  
  79.         System.out.print("前序遍历 - " );  
  80.         treeOrder.preOrder(new  Visitor() {  
  81.         });  
  82.         System.out.println();  
  83.         System.out.print("中序遍历 - " );  
  84.         treeOrder.inOrder(new  Visitor() {  
  85.         });  
  86.         System.out.println();  
  87.         System.out.print("后序遍历 - " );  
  88.         treeOrder.postOrder(new  Visitor() {  
  89.         });  
  90.         /*  
  91.          * output:  
  92.          * 前序遍历 - 1 2 4 6 3 5 7 8   
  93.          * 中序遍历 - 4 6 2 1 3 7 5 8   
  94.          * 后序遍历 - 6 4 2 7 8 5 3 1   
  95.          */   
  96.     }  
  97. }   

(三)二叉树的非递归遍历(属外部遍历)

1、利用栈与队列对二叉树进行非递归遍历

Java代码  收藏代码
  1. package  tree.bintree;  
  2.   
  3. import  java.util.Iterator;  
  4. import  java.util.LinkedList;  
  5. import  java.util.Stack;  
  6.   
  7. /**  
  8.  * 二叉树的外部遍历:深度优先(先根)、广度(层次)优先遍历  
  9.  *   
  10.  * @author jzj  
  11.  * @date 2009-12-23  
  12.  */   
  13. public   class  BinTreeOutOrder  extends  BinTree {  
  14.   
  15.     /**  
  16.      * 二叉树深序优先遍历(即二叉树的先根遍历)迭代器,外部可以使用该迭代器  
  17.      * 进行非递归的遍历,这是一种在二叉树结构外部的一种遍历算法,它没有使用  
  18.      * 二叉树本身的结构特点(左右子树递归)进行递归遍历  
  19.      * @author jzj  
  20.      */   
  21.     private   class  DepthOrderIterator  implements  Iterator {  
  22.         //栈里存放的是每个节点   
  23.         private  Stack stack =  new  Stack();  
  24.   
  25.         public  DepthOrderIterator(Entry node) {  
  26.   
  27.             //根入栈,但在放入左右子节点前会马上出栈,即根先优于左右子节点访问   
  28.             stack.push(node);  
  29.   
  30.         }  
  31.   
  32.         //是否还有下一个元素   
  33.         public   boolean  hasNext() {  
  34.             if  (stack.isEmpty()) {  
  35.                 return   false ;  
  36.             }  
  37.             return   true ;  
  38.         }  
  39.   
  40.         //取下一个元素   
  41.         public  Entry next() {  
  42.             if  (hasNext()) {  
  43.                 //取栈顶元素   
  44.                 Entry treeNode = (Entry) stack.pop();//先访问根   
  45.   
  46.                 if  (treeNode.right !=  null ) {  
  47.                     stack.push(treeNode.right);//再放入右子节点   
  48.                 }  
  49.   
  50.                 if  (treeNode.left !=  null ) {  
  51.                     stack.push(treeNode.left);//最后放入左子节点,但访问先于右节点   
  52.                 }  
  53.   
  54.                 // 返回遍历得到的节点   
  55.                 return  treeNode;  
  56.   
  57.             } else  {  
  58.                 // 如果栈为空   
  59.                 return   null ;  
  60.             }  
  61.         }  
  62.   
  63.         public   void  remove() {  
  64.             throw   new  UnsupportedOperationException();  
  65.         }  
  66.   
  67.     }  
  68.   
  69.     /**  
  70.      * 向外界提供先根遍历迭代器  
  71.      * @return Iterator 返回先根遍历迭代器  
  72.      */   
  73.     public  Iterator createPreOrderItr() {  
  74.         return   new  DepthOrderIterator(root);  
  75.     }  
  76.   
  77.     /**  
  78.      * 二叉树广度优先遍历迭代器,外部可以使用该迭代器  
  79.      * 进行非递归的遍历,这是一种在二叉树结构外部的一种遍历算法,它没有使用  
  80.      * 二叉树本身的结构特点(左右子树递归)进行递归遍历  
  81.      * @author jzj  
  82.      */   
  83.     private   class  LevelOrderIterator  implements  Iterator {  
  84.         //使用队列结构实现层次遍历,队列里存储的为节点   
  85.         private  LinkedList queue =  new  LinkedList();  
  86.   
  87.         public  LevelOrderIterator(Entry node) {  
  88.   
  89.             if  (node !=  null ) {  
  90.                 //将根入队   
  91.                 queue.addLast(node);  
  92.             }  
  93.         }  
  94.   
  95.         //是否还有下一个元素   
  96.         public   boolean  hasNext() {  
  97.             if  (queue.isEmpty()) {  
  98.                 return   false ;  
  99.             }  
  100.             return   true ;  
  101.         }  
  102.   
  103.         //取下一个元素   
  104.         public  Entry next() {  
  105.             if  (hasNext()) {  
  106.                 //取栈顶迭元素   
  107.                 Entry treeNode = (Entry) queue.removeFirst();  
  108.   
  109.                 if  (treeNode.left !=  null ) { //如果有左子树,加入有序列表中   
  110.                     queue.addLast(treeNode.left);  
  111.                 }  
  112.                 if  (treeNode.right !=  null ) { //如果有右子树,加入有序列表中   
  113.                     queue.addLast(treeNode.right);  
  114.                 }  
  115.   
  116.                 // 返回遍历得到的节点   
  117.                 return  treeNode;  
  118.   
  119.             } else  {  
  120.                 // 如果队列为空   
  121.                 return   null ;  
  122.             }  
  123.         }  
  124.   
  125.         public   void  remove() {  
  126.             throw   new  UnsupportedOperationException();  
  127.         }  
  128.   
  129.     }  
  130.   
  131.     /**  
  132.      * 向外界提供广度优先迭代器  
  133.      * @return Iterator 返回遍历迭代器  
  134.      */   
  135.     public  Iterator createLayerOrderItr() {  
  136.         return   new  LevelOrderIterator(root);  
  137.     }  
  138.   
  139.     public   static   void  main(String[] args) {  
  140.         //创建一棵满二叉树   
  141.         BinTreeOutOrder treeOrder = new  BinTreeOutOrder();  
  142.         treeOrder.createFullBiTree(15 );  
  143.         Iterator preOrderItr = treeOrder.createPreOrderItr();  
  144.         System.out.print("深度优先(先根)遍历 - " );  
  145.         while  (preOrderItr.hasNext()) {  
  146.             System.out.print(((Entry) preOrderItr.next()).elem + " " );  
  147.         }  
  148.         System.out.println();  
  149.         System.out.print("广度优先(层次)遍历 - " );  
  150.         Iterator layerOrderItr = treeOrder.createLayerOrderItr();  
  151.         while  (layerOrderItr.hasNext()) {  
  152.             System.out.print(((Entry) layerOrderItr.next()).elem + " " );  
  153.         }  
  154.         /*  
  155.          * output:  
  156.          * 深度优先(先根)遍历 - 1 2 4 8 9 5 10 11 3 6 12 13 7 14 15  
  157.          * 广度优先(层次)遍历 - 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15    
  158.          */   
  159.     }  
  160. }   

2、利用二叉树节点的父节点指针进行非递归遍历

要想采用非递归的方法遍历树,又不借助于前面的队列与栈,我们需要该树是一棵可回溯的二叉树,即从子节点要能够知道他的父节点及祖先节点,与前面的二叉树不同的是,树的节点结构体中多一个指向父的节点指针,这样外界可以以非递归的方式来遍历二叉树了

Java代码  收藏代码
  1. package  tree.bintree;  
  2.   
  3. /**  
  4.  *   
  5.  * 可回溯的二叉树  
  6.  * 二叉树的非递归遍历  
  7.  *   
  8.  * @author jzj  
  9.  * @date 2009-12-23  
  10.  */   
  11. public   class  BackBinTree { // Bin=Binary(二进位的, 二元的)   
  12.   
  13.     protected  Entry root; //根   
  14.     private   int  size; //树的节点数   
  15.   
  16.     /**  
  17.      * 树的节点结构  
  18.      * @author jzj  
  19.      * @date 2009-12-23  
  20.      */   
  21.     private   static   class  Entry {  
  22.         int  elem; //数据域,这里为了测试,就作为节点编号吧   
  23.         Entry paraent;//父节点   
  24.         Entry left;//左节点   
  25.         Entry right;//右节点   
  26.   
  27.         //构造函数只有两个参数,左右节点是调用add方法时设置   
  28.         public  Entry( int  elem, Entry parent) {  
  29.             this .elem = elem;  
  30.             this .paraent = parent;  
  31.         }  
  32.     }  
  33.   
  34.     /**  
  35.      * 查找前序遍历(根左右)直接后继节点  
  36.      *   
  37.      * 以非递归 根左右 的方式遍历树  
  38.      *   
  39.      * @param e 需要查找哪个节点的直接后继节点  
  40.      * @return Entry 前序遍历直接后继节点  
  41.      */   
  42.     public  Entry preOrderSuccessor(Entry e) {  
  43.         if  (e ==  null ) {  
  44.             return   null ;  
  45.         }//如果左子树不为空,则直接后继为左子节点   
  46.         else   if  (e.left !=  null ) { //先看左子节点是否为空   
  47.             return  e.left; //如果不为空,则直接后继为左子节点   
  48.         }//否则如果右子树不为空,则直接后继为右子节点   
  49.         else   if  (e.right !=  null ) { //如果左子节点为空,则看右子节点是否为空   
  50.             return  e.right; //如果右子节点不为空,则返回   
  51.         }//左右子节点都为空的情况下   
  52.         else  {  
  53.             Entry s = e.paraent;  
  54.             Entry c = e;  
  55.   
  56.             /*  
  57.             * 一直向上,直到c是s的左子树,且s的右子树不为空。请试着找一下36与68节点的  
  58.             * 直接后继节点,36的应该是75,而68则没有后继节点了  
  59.             *   
  60.             *                            50  
  61.             *                            /\  
  62.             *                          37  75  
  63.             *                         /    /  
  64.             *                       25    61  
  65.             *                      /\     /\  
  66.             *                    15 30   55 68  
  67.             *                       /\    \  
  68.             *                     28 32   59  
  69.             *                         \  
  70.             *                         36  
  71.             */   
  72.             while  (s !=  null  && (c == s.right || s.right ==  null )) {  
  73.                 c = s;  
  74.                 s = s.paraent;  
  75.             }  
  76.             //退出循环时 s 可以为null,比如查找 68 节点的直接后继时退出循环时s=null   
  77.             if  (s ==  null ) {  
  78.                 return   null ;  
  79.             } else  {  
  80.                 return  s.right;  
  81.             }  
  82.         }  
  83.     }  
  84.   
  85.     /**  
  86.      * 查找前序遍历(根左右)直接前驱节点  
  87.      *   
  88.      * 以非递归 右左根 的方式遍历树  
  89.      *   
  90.      * @param e 需要查找哪个节点的直接前驱节点  
  91.      * @return Entry 前序遍历直接前驱节点  
  92.      */   
  93.     public  Entry preOrderAncestor(Entry e) {  
  94.         if  (e ==  null ) {  
  95.             return   null ;  
  96.         }//如果节点为父节点的左节点,则父节点就是直接前驱节点   
  97.         else   if  (e.paraent !=  null  && e == e.paraent.left) {  
  98.             return  e.paraent;  
  99.         }//如果节点为父节点的右节点   
  100.         else   if  (e.paraent !=  null  && e == e.paraent.right) {  
  101.   
  102.             Entry s = e.paraent;//前驱节点默认为父节点   
  103.             if  (s.left !=  null ) { //如果父节点没有左子,前驱节点就为父节点   
  104.                 s = s.left;//如果父节点的左子节点不空,则初始为父节点左子节点   
  105.   
  106.                 /*  
  107.                 * 只要父节点左子节点还有子节点,则前驱节点要从其子树中找。请试着找  
  108.                 * 一下75直接前驱节点,应该是36  
  109.                 *   
  110.                 *                            50  
  111.                 *                            /\  
  112.                 *                          37  75  
  113.                 *                         /    /  
  114.                 *                       25    61  
  115.                 *                      /\     /\  
  116.                 *                    15 30   55 68  
  117.                 *                       /\    \  
  118.                 *                     28 32   59  
  119.                 *                         \  
  120.                 *                         36  
  121.                 */   
  122.                 while  (s.left !=  null  || s.right !=  null ) {  
  123.                     //在父节点的左子节点的子树中查找时,一定要先向右边拐   
  124.                     if  (s.right !=  null ) {  
  125.                         s = s.right;  
  126.                     } else  { //如果右边没有,然后才能向左边拐   
  127.                         s = s.left;  
  128.                     }  
  129.                 }  
  130.             }  
  131.             return  s;  
  132.         } else  { //如果是根节点,则没有直接前驱节点了   
  133.             return   null ;  
  134.         }  
  135.     }  
  136.   
  137.     /**  
  138.      * 查找后序遍历(左右根)直接后继节点  
  139.      *   
  140.      * 以非递归 左右根 的方式遍历树  
  141.      *   
  142.      * @param e 需要查找哪个节点的直接后继节点  
  143.      * @return Entry 后序遍历直接后继节点  
  144.      */   
  145.     public  Entry postOrderSuccessor(Entry e) {  
  146.         if  (e ==  null ) {  
  147.             return   null ;  
  148.         }//如果节点为父节点的右子节点,则父节点就是直接后继节点   
  149.         else   if  (e.paraent !=  null  && e == e.paraent.right) {  
  150.             return  e.paraent;  
  151.         }//如果节点为父节点的左子节点   
  152.         else   if  (e.paraent !=  null  && e == e.paraent.left) {  
  153.             Entry s = e.paraent;//后继节点默认为父节点   
  154.             if  (s.right !=  null ) { //如果父节点没有右子,后继节点就为父节点   
  155.                 s = s.right;//如果父节点的右子节点不空,则初始为父节点右子节点   
  156.                 /*  
  157.                  * 只要父节点右子节点还有子节点,则后断节点要从其子树中找,  
  158.                  * 如15的后继节点为28  
  159.                  *                            50  
  160.                  *                            /\  
  161.                  *                          37  75  
  162.                  *                         /    /  
  163.                  *                       25    61  
  164.                  *                      /\     /\  
  165.                  *                    15 30   55 68  
  166.                  *                       /\    \  
  167.                  *                     28 32   59  
  168.                  *                         \  
  169.                  *                         36  
  170.                  */   
  171.   
  172.                 while  (s.left !=  null  || s.right !=  null ) {  
  173.                     //在父节点的右子节点的子树中查找时,一定要先向左边拐   
  174.                     if  (s.left !=  null ) {  
  175.                         s = s.left;  
  176.                     } else  { //如果左边没有,然后才能向右边拐   
  177.                         s = s.right;  
  178.                     }  
  179.                 }  
  180.             }  
  181.             return  s;  
  182.         } else  {  
  183.             //如果是根节点,则没有后继节点了   
  184.             return   null ;  
  185.         }  
  186.     }  
  187.   
  188.     /**  
  189.      * 查找后序遍历(左右根)直接前驱节点  
  190.      *   
  191.      * 以非递归 根右左 的方式遍历树  
  192.      *   
  193.      * @param e 需要查找哪个节点的直接前驱节点  
  194.      * @return Entry 后序遍历直接前驱节点  
  195.      */   
  196.     public  Entry postOrderAncestor(Entry e) {  
  197.   
  198.         if  (e ==  null ) {  
  199.             return   null ;  
  200.         }//如果右子树不为空,则直接前驱为右子节点   
  201.         else   if  (e.right !=  null ) { //先看右子节点是否为空   
  202.             return  e.right; //如果不为空,则直接后继为右子节点   
  203.         }//否则如果左子树不为空,则直接前驱为左子节点   
  204.         else   if  (e.left !=  null ) {  
  205.             return  e.left;  
  206.         }//左右子节点都为空的情况下   
  207.         else  {  
  208.             Entry s = e.paraent;  
  209.             Entry c = e;  
  210.   
  211.             /*  
  212.             * 一直向上,直到c是s的右子树,且s的左子树不为空。请试着找一下59与15节点的  
  213.             * 直接后继节点,59的应该是37,而15则没有后继节点了  
  214.             *   
  215.             *                            50  
  216.             *                            /\  
  217.             *                          37  75  
  218.             *                         /    /  
  219.             *                       25    61  
  220.             *                      /\     /\  
  221.             *                    15 30   55 68  
  222.             *                       /\    \  
  223.             *                     28 32   59  
  224.             *                         \  
  225.             *                         36  
  226.             */   
  227.             while  (s !=  null  && (c == s.left || s.left ==  null )) {  
  228.                 c = s;  
  229.                 s = s.paraent;  
  230.             }  
  231.             if  (s ==  null ) {  
  232.                 return   null ;  
  233.             } else  {  
  234.                 return  s.left;  
  235.             }  
  236.         }  
  237.     }  
  238.   
  239.     /**  
  240.      * 查找中序遍历(左根右)直接后继节点  
  241.      *   
  242.      * 以非递归 左根右 的方式遍历树  
  243.      *   
  244.      * @param e 需要查找哪个节点的直接后继节点  
  245.      * @return Entry 中序遍历直接后继节点  
  246.      */   
  247.     public  Entry inOrderSuccessor(Entry e) {  
  248.         if  (e ==  null ) {  
  249.             return   null ;  
  250.         }//如果待找的节点有右子树,则在右子树上查找   
  251.         else   if  (e.right !=  null ) {  
  252.             //默认后继节点为右子节点(如果右子节点没有左子树时即为该节点)   
  253.             Entry p = e.right;  
  254.             while  (p.left !=  null ) {  
  255.                 //注,如果右子节点的左子树不为空,则在左子树中查找,且后面找时要一直向左拐   
  256.                 p = p.left;  
  257.             }  
  258.             return  p;  
  259.         }//如果待查节点没有右子树,则要在祖宗节点中查找后继节点    
  260.         else  {  
  261.             //默认后继节点为父节点(如果待查节点为父节点的左子树,则后继为父节点)   
  262.             Entry p = e.paraent;  
  263.             Entry current = e;//当前节点,如果其父不为后继,则下次指向父节点   
  264.             //如果待查节点为父节点的右节点时,继续向上找,一直要找到current为左子节点,则s才是后继   
  265.             while  (p !=  null  && current == p.right) {  
  266.                 current = p;  
  267.                 p = p.paraent;  
  268.             }  
  269.             return  p;  
  270.         }  
  271.     }  
  272.   
  273.     /**  
  274.      * 查找中序遍历(左根右)直接前驱节点  
  275.      *   
  276.      * 以非递归 右根左 的方式遍历树  
  277.      *   
  278.      * @param e 需要查找哪个节点的直接前驱节点  
  279.      * @return Entry 中序遍历直接前驱节点  
  280.      */   
  281.     public  Entry inOrderAncestor(Entry e) {  
  282.         if  (e ==  null ) {  
  283.             return   null ;  
  284.         }//如果待找的节点有左子树,则在在子树上查找   
  285.         else   if  (e.left !=  null ) {  
  286.             //默认直接前驱节点为左子节点(如果左子节点没有右子树时即为该节点)   
  287.             Entry p = e.left;  
  288.             while  (p.right !=  null ) {  
  289.                 //注,如果左子节点的右子树不为空,则在右子树中查找,且后面找时要一直向右拐   
  290.                 p = p.right;  
  291.             }  
  292.             return  p;  
  293.         }//如果待查节点没有左子树,则要在祖宗节点中查找前驱节点    
  294.         else  {  
  295.             //默认前驱节点为父节点(如果待查节点为父节点的右子树,则前驱为父节点)   
  296.             Entry p = e.paraent;  
  297.             Entry current = e;//当前节点,如果其父不为前驱,则下次指向父节点   
  298.             //如果待查节点为父节点的左节点时,继续向上找,一直要找到current为p的右子节点,则s才是前驱   
  299.             while  (p !=  null  && current == p.left) {  
  300.                 current = p;  
  301.                 p = p.paraent;  
  302.             }  
  303.             return  p;  
  304.         }  
  305.     }  
  306.   
  307.     /**  
  308.      * 查找指定的节点  
  309.      * @param num  
  310.      * @return Entry  
  311.      */   
  312.     public  Entry getEntry( int  num) {  
  313.         return  getEntry(root, num);  
  314.     }  
  315.   
  316.     /**  
  317.      * 使用树的先序遍历递归方式查找指定的节点  
  318.      *   
  319.      * @param entry  
  320.      * @param num  
  321.      * @return  
  322.      */   
  323.     private  Entry getEntry(Entry entry,  int  num) {  
  324.   
  325.         //如果找到,则停止后续搜索,并把查找到的节点返回给上层调用者   
  326.         if  (entry.elem == num) { //1、先与父节点比对   
  327.             return  entry;  
  328.         }  
  329.   
  330.         Entry tmp = null ;  
  331.   
  332.         if  (entry.left !=  null ) { //2、再在左子树上找   
  333.             tmp = getEntry(entry.left, num);  
  334.             //如果左子树上找到,返回并停止查找,否则继续在后续节点中找   
  335.             if  (tmp !=  null ) {  
  336.                 //节点在左子树中找到,返回给上层调用者   
  337.                 return  tmp;  
  338.             }  
  339.         }  
  340.   
  341.         if  (entry.right !=  null ) { //3、否则在右子树上找   
  342.             tmp = getEntry(entry.right, num);  
  343.             //如果右子树上找到,返回并停止查找,否则继续在后续节点中找   
  344.             if  (tmp !=  null ) {  
  345.                 //节点在右子树中找到,返回给上层调用者   
  346.                 return  tmp;  
  347.             }  
  348.         }  
  349.   
  350.         //当前比较节点 entry 子树为空或不为空时没有找到,直接返回给上层调用者null   
  351.         return   null ;  
  352.     }  
  353.   
  354.     /**  
  355.      * 根据给定的数组创建一棵树,这个棵树可以是完全二叉树也可是普通二叉树  
  356.      * 数组中为0的表示不创建该位置上的节点  
  357.      * @param nums 数组中指定了要创建的节点的编号,如果为0,表示不创建  
  358.      */   
  359.     public   void  createBinTree( int [] nums) {  
  360.         root = recurCreateBinTree(nums, null 0 );  
  361.     }  
  362.   
  363.     /**  
  364.      * 递归创建二叉树  
  365.      * @param nums 数组中指定了要创建的节点的编号,如果为0,表示不创建  
  366.      * @param paraent 父节点  
  367.      * @param index 需要使用数组中的哪个元素创建节点,如果为元素为0,则不创建  
  368.      * @return Entry 返回创建的节点,最终会返回树的根节点  
  369.      */   
  370.     private  Entry recurCreateBinTree( int [] nums, Entry pararent,  int  index) {  
  371.         //指定索引上的编号不为零上才需创建节点   
  372.         if  (nums[index] !=  0 ) {  
  373.             size++;  
  374.             Entry root = new  Entry(nums[index], pararent); //根节点   
  375.             //如果有左子树则创建左子树   
  376.             if  ((index +  1 ) *  2  <= nums.length) {  
  377.                 root.left = (Entry) recurCreateBinTree(nums, root, (index + 1 ) *  2  -  1 );  
  378.                 //如果还可以创建右子树,则创建   
  379.                 if  ((index +  1 ) *  2  +  1  <= nums.length) {  
  380.                     root.right = (Entry) recurCreateBinTree(nums, root, (index + 1 ) *  2 );  
  381.                 }  
  382.             }  
  383.             return  (Entry) root;  
  384.         }  
  385.         return   null ;  
  386.   
  387.     }  
  388.   
  389.     public   int  size() {  
  390.         return  size;  
  391.     }  
  392.   
  393.     //测试   
  394.     public   static   void  main(String[] args) {  
  395.   
  396.         //创建一棵非完全二叉树   
  397.         BackBinTree binTree = new  BackBinTree();  
  398.         /*  
  399.         *                            50  
  400.         *                            /\  
  401.         *                          37  75  
  402.         *                         /    /  
  403.         *                       25    61  
  404.         *                      /\     /\  
  405.         *                    15 30   55 68  
  406.         *                       /\    \  
  407.         *                     28 32   59  
  408.         *                         \  
  409.         *                         36  
  410.         */   
  411.         int [] nums =  new   int [] {  50 37 75 25 0 61 0 15 30 0 0 55 68 0 0 0 ,  
  412.                 0 28 32 0 0 0 0 0 59 0 0 0 0 0 0 0 0 0 0 0 0 0 36  };  
  413.         binTree.createBinTree(nums);  
  414.   
  415.         Entry entry = binTree.getEntry(50 );  
  416.         System.out.print("根左右(先序遍历)- " );  
  417.         while  (entry !=  null ) {  
  418.             System.out.print(entry.elem + " " );  
  419.             entry = binTree.preOrderSuccessor(entry);  
  420.         }  
  421.         System.out.println();  
  422.         entry = binTree.getEntry(68 );  
  423.         System.out.print("右左根(先序的逆)- " );  
  424.         while  (entry !=  null ) {  
  425.             System.out.print(entry.elem + " " );  
  426.             entry = binTree.preOrderAncestor(entry);  
  427.         }  
  428.         System.out.println();  
  429.         entry = binTree.getEntry(15 );  
  430.         System.out.print("左右根(后序遍历)- " );  
  431.         while  (entry !=  null ) {  
  432.             System.out.print(entry.elem + " " );  
  433.             entry = binTree.postOrderSuccessor(entry);  
  434.         }  
  435.         System.out.println();  
  436.   
  437.         entry = binTree.getEntry(50 );  
  438.         System.out.print("根右左(后序的逆)- " );  
  439.         while  (entry !=  null ) {  
  440.             System.out.print(entry.elem + " " );  
  441.             entry = binTree.postOrderAncestor(entry);  
  442.         }  
  443.         System.out.println();  
  444.   
  445.         entry = binTree.getEntry(15 );  
  446.         System.out.print("左根右(中序遍历)- " );  
  447.         while  (entry !=  null ) {  
  448.             System.out.print(entry.elem + " " );  
  449.             entry = binTree.inOrderSuccessor(entry);  
  450.         }  
  451.         System.out.println();  
  452.   
  453.         entry = binTree.getEntry(75 );  
  454.         System.out.print("右根左(中序的逆)- " );  
  455.         while  (entry !=  null ) {  
  456.             System.out.print(entry.elem + " " );  
  457.             entry = binTree.inOrderAncestor(entry);  
  458.         }  
  459.         System.out.println();  
  460.         /*  
  461.          * output:  
  462.          * 根左右(先序遍历)- 50 37 25 15 30 28 32 36 75 61 55 59 68   
  463.          * 右左根(先序的逆)- 68 59 55 61 75 36 32 28 30 15 25 37 50  
  464.          * 左右根(后序遍历)- 15 28 36 32 30 25 37 59 55 68 61 75 50  
  465.          * 根右左(后序的逆)- 50 75 61 68 55 59 37 25 30 32 36 28 15  
  466.          * 左根右(中序遍历)- 15 25 28 30 32 36 37 50 55 59 61 68 75  
  467.          * 右根左(中序的逆)- 75 68 61 59 55 50 37 36 32 30 28 25 15    
  468.          */   
  469.     }  

分享到:
评论

相关推荐

    数据结构实验报告6-树-二叉树的遍历算法-实验内容及要求.docx

    通过这次实验,学生不仅可以巩固和扩展关于二叉树及其遍历算法的知识,还能提高实际编程能力,学会如何使用循环队列等数据结构来解决实际问题。此外,通过亲手编写代码并调试运行,能够更深刻地理解理论知识与实际...

    二叉树遍历实验报告

    - **结论:** 通过本实验,成功实现了二叉树的多种遍历方法,并计算了二叉树的深度和叶子节点数量,加深了对二叉树及其遍历的理解。 - **改进建议:** - 进一步优化遍历算法的时间复杂度。 - 增加异常处理机制,...

    数据结构 二叉树的遍历 c语言版

    ### 数据结构:二叉树的遍历(C语言版) #### 一、引言 在计算机科学中,数据结构是...在实际应用中,二叉树及其遍历方法是非常重要的基础,掌握这些基本概念和技术对于深入理解高级数据结构和算法设计具有重要意义。

    二叉树的创建及其遍历

     按先序遍历的扩展序列建立二叉树的二叉链表存储结构,实现二叉树先序、中序、后序遍历的递归算法,实现二叉树中序遍历的非递归算法,实现二叉树层次遍历的非递归算法(要求使用顺序队列,调用顺序队列基本操作...

    什么是二叉树的遍历以及学习二叉树的遍历的意义

    ### 二叉树遍历的重要性及其意义 #### 一、二叉树的遍历概念 在探讨二叉树遍历的重要性和意义之前,首先需要明确什么是二叉树的遍历。简单来说,二叉树的遍历就是按照某种确定的顺序访问二叉树中的所有节点的过程...

    树,二叉树及其遍历,哈夫曼树课题讲解

    二叉树的遍历是其重要特性之一,通常有三种遍历方法: 1. 前序遍历:访问根节点,然后遍历左子树,最后遍历右子树。 2. 中序遍历:对于二叉排序树,中序遍历可以得到升序序列。 3. 后序遍历:先遍历左子树,然后遍历...

    二叉树的遍历 C语言 数据结构课设

    该程序实现了二叉树的存储,及其先序、中序和后序的遍历,还能够统计二叉树的叶子结点的个数。 二、设计内容 1. 数据结构 在本程序中,我们使用了二叉树结点结构体 BiTNode,包含了节点的内容(char 数据类型)和...

    二叉树的遍历及其操作

    二叉树的遍历及其操作

    中序线索化二叉树及中序遍历

    二叉树是一种重要的数据结构,它由节点组成,每个节点包含一个值以及指向左子节点和右子...理解并掌握中序线索化二叉树及其遍历的方法,对于提升算法能力,特别是在数据结构和算法相关的编程面试中,都是非常有价值的。

    实验八:二叉树的遍历算法

    该方法通过输入节点编号及其数据值的方式构建二叉树。具体实现过程如下: 1. 首先读取节点编号(i)和节点数据值(e),如果 i 和 e 均为 0,则结束输入。 2. 根据节点编号动态分配空间并初始化节点。 3. 如果是根...

    二叉树的遍历算法与相关设计

    本文将深入探讨二叉树的遍历算法及其在求解二叉树高度问题上的应用。 首先,我们要了解二叉树的基本概念。二叉树是由n(n&gt;=0)个有限节点组成的一个有穷集合,且满足以下条件: 1. 有且仅有一个特定的称为根的节点...

    二叉树的遍历与求深度以及结点数

    在探讨二叉树的遍历方法及其深度与结点数的计算之前,我们首先简要回顾一下二叉树的基本定义。二叉树是一种特殊的树结构,其中每个节点最多有两个子节点,通常称为左子节点和右子节点。二叉树具有以下特点: 1. **...

    C语言数据结构之线索二叉树及其遍历

    C语言数据结构之线索二叉树及其遍历 遍历二叉树就是以一定的规则将二叉树中的节点排列成一个线性序列,从而得到二叉树节点的各种遍历序列,其实质是:对一个非线性的结构进行线性化。使得在这个访问序列中每一个节点...

    二叉树的遍历——递归以及非递归实现

    vs2010下运行编写,使用了STL栈,实现了基本的插入、删除、计算深度、查找,主要是遍历,包括递归遍历,以及非递归的前序中序后序遍历,每个函数都有测试用例,如果存在错误,请在给我留言。

    数据结构 二叉树 遍历 源代码

    本篇文章将深入探讨二叉树及其遍历方法的源代码实现。 二叉树是由节点构成的层次结构,每个节点最多有两个子节点,分别称为左子节点和右子节点。二叉树的主要操作包括创建、插入、删除节点以及遍历。遍历是指按照...

    二叉树的遍历及通过前序中序遍历确定后序层序遍历

    本话题主要涉及二叉树的遍历方法及其在特定情况下的应用。 二叉树的遍历主要有三种经典方法:前序遍历、中序遍历和后序遍历。这些遍历方法是理解二叉树特性和操作的关键。 1. **前序遍历**(Preorder Traversal)...

    二叉树的遍历

    二叉树的遍历是数据结构领域中的一个重要概念,它涉及到计算机科学中树形数据结构的访问策略。在深入理解这一主题之前,我们先要明白什么是...无论是学术研究还是工业界的应用,二叉树及其遍历都是一个不可或缺的工具。

Global site tag (gtag.js) - Google Analytics