二叉树介绍

  1. 树有很多种，每个节点最多只能有两个子节点的一种形式称为二叉树。
  2. 二叉树的子节点分为 左节点 和 右节点。

image.png

  1. 如果该二叉树的所有叶子节点都在最后一层，并且节点总数为2**n**-1，n为层数，则我们称为满二叉树

image.png

  1. 如果该二叉树的所有叶子节点都在最后一层或者倒数第二层，而且最后一层的叶子节点在左边连续，倒数第二成的叶子节点在右边连续，我们称为完全二叉树

image.png

  1. 满二叉树一定是完全二叉树，反之不成立

    遍历节点

  2. 前序遍历：先输出父节点，再遍历左子树和右子树

    1. 先输出当前节点（初始的时候是root节点）
    2. 如果当前节点的左子节点不为空，则递归继续前序遍历
    3. 如果当前节点的右子节点不为空，则递归继续前序遍历

  3. 中序遍历：先遍历左子树，再输出父节点，再遍历右子树

    1. 如果当前节点的左子节点不为空，则递归继续中序遍历
    2. 输出当前节点
    3. 如果当前节点的右子节点不为空，则递归继续中序遍历

  4. 后序遍历：先遍历左子树，在遍历右子树，最后输出父节点

    1. 如果当前节点的左子节点不为空，则递归继续后序遍历
    2. 如果当前节点的右子节点不为空，则递归继续后序遍历
    3. 输出当前节点

总结：看输出父节点的顺序，就确定是前中后序

代码

就跟链表一个路子，单链表每个节点指向一个next，二叉树每个节点指向两个节点left和right

  1. using System;
  2. using System.Collections.Generic;
  3. using System.Text;
  5. namespace ConsoleApp1
  6. {
  7.     public class BinaryTree
  8.     {
  9.         public BTNode root;
  11.         //前序遍历
  12.         public void preOrder()
  13.         {
  14.             if (this.root != null)
  15.                 this.root.preOrder();
  16.             else
  17.                 Console.WriteLine("当前二叉树为空");
  18.         }
  20.         //中序遍历
  21.         public void infixOrder()
  22.         {
  23.             if (this.root != null)
  24.                 this.root.infixOrder();
  25.             else
  26.                 Console.WriteLine("当前二叉树为空");
  27.         }
  29.         //后序遍历
  30.         public void postOrder()
  31.         {
  32.             if (this.root != null)
  33.                 this.root.postOrder();
  34.             else
  35.                 Console.WriteLine("当前二叉树为空");
  36.         }
  37.     }
  39.     //二叉树节点
  40.     public class BTNode
  41.     {
  42.         public int id;
  43.         public string name;
  44.         public BTNode left;
  45.         public BTNode right;
  46.         public BTNode(int id,string name)
  47.         {
  48.             this.id = id;
  49.             this.name = name;
  50.         }
  52.         //前序遍历
  53.         public void preOrder()
  54.         {
  55.             //1.先输出当前节点
  56.             Console.WriteLine(this.id+this.name);
  57.             //2.如果当前节点的左子节点不为空,则递归继续前序遍历
  58.             if (this.left != null)
  59.                 this.left.preOrder();
  60.             //3.如果当前节点的右子节点不为空,则递归继续前序遍历
  61.             if (this.right != null)
  62.                 this.right.preOrder();
  63.         }
  65.         //中序遍历
  66.         public void infixOrder()
  67.         {
  68.             //1.如果当前节点的左子节点不为空，则递归继续中序遍历
  69.             if (this.left != null)
  70.                 this.left.infixOrder();
  71.             //2.输出当前节点
  72.             Console.WriteLine(this.id+this.name);
  73.             //3.如果当前节点的右子节点不为空,则递归继续中序遍历
  74.             if (this.right != null)
  75.                 this.right.infixOrder();
  76.         }
  78.         //后续遍历
  79.         public void postOrder()
  80.         {
  81.             //1.如果当前节点的左子节点不为空，则递归继续后序遍历
  82.             if (this.left != null)
  83.                 this.left.postOrder();
  84.             //2.如果当前节点的右子节点不为空，则递归继续后序遍历
  85.             if (this.right != null)
  86.                 this.right.postOrder();
  87.             //3.输出当前节点
  88.             Console.WriteLine(this.id+this.name);
  89.         }
  90.     }
  91. }

查找节点

代码

思路就跟前中后序遍历大致相同，不过找到就返回，要注意，比如我左边节点返回了，就要在它执行下一段代码的时候判断有没有找到数据，如果找到了，不用执行另外分支的递归了，直接返回。如果没有这个判断的话，哪怕前面分支已经找到了结果，依旧去找后面的分支。两递归函数也不要用else if判断，哪怕一条分支返回为null，只能说明这条分支没找到，还有其他的分支呢，用else if其他的分支直接不执行了

  1. using System;
  2. using System.Collections.Generic;
  3. using System.Text;
  5. namespace ConsoleApp1
  6. {
  7.     public class BinaryTree
  8.     {
  9.         public BTNode root;
  11.         public void preOrder(){};//前序遍历
  12.         public void infixOrder(){}//中序遍历
  13.         public void postOrder(){};//后序遍历
  15.         //前序查找
  16.         public BTNode preFind(int id)
  17.         {
  18.             if (root != null)
  19.                 return this.root.preFind(id);
  20.             else
  21.                 throw new Exception("二叉树为空");
  22.         }
  23.         //中序查找
  24.         public BTNode infixFind(int id)
  25.         {
  26.             if (root != null)
  27.                 return this.root.infixFind(id);
  28.             else
  29.                 throw new Exception("二叉树为空");
  30.         }
  31.         //后序查找
  32.         public BTNode postFind(int id)
  33.         {
  34.             if (root != null)
  35.                 return this.root.postFind(id);
  36.             else
  37.                 throw new Exception("二叉树为空");
  38.         }
  39.     }
  41.     public class BTNode
  42.     {
  43.         public int id;
  44.         public string name;
  45.         public BTNode left;
  46.         public BTNode right;
  47.         public BTNode(int id,string name)
  48.         {
  49.             this.id = id;
  50.             this.name = name;
  51.         }
  54.         public void preOrder(){};//前序遍历
  55.         public void infixOrder(){};//中序遍历
  56.         public void postOrder(){};//后续遍历
  58.         //前序查找
  59.         public BTNode preFind(int id)
  60.         {
  61.             //1.定义一个辅助节点，这个节点用来装递归的结果，默认为null，如果都没有找到就返回默认的
  62.             BTNode temp = null;
  63.             //2.先比较当前节点，如果找到了就返回
  64.             if (this.id == id)
  65.                 return this;
  67.             //3.没找到就前序查找左节点
  68.             if (this.left != null)
  69.                 temp = this.left.preFind(id);
  70.             //3.1.只要找到了这个节点，temp不为空了就立马返回
  71.             if (temp != null)
  72.                 return temp;
  74.             //4.右边节点也前序查找
  75.             if (this.right != null)
  76.                 temp = this.right.preFind(id);
  77.             if (temp != null)
  78.                 return temp;
  80.             //5.都没找到说明真没有这个要查找的值，返回temp，默认值为null
  81.             return temp;
  82.         }
  84.         //中序查找
  85.         public BTNode infixFind(int id)
  86.         {
  87.             //中序遍历一样的思路，前序查找一样的写法
  88.             BTNode temp = null;
  89.             if (this.left != null)
  90.                 temp = this.left.infixFind(id);
  91.             if (temp != null)
  92.                 return temp;
  94.             if (this.id == id)
  95.                 return this;
  97.             if (this.right != null)
  98.                 temp = this.right.infixFind(id);
  99.             if (temp != null)
  100.                 return temp;
  101.             return temp;
  102.         }
  104.         //后序查找
  105.         public BTNode postFind(int id)
  106.         {
  107.             //如上
  108.             BTNode temp = null;
  109.             if (this.left != null)
  110.                 temp = this.left.postFind(id);
  111.             if (temp != null)
  112.                 return temp;
  114.             if (this.right != null)
  115.                 temp =  this.right.postFind(id);
  116.             if (temp != null)
  117.                 return temp;
  118.             if (this.id == id)
  119.                 return this;
  121.             if (this.id == id)
  122.                 return this;
  123.             return temp;
  124.         }
  127.     }
  128. }

删除节点

思路

  1. 因为这个二叉树是单向的，所以我们要判断当前节点的子节点是否需要被删除，而不是判断当前节点，和单链表删除一样
  2. 当前节点的子节点又分为左右两个子节点，需要都判断左子节点和右子节点是不是这个要被删除的节点，如果是，就把当前节点对应的子节点赋值为null，然后返回（结束递归）
  3. 如果第2步没有删除节点，就继续向左子数递归删除
  4. 如果第2步也没有删除节点，则应当向右子树进行递归删除

    代码

    ```csharp using System; using System.Collections.Generic; using System.Text;

namespace ConsoleApp1 { public class BinaryTree { public BTNode root;

  1.     public void preOrder(){};//前序遍历
  2.     public void infixOrder(){};//中序遍历
  3.     public void postOrder(){};//后序遍历
  4.     public BTNode preFind(int id){};//前序查找
  5.     public BTNode infixFind(int id){};//中序查找
  6.     public BTNode postFind(int id){};//后序查找
  8.     //删除节点
  9.     public void delNode(int id)
  10.     {
  11.         if (root != null)
  12.         {
  13.             if (root.id == id)
  14.             {
  15.                 root = null;
  16.                 return;
  17.             }
  18.             else
  19.             {
  20.                 root.delNode(id);
  21.             }
  22.         }
  23.         else
  24.         {
  25.             Console.WriteLine("空树");
  26.         }
  27.     }
  28. }
  29. public class BTNode
  30. {
  31.     public int id;
  32.     public string name;
  33.     public BTNode left;
  34.     public BTNode right;
  35.     public BTNode(int id, string name)
  36.     {
  37.         this.id = id;
  38.         this.name = name;
  39.     }
  41.     public void preOrder(){};//前序遍历
  42.     public void infixOrder(){};//中序遍历
  43.     public void postOrder(){};//后序遍历
  44.     public BTNode preFind(int id){};//前序查找
  45.     public BTNode infixFind(int id){};//中序查找
  46.     public BTNode postFind(int id){};//后序查找
  48.     //删除节点
  49.     public void delNode(int id)
  50.     {
  51.         if (this.left != null && this.left.id == id)
  52.         {
  53.             this.left = null;
  54.             return;
  55.         }
  56.         if (this.right != null && this.right.id == id)
  57.         {
  58.             this.right = null;
  59.             return;
  60.         }
  62.         //当前节点的左右节点都不是要删除的节点，就要向左右树递归删除
  63.         if (this.left != null)
  64.         {
  65.             this.left.delNode(id);
  66.         }
  67.         if (this.right != null)
  68.         {
  69.             this.right.delNode(id);
  70.         }
  71.     }
  73. }

}

  1. <a name="qaLkk"></a>
  2. # 顺序存储二叉树
  3. 从数据存储来看，数组存储方式和树的存储方式可以相互转换，即数组可以转换成树，树也可以转换成数组。<br />可以用二叉树前中后序遍历的方式遍历数组。
  5. 顺序存储二叉树有如下特点
  7. 1. 顺序存储二叉树只考虑完全二叉树
  8. 1. 第n个元素的左子节点为`2*n+1`
  9. 1. 第n个元素的右子节点为`2*n+2`
  10. 1. 第n个元素的父节点为`(n-1)/2`
  11. 1. n表示二叉树中第几个元素，从0开始（为了跟数组保持一致）
  13. ![image.png](https://cdn.nlark.com/yuque/0/2022/png/21464164/1644979413555-3071da35-bff8-4663-ada0-63392d6f4a07.png#clientId=u3daa3f58-8541-4&crop=0&crop=0&crop=1&crop=1&from=paste&height=335&id=uac5e9af3&margin=%5Bobject%20Object%5D&name=image.png&originHeight=553&originWidth=760&originalType=binary&ratio=1&rotation=0&showTitle=true&size=37756&status=done&style=none&taskId=u3c41491c-9a06-4fca-9323-59e1e93bc69&title=%E9%A1%BA%E5%BA%8F%E5%AD%98%E5%82%A8%E4%BA%8C%E5%8F%89%E6%A0%91&width=460.60603398374883 "顺序存储二叉树")<br />上图对应的数组就是`[1,2,3,4,5,6,7]`
  14. <a name="bewHh"></a>
  15. ## 代码
  16. ```csharp
  17. using System;
  18. using System.Collections.Generic;
  19. using System.Text;
  21. namespace ConsoleApp1
  22. {
  23.     public class ArrayBinaryTree
  24.     {
  25.         int[] array = null;
  26.         public ArrayBinaryTree(int[] array)
  27.         {
  28.             this.array = array;
  29.         }
  31.         //前序
  32.         public void preOrder(int index)
  33.         {
  34.             if (array == null || array.Length == 0)
  35.             {
  36.                 Console.WriteLine("数组为空");
  37.                 return;
  38.             }
  39.             //1.输出当前元素
  40.             Console.WriteLine(array[index]);
  42.             //2.向左递归遍历
  43.             if (2 * index + 1 < array.Length)
  44.                 preOrder(2 * index + 1);
  46.             //3.向右递归遍历
  47.             if (2 * index + 2 < array.Length)
  48.                 preOrder(2 * index + 2); 
  49.         }
  51.         //中序
  52.         public void infixOrder(int index)
  53.         {
  54.             if (array == null || array.Length == 0)
  55.             {
  56.                 Console.WriteLine("数组为空");
  57.                 return;
  58.             }
  60.             if (2 * index + 1 < array.Length)
  61.                 infixOrder(2 * index + 1);
  63.             Console.WriteLine(array[index]);
  65.             if (2 * index + 2 < array.Length)
  66.                 infixOrder(2 * index + 2);
  67.         }
  69.         //后序
  70.         public void postOrder(int index)
  71.         {
  72.             if (array == null || array.Length == 0)
  73.             {
  74.                 Console.WriteLine("数组为空");
  75.                 return;
  76.             }
  78.             if (2 * index + 1 < array.Length)
  79.                 postOrder(2 * index + 1);
  81.             if (2 * index + 2 < array.Length)
  82.                 postOrder(2 * index + 2);
  84.             Console.WriteLine(array[index]);
  85.         }
  86.     }
  87. }

线索二叉树

线索化二叉树思路

n个节点的二叉树中含有n+1个（公式2n-(n-1)=n+1）个空指针域。利用二叉树中这些空指针域，存放指向该节点在某种遍历次序下的前驱和后继节点指针（这种附加的指针称为 “线索”）。
image.png
这种加上了线索的二叉树称为线索二叉树。根据线索性质的不同，线索二叉树可以分为前序线索二叉树，中序线索二叉树，和后序线索二叉树三种。

一个节点的前一个节点，称为前驱节点。
一个节点的有一个结点，称为后继节点。

如上图的二叉树，3，4，5，6节点的指针域并没有使用完。3的右子节点为空，4，5，6的左右节点都为空，所以空的指针节点有7个。
根据上图公式2n-(n-1)=n+1得到 2*6-(6-1)=6+1=7
image.png

根据中序遍历，结果为4，2，5，1，6，3 输出4后，下一个节点应该是输出2，这时候就用4的右指针指向2（2是4的后继节点）。这时候4的左指针还是空的，4是第一个输出，因此没有前驱节点。 5的后继节点是1，就用5的右指针指向1，而5的左指针还是空的，就指向前驱节点2。 6的后继节点是3，右指针指向3，左指针是空的，就指向6的前驱节点1。 3没有后继节点，左指针又不为空，就不动。 以此类推。这就是附加线索

这里举例是前序，中后序同理。

说明：当线索化二叉树后节点的left和right有如下情况。

  1. left指向的是左子树，也有可能指向前驱节点，如上图，1节点的left就指向左子树，而4节点的left指向的就是前驱节点
  2. right指向的是右子数，也有可能指向后继节点，如上图，1节点的right就指向右子树，而4节点的right指向的就是后继节点

因此需要给每个节点的left和right设置一个属性，来判断他是子树还是线索节点

线索化代码

  1. using System;
  2. using System.Collections.Generic;
  3. using System.Text;
  5. namespace ConsoleApp1
  6. {
  7.     public class ThreadedBinaryTree
  8.     {
  9.         public TBTNode root;
  10.         //为了实现线索化，需要创建要给指向当前节点的前驱节点的指针
  11.         //在递归进行线索化时，pre总是保留前一个节点
  12.         public TBTNode pre;
  14.         //前序线索化二叉树
  15.         public void preThreadedNodes(TBTNode node)
  16.         {
  17.             //思路如中序线索化
  18.             if (node == null)
  19.                 return;
  21.             if (node.left == null)
  22.             {
  23.                 node.left = pre;
  24.                 node.lefttype = 1;
  25.             }
  26.             if (pre != null && pre.right == null)
  27.             {
  28.                 pre.right = node;
  29.                 pre.righttype = 1;
  30.             }
  31.             pre = node;
  32.             if(node.lefttype==0)
  33.                 preThreadedNodes(node.left);
  34.             if(node.righttype==0)
  35.                 preThreadedNodes(node.right);
  36.         }
  38.         //中序线索化二叉树，node就是需要线索化的节点
  39.         public void infixThreadedNodes(TBTNode node)
  40.         {
  41.             if (node == null)//不能线索化
  42.                 return;
  44.             //(一).先线索化左子树
  45.             infixThreadedNodes(node.left);
  46.             //(二).线索化当前节点
  48.             //先处理当前节点的前驱节点
  49.             if (node.left == null)
  50.             {
  51.                 node.left = pre;//让当前节点的左指针指向前驱节点
  52.                 node.lefttype = 1;//修改当前结点的左指针类型，指向前驱节点
  53.             }
  54.             //处理后继节点，其实是在下次递归的时候处理当前节点的后继节点
  55.             //也就是说当前这次是处理上一节点的后继节点与当前节点的前驱节点
  56.             if(pre!= null && pre.right==null)
  57.             {
  58.                 pre.right = node;//让前驱节点的右指针指向当前节点
  59.                 pre.righttype = 1;//修改前驱节点的右指针类型
  60.                 //这样就处理好了 上一个节点 的后继节点
  61.             }
  63.             pre = node;//前一个节点进行迭代
  65.             //(三).线索化右子树
  66.             infixThreadedNodes(node.right);
  67.         }
  69.         //后序线索化二叉树
  70.         public void postThreadedNodes(TBTNode node)
  71.         {
  72.             if (node == null)
  73.                 return;
  74.             postThreadedNodes(node.left);
  75.             postThreadedNodes(node.right);
  76.             if (node.left == null)
  77.             {
  78.                 node.left = pre;
  79.                 node.lefttype = 1;
  80.             }
  81.             if (pre != null && pre.right == null)
  82.             {
  83.                 pre.right = node;
  84.                 pre.righttype = 1;
  85.             }
  86.             pre = node;
  87.         }
  88.     }
  89.     public class TBTNode
  90.     {
  91.         public int id;
  92.         public string name;
  93.         public TBTNode left;
  94.         public TBTNode right;
  95.         //说明
  96.         //1.如果lefttype==0，表示指向的是左子树，如果1表示指向前驱节点
  97.         //2.如果righttype==0，表示指向是右子树，如果1表示指向后继节点
  98.         public int lefttype;
  99.         public int righttype;
  100.         public TBTNode(int id, string name)
  101.         {
  102.             this.id = id;
  103.             this.name = name;
  104.         }
  106.     }
  107. }

遍历线索化二叉树

因为线索化了之后，各个节点指向有变化，因此原来的遍历方式不能使用，这时需要使用新的方式遍历线索化二叉树，各个节点可以通过线型方式遍历，因此无需使用递归方式，这样提高了遍历的效率。遍历的次序和使用的线性化的次序一致。

遍历线索化二叉树代码

需要注意的是，后序遍历线索二叉树，需要每个节点添加一个父节点，在创建二叉树时每个节点就指向了父节点

  1. using System;
  2. using System.Collections.Generic;
  3. using System.Text;
  5. namespace ConsoleApp1
  6. {
  7.     public class ThreadedBinaryTree
  8.     {
  9.         public TBTNode root;
  10.         //为了实现线索化，需要创建要给指向当前节点的前驱节点的指针
  11.         //在递归进行线索化时，pre总是保留前一个节点
  12.         public TBTNode pre;
  15.         public void preThreadedNodes(TBTNode node){};//前序线索化二叉树
  16.         public void infixThreadedNodes(TBTNode node){};//中序线索化二叉树
  17.         public void postThreadedNodes(TBTNode node){};//后序线索化二叉树
  19.         //前序遍历线索二叉树
  20.         public void preThreadedList()
  21.         {
  22.             TBTNode node = root;
  23.             while (node != null)
  24.             {
  25.                 //前序遍历，先输出当前节点
  27.                 //如果lefttype==0，说明left是左子树
  28.                 while (node.lefttype == 0)
  29.                 {
  30.                     Console.WriteLine(node.id + node.name);
  31.                     node = node.left;
  32.                 }
  34.                 Console.WriteLine(node.id + node.name);
  35.                 node = node.right;
  36.             }
  37.         }
  39.         //中序遍历线索二叉树
  40.         public void infixThreadedList()
  41.         {
  42.             //定义一个变量，存储当前遍历的结点，从root开始
  43.             TBTNode node = root;
  44.             while (node != null)
  45.             {
  46.                 //循环的找到lefttype==1的节点
  47.                 //因为是中序遍历，左边的节点先输出
  48.                 //所以第一个输出的节点本身指针为null，线索化后，lefttype==1，该节点是按照线索化处理的有效节点
  49.                 while (node.lefttype==0)
  50.                 {
  51.                     node = node.left;
  52.                 }
  54.                 Console.WriteLine(node.id+node.name);
  56.                 //如果当前节点的右指针指向的是后继节点就一直输出
  57.                 while (node.righttype == 1)
  58.                 {
  59.                     //改变当前节点为下一个节点
  60.                     node = node.right;
  61.                     Console.WriteLine(node.id+node.name);
  62.                 }
  63.                 //退出了上面的循环，就说明遇到了下一个节点不是后继节点的节点，直接替换它
  64.                 node = node.right;
  65.             }
  66.         }
  68.         //后序遍历线索二叉树
  69.         public void postThreadedList()
  70.         {
  72.             TBTNode node = root;
  73.             TBTNode pre = null;
  74.             //后序的第一个值是左边的叶子节点，所以当lefttype==1时，说明这个节点就是第一个输出的点，用循环先定位到这个点
  75.             while (node != null&&node.lefttype == 0)
  76.             {
  77.                 node = node.left;
  78.             }
  80.             //然后开始遍历节点
  81.             while (node != null)
  82.             {
  83.                 //如果当前节点有后继节点
  84.                 if (node.righttype == 1)
  85.                 {
  86.                     Console.WriteLine(node.id + node.name);
  87.                     pre = node;
  88.                     node = node.right;
  89.                 }
  90.                 else//没有后继节点，想象三角形顶上的那个点，左右节点都是子节点
  91.                 {
  92.                     //如果上一个处理的节点是当前节点的右节点（当前节点来到了三角形的顶端节点，想想后序遍历的顺序）
  93.                     if (pre == node.right)
  94.                     {
  95.                         Console.WriteLine(node.id+node.name);
  96.                         if (node == root)//根节点是后序遍历的最后一个点
  97.                             return;
  98.                         pre = node;
  99.                         node = node.parent;//往父节点迭代
  100.                     }
  101.                     else//已经退回了root节点，上一个处理的节点不是当前节点(root)的右节点
  102.                     {
  103.                         //开始往根节点的右边遍历
  104.                         node = node.right;
  105.                         //同样的找到最左边的点开始
  106.                         while (node != null && node.lefttype == 0)
  107.                         {
  108.                             node = node.left;
  109.                         }
  110.                     }
  111.                 }
  112.             }
  113.         }
  114.     }
  115.     public class TBTNode
  116.     {
  117.         public int id;
  118.         public string name;
  119.         public TBTNode left;
  120.         public TBTNode right;
  121.         public TBTNode parent;//当前节点的父节点，用于后序遍历线索二叉树
  122.         //说明
  123.         //1.如果lefttype==0，表示指向的是左子树，如果1表示指向前驱节点
  124.         //2.如果righttype==0，表示指向是右子树，如果1表示指向后继节点
  125.         public int lefttype;
  126.         public int righttype;
  127.         public TBTNode(int id, string name)
  128.         {
  129.             this.id = id;
  130.             this.name = name;
  131.         }
  133.     }
  134. }

前中后序遍历线索二叉树比较

  1. 前序线索化二叉树遍历相对最容易理解，实现起来也比较简单。由于前序遍历的顺序是：根左右，所以从根节点开始，沿着左子树进行处理，当子节点的left指针类型是线索时，说明到了最左子节点，然后处理子节点的right指针指向的节点，可能是右子树，也可能是后继节点，无论是哪种类型继续按照上面的方式（先沿着左子树处理，找到子树的最左子节点，然后处理right指针指向），以此类推，直到节点的right指针为空，说明是最后一个，遍历完成。

  2. 中序线索化二叉树的网上相关介绍最多。中序遍历的顺序是：左根右，因此第一个节点一定是最左子节点，先找到最左子节点，依次沿着right指针指向进行处理（无论是指向子节点还是指向后继节点），直到节点的right指针为空，说明是最后一个，遍历完成。

  3. 后序遍历线索化二叉树最为复杂，通用的二叉树数节点存储结构不能够满足后序线索化，因此我们扩展了节点的数据结构，增加了父节点的指针。后序的遍历顺序是：左右根，先找到最左子节点，沿着right后继指针处理，当right不是后继指针时，并且上一个处理节点是当前节点的右节点，则处理当前节点的右子树，遍历终止条件是：当前节点是root节点，并且上一个处理的节点是root的right节点。