二叉树的遍历和线索二叉树--中序线索二叉树的遍历

张开发
• 2026/4/21 5:22:45 • 15 分钟阅读

最新文章

推荐文章

相关文章

分享文章

二叉树的遍历和线索二叉树--中序线索二叉树的遍历
一、遍历特点1. 不需要递归2. 不需要栈3. 顺着线索指针依次访问4. 遍历顺序依然左 → 根 → 右二、先回顾结点标记- ltag 0left 是左孩子- ltag 1left 是前驱线索- rtag 0right 是右孩子- rtag 1right 是后继线索三、遍历完整步骤步骤1找到中序遍历第一个结点从根出发一直向左走只要 ltag 0 就继续左走走到不能左走为止就是最左下结点→ 中序第一个访问结点步骤2访问当前结点输出当前结点数据步骤3找当前结点的后继结点分两种情况1. rtag 1右指针是线索直接 p p.right 就是后继2. rtag 0右指针是右孩子进入右子树继续往左走到最底端那个结点就是后继步骤4循环重复 2、3 步直到 p null 结束四、遍历口诀找首结点一路向左到底访问结点直接打印找后继- 右是线索 → 直接跳- 右是孩子 → 右子树向左到底五、Java 完整遍历代码//中序线索二叉树遍历非递归、不用栈 public void inThreadTraverse(ThreadNode p) { if(p null) return; //1. 找中序第一个结点最左下 while(p.ltag 0){ p p.left; } //2. 循环遍历所有结点 while(p ! null){ System.out.print(p.data ); //判断后继 if(p.rtag 1){ //右是线索直接后继 p p.right; }else{ //右是孩子进入右子树找最左下 p p.right; while(p.ltag 0){ p p.left; } } } }六、总结1. 中序线索树遍历空间复杂度 O(1)2. 普通二叉树非递归遍历空间 O(h)栈3. 叶子结点左右全是线索直接顺着走就行4. 第一个结点整树最左下5. 最后一个结点整树最右下右线索指向 null6. 循环线索二叉树首尾相连不会为空七、构造 遍历对比一句话-构造线索树中序遍历 pre 绑定空指针-遍历线索树不用栈递归顺着前驱后继线索走

更多文章