顺序存储二叉树，线索化二叉树

小咪咪 2024-04-18 19:24 109阅读 0赞

## 一、 顺序存储二叉树　 ##

### 1、概述 ###

从数据存储来看，数组存储方式和树的存储方式可以相互转换，即数组可以转换成树，树也可以转换成数组

![1007094-20190910155601784-1855905638.png][]

### 2、特点 ###

*  顺序二叉树通常只考虑完全二叉树
 *  第n个元素的左子节点为  2 \* n + 1
 *  第n个元素的右子节点为  2 \* n + 2
 *  第n个元素的父节点为  (n-1) / 2
 *  n : 表示二叉树中的第几个元素(按0开始编号如图所示)

### 3、八大排序算法中的堆排序，就要使用到顺序存储二叉树 ###

### 4、完整代码 ###

1  2 
     3 public class ArrBinaryTreeDemo {
     4 
     5     public static void main(String[] args) {
     6         int[] arr = { 1, 2, 3, 4, 5, 6, 7 };
     7         //创建一个 ArrBinaryTree
     8         ArrBinaryTree arrBinaryTree = new ArrBinaryTree(arr);
     9         arrBinaryTree.preOrder(); // 1,2,4,5,3,6,7
    10     }
    11 
    12 }
    13 
    14 //编写一个ArrayBinaryTree, 实现顺序存储二叉树遍历
    15 
    16 class ArrBinaryTree {
    17     private int[] arr;//存储数据结点的数组
    18 
    19     public ArrBinaryTree(int[] arr) {
    20         this.arr = arr;
    21     }
    22     
    23     //重载preOrder
    24     public void preOrder() {
    25         this.preOrder(0);
    26     }
    27     
    28     //编写一个方法，完成顺序存储二叉树的前序遍历
    29     /**
    30      * 
    31      * @param index 数组的下标 
    32      */
    33     public void preOrder(int index) {
    34         //如果数组为空，或者 arr.length = 0
    35         if(arr == null || arr.length == 0) {
    36             System.out.println("数组为空，不能按照二叉树的前序遍历");
    37         }
    38         //输出当前这个元素
    39         System.out.println(arr[index]); 
    40         //向左递归遍历
    41         if((index * 2 + 1) < arr.length) {
    42             preOrder(2 * index + 1 );
    43         }
    44         //向右递归遍历
    45         if((index * 2 + 2) < arr.length) {
    46             preOrder(2 * index + 2);
    47         }
    48     }
    49     
    50 }

## 二、线索化二叉树　 ##

### 1、概述 ###

1）n个结点的二叉链表中含有n+1  【公式 2n-(n-1)=n+1】 个空指针域。利用二叉链表中的空指针域，存放指向该结点在某种遍历次序下的前驱和后继结点的指针（这种附加的指针称为"线索"）  
  
　　2）这种加上了线索的二叉链表称为线索链表，相应的二叉树称为线索**二叉树(Threaded BinaryTree)**。

根据线索性质的不同，线索二叉树可分为**前序线索二叉树**、**中序线索二叉树**和**后序线索二叉树**三种  
  
　　3）一个结点的前一个结点，称为前驱结点  
　　4）一个结点的后一个结点，称为后继结点

### 2、代码　　 ###

1 public class ThreadedBT{
      2 
      3     public static void main(String[] args) {
      4         HeroNode root = new HeroNode(1, "亚瑟");
      5         HeroNode node2 = new HeroNode(3, "凯");
      6         HeroNode node3 = new HeroNode(6, "甄姬");
      7         HeroNode node4 = new HeroNode(8, "虞姬");
      8         HeroNode node5 = new HeroNode(10, "猴子");
      9         HeroNode node6 = new HeroNode(14, "兰陵王");
     10 
     11         //二叉树，后面我们要递归创建, 现在简单处理使用手动创建
     12         root.setLeft(node2);
     13         root.setRight(node3);
     14         node2.setLeft(node4);
     15         node2.setRight(node5);
     16         node3.setLeft(node6);
     17 
     18         //测试中序线索化
     19         ThreadedBinaryTree threadedBinaryTree = new ThreadedBinaryTree();
     20         threadedBinaryTree.setRoot(root);
     21         threadedBinaryTree.threadedNodes();
     22 
     23         //测试: 以10号节点测试
     24         HeroNode leftNode = node5.getLeft();
     25         HeroNode rightNode = node5.getRight();
     26 
     27         //当线索化二叉树后，能在使用原来的遍历方法
     28         //threadedBinaryTree.infixOrder();
     29         System.out.println("使用线索化的方式遍历 线索化二叉树");
     30         threadedBinaryTree.threadedList();
     31     }
     32 }
     33 
     34 class ThreadedBinaryTree {
     35     private HeroNode root;
     36 
     37     //为了实现线索化，需要创建要给指向当前结点的前驱结点的指针
     38     //在递归进行线索化时，pre 总是保留前一个结点
     39     private HeroNode pre = null;
     40 
     41     public void setRoot(HeroNode root) {
     42         this.root = root;
     43     }
     44 
     45     //重载一把threadedNodes方法
     46     public void threadedNodes() {
     47         this.threadedNodes(root);
     48     }
     49 
     50     //遍历线索化二叉树的方法
     51     public void threadedList() {
     52         //定义一个变量，存储当前遍历的结点，从root开始
     53         HeroNode node = root;
     54         while(node != null) {
     55             //循环的找到leftType == 1的结点，第一个找到就是8结点
     56             //后面随着遍历而变化,因为当leftType==1时，说明该结点是按照线索化
     57             //处理后的有效结点
     58             while(node.getLeftType() == 0) {
     59                 node = node.getLeft();
     60             }
     61 
     62             //打印当前这个结点
     63             System.out.println(node);
     64             //如果当前结点的右指针指向的是后继结点,就一直输出
     65             while(node.getRightType() == 1) {
     66                 //获取到当前结点的后继结点
     67                 node = node.getRight();
     68                 System.out.println(node);
     69             }
     70             //替换这个遍历的结点
     71             node = node.getRight();
     72 
     73         }
     74     }
     75 
     76     //编写对二叉树进行中序线索化的方法
     77     /**
     78      *
     79      * @param node 就是当前需要线索化的结点
     80      */
     81     public void threadedNodes(HeroNode node) {
     82 
     83         //如果node==null, 不能线索化
     84         if(node == null) {
     85             return;
     86         }
     87 
     88         //(一)先线索化左子树
     89         threadedNodes(node.getLeft());
     90         //(二)线索化当前结点[有难度]
     91 
     92         //处理当前结点的前驱结点
     93         //以8结点来理解
     94         //8结点的.left = null , 8结点的.leftType = 1
     95         if(node.getLeft() == null) {
     96             //让当前结点的左指针指向前驱结点
     97             node.setLeft(pre);
     98             //修改当前结点的左指针的类型,指向前驱结点
     99             node.setLeftType(1);
    100         }
    101 
    102         //处理后继结点
    103         if (pre != null && pre.getRight() == null) {
    104             //让前驱结点的右指针指向当前结点
    105             pre.setRight(node);
    106             //修改前驱结点的右指针类型
    107             pre.setRightType(1);
    108         }
    109         //!!! 每处理一个结点后，让当前结点是下一个结点的前驱结点
    110         pre = node;
    111 
    112         //(三)在线索化右子树
    113         threadedNodes(node.getRight());
    114 
    115 
    116     }
    117     //前序遍历
    118     public void preOrder() {
    119         if(this.root != null) {
    120             this.root.preOrder();
    121         }else {
    122             System.out.println("二叉树为空，无法遍历");
    123         }
    124     }
    125 
    126     //中序遍历
    127     public void infixOrder() {
    128         if(this.root != null) {
    129             this.root.infixOrder();
    130         }else {
    131             System.out.println("二叉树为空，无法遍历");
    132         }
    133     }
    134     //后序遍历
    135     public void postOrder() {
    136         if(this.root != null) {
    137             this.root.postOrder();
    138         }else {
    139             System.out.println("二叉树为空，无法遍历");
    140         }
    141     }
    142 
    143    
    144 }
    145 
    146 //先创建HeroNode 结点
    147 class HeroNode {
    148     private int no;
    149     private String name;
    150     private HeroNode left; //默认null
    151     private HeroNode right; //默认null
    152     //说明
    153     //1. 如果leftType == 0 表示指向的是左子树, 如果 1 则表示指向前驱结点
    154     //2. 如果rightType == 0 表示指向是右子树, 如果 1表示指向后继结点
    155     private int leftType;
    156     private int rightType;
    157 
    158     public int getLeftType() {
    159         return leftType;
    160     }
    161     public void setLeftType(int leftType) {
    162         this.leftType = leftType;
    163     }
    164     public int getRightType() {
    165         return rightType;
    166     }
    167     public void setRightType(int rightType) {
    168         this.rightType = rightType;
    169     }
    170     public HeroNode(int no, String name) {
    171         this.no = no;
    172         this.name = name;
    173     }
    174     public int getNo() {
    175         return no;
    176     }
    177     public void setNo(int no) {
    178         this.no = no;
    179     }
    180     public String getName() {
    181         return name;
    182     }
    183     public void setName(String name) {
    184         this.name = name;
    185     }
    186     public HeroNode getLeft() {
    187         return left;
    188     }
    189     public void setLeft(HeroNode left) {
    190         this.left = left;
    191     }
    192     public HeroNode getRight() {
    193         return right;
    194     }
    195     public void setRight(HeroNode right) {
    196         this.right = right;
    197     }
    198     @Override
    199     public String toString() {
    200         return "HeroNode [no=" + no + ", name=" + name + "]";
    201     }
    202 
    203     //递归删除结点
    204     //1.如果删除的节点是叶子节点，则删除该节点
    205     //2.如果删除的节点是非叶子节点，则删除该子树
    206     public void delNode(int no) {
    207 
    208         /*
    209          *     1. 因为我们的二叉树是单向的，所以我们是判断当前结点的子结点是否需要删除结点，而不能去判断当前这个结点是不是需要删除结点.
    210             2. 如果当前结点的左子结点不为空，并且左子结点 就是要删除结点，就将this.left = null; 并且就返回(结束递归删除)
    211             3. 如果当前结点的右子结点不为空，并且右子结点 就是要删除结点，就将this.right= null ;并且就返回(结束递归删除)
    212             4. 如果第2和第3步没有删除结点，那么我们就需要向左子树进行递归删除
    213             5.  如果第4步也没有删除结点，则应当向右子树进行递归删除.
    214 
    215          */
    216         //2. 如果当前结点的左子结点不为空，并且左子结点 就是要删除结点，就将this.left = null; 并且就返回(结束递归删除)
    217         if(this.left != null && this.left.no == no) {
    218             this.left = null;
    219             return;
    220         }
    221         //3.如果当前结点的右子结点不为空，并且右子结点 就是要删除结点，就将this.right= null ;并且就返回(结束递归删除)
    222         if(this.right != null && this.right.no == no) {
    223             this.right = null;
    224             return;
    225         }
    226         //4.我们就需要向左子树进行递归删除
    227         if(this.left != null) {
    228             this.left.delNode(no);
    229         }
    230         //5.则应当向右子树进行递归删除
    231         if(this.right != null) {
    232             this.right.delNode(no);
    233         }
    234     }
    235 
    236     //编写前序遍历的方法
    237     public void preOrder() {
    238         System.out.println(this); //先输出父结点
    239         //递归向左子树前序遍历
    240         if(this.left != null) {
    241             this.left.preOrder();
    242         }
    243         //递归向右子树前序遍历
    244         if(this.right != null) {
    245             this.right.preOrder();
    246         }
    247     }
    248     //中序遍历
    249     public void infixOrder() {
    250 
    251         //递归向左子树中序遍历
    252         if(this.left != null) {
    253             this.left.infixOrder();
    254         }
    255         //输出父结点
    256         System.out.println(this);
    257         //递归向右子树中序遍历
    258         if(this.right != null) {
    259             this.right.infixOrder();
    260         }
    261     }
    262     //后序遍历
    263     public void postOrder() {
    264         if(this.left != null) {
    265             this.left.postOrder();
    266         }
    267         if(this.right != null) {
    268             this.right.postOrder();
    269         }
    270         System.out.println(this);
    271     }
    272 
    273     //前序遍历查找
    274     /**
    275      *
    276      * @param no 查找no
    277      * @return 如果找到就返回该Node ,如果没有找到返回 null
    278      */
    279     public HeroNode preOrderSearch(int no) {
    280         System.out.println("进入前序遍历");
    281         //比较当前结点是不是
    282         if(this.no == no) {
    283             return this;
    284         }
    285         //1.则判断当前结点的左子节点是否为空，如果不为空，则递归前序查找
    286         //2.如果左递归前序查找，找到结点，则返回
    287         HeroNode resNode = null;
    288         if(this.left != null) {
    289             resNode = this.left.preOrderSearch(no);
    290         }
    291         if(resNode != null) {
        //说明我们左子树找到
    292             return resNode;
    293         }
    294         //1.左递归前序查找，找到结点，则返回，否继续判断，
    295         //2.当前的结点的右子节点是否为空，如果不空，则继续向右递归前序查找
    296         if(this.right != null) {
    297             resNode = this.right.preOrderSearch(no);
    298         }
    299         return resNode;
    300     }
    301 
    302     //中序遍历查找
    303     public HeroNode infixOrderSearch(int no) {
    304         //判断当前结点的左子节点是否为空，如果不为空，则递归中序查找
    305         HeroNode resNode = null;
    306         if(this.left != null) {
    307             resNode = this.left.infixOrderSearch(no);
    308         }
    309         if(resNode != null) {
    310             return resNode;
    311         }
    312         System.out.println("进入中序查找");
    313         //如果找到，则返回，如果没有找到，就和当前结点比较，如果是则返回当前结点
    314         if(this.no == no) {
    315             return this;
    316         }
    317         //否则继续进行右递归的中序查找
    318         if(this.right != null) {
    319             resNode = this.right.infixOrderSearch(no);
    320         }
    321         return resNode;
    322 
    323     }
    324 
    325     //后序遍历查找
    326     public HeroNode postOrderSearch(int no) {
    327 
    328         //判断当前结点的左子节点是否为空，如果不为空，则递归后序查找
    329         HeroNode resNode = null;
    330         if(this.left != null) {
    331             resNode = this.left.postOrderSearch(no);
    332         }
    333         if(resNode != null) {
        //说明在左子树找到
    334             return resNode;
    335         }
    336 
    337         //如果左子树没有找到，则向右子树递归进行后序遍历查找
    338         if(this.right != null) {
    339             resNode = this.right.postOrderSearch(no);
    340         }
    341         if(resNode != null) {
    342             return resNode;
    343         }
    344         System.out.println("进入后序查找");
    345         //如果左右子树都没有找到，就比较当前结点是不是
    346         if(this.no == no) {
    347             return this;
    348         }
    349         return resNode;
    350     }
    351 
    352 }

![loading.gif][]

[1007094-20190910155601784-1855905638.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/5b7b3138cbaa47a3b5f6828c8b014998.png
[loading.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/71c594bcc0254135b91e3df4406fc1ce.gif