本文共 2103 字,大约阅读时间需要 7 分钟。
采用递归地调用的方式,判定条件是当前指针的左子树是否为空
代码实现:public void midOrder() { if (this.left != null) { this.left.midOrder(); } System.out.println(this); if (this.right != null) { this.right.midOrder(); } }
对比:
但是对二叉树进行线索化之后,不存在空的左右指针,但是单独设置每一个指针的类型,故而条件修改为指针的类型。public void midLIst(){ if (this.getLeftType() != 1){ this.getLeft().midLIst(); } System.out.print(this + " "); if (this.getRightType() != 1){ this.getRight().midLIst(); } }
问题分析与总结:
public void midLIst(){ if (this.getLeftType() != 1){ this.getLeft().midLIst(); } if (this != null){ System.out.println(this + " "); } if (this.getRightType() != 1 && this.getRight() != null){ this.getRight().midLIst(); } }
分析与总结:
针对最尾结点的情况进行修改,尾节点的右指针始终为空,增加判定条件即可思路实现:
因为二叉树线索化之后,每一个叶子结点的左右指针都将整个二叉树按照对应的顺序链接起来了,所以就可以按照线索化之后的连接彼此的指针进行遍历 代码实现:public void threadList(){ //代码终止的条件是找到了对应的空指针 HeroArragement hero = root; while (hero != null){ //中序遍历,先找到左边的最初的结点 while (hero.getLeftType() == 0){ hero = hero.getLeft(); } //退出循环就是当前的最左边的节点,并且打印当前节点 System.out.println(hero); //然后开始判定总共是两种情况,一种左右结点不为空,另一种是左右节点为空 //如果是左右都不为后继节点,而是对应的子树 //如果是左右都是后继节点,直接输出 while (hero.getRightType() == 1){ //获取到当前节点的后后继节点,因为当前节点已经输出过了 hero = hero.getRight(); System.out.println(hero); } hero = hero.getRight(); }
while(hero.getLeftType() == 0){ hero = hero.getLeft(); }
while(hero.getLeftType() == 1){ hero = hero.getLeft(); System.out.println(hero); }hero = hero.getRight();
转载地址:http://tqgpb.baihongyu.com/