木の遍歴と実現

最近はデータ構造の知識をまとめたいので、いくつかの文章を書いて記録することにしました.
    木の遍歴は三つの種類に分けられています.まず、中順に遍歴し、後順に遍歴します.私にとっては、次の3つの方法を理解しています.再帰的に、スタックを利用して、Morris遍歴(よりクールな方法)です.(本論文ではjava言語を使用して実現する)
    簡単な再帰実現から始めましょう.

//    
public void preorderRecursion(TreeNode root){
        doSomething(root);
        if(root.left!=null)
            preorderRecursion(root.left);
        if(root.right!=null)
            preorderRecursion(root.right);
    }

//    
public void inorderRecursion(TreeNode root){
        if(root.left!=null)
            inorderRecursion(root.left);
        doSomething(root);
        if(root.right!=null)
            inorderRecursion(root.right);
    }

//    
public void postorderRecursion(TreeNode root){
        if(root.left!=null)
            postorderRecursion(root.left);
        if(root.right!=null)
            postorderRecursion(root.right);
        doSomething(root);
    }

再帰的な実現は非常に簡単で、doSomethingの順序を変更するだけでいいです.
再帰的に順を追ってエルゴードする思想を実現するのは、まずpreorders Recursionを木の順序を実現する関数と見なしています.
1.rootノードdoSomething
2.rootの左の木を先に遍歴します.
3.rootの右子樹を先に遍歴する
次にスタックを利用してエルゴードを実現します.

//    
public void preorderStack(TreeNode root){
        Stack s = new Stack();
        preorderStackSupport(root,s);
        TreeNode temp;
        while(!s.empty())
        {
            temp = (TreeNode)s.pop();
            if(temp.right!=null)
                preorderStackSupport(temp.right,s);
        }
    }
    public void preorderStackSupport(TreeNode root,Stack s){
        while(root.left!=null)
        {
            doSomething(root);
            s.push(root);
            root = root.left;
        }
        doSomething(root);
        s.push(root);
    }

補助関数の役割は、着信結点を左の息子の方向のすべての結点に沿って対応する処理をスタックに組み込むことであり、このプロセスは親の結点->左の息子の順序を保証する.
補助関数を呼び出した後、スタックは親ノードの左の息子の順に処理された最初のバッチの要素を持っています.この時、スタックの一番上はルートの一番左の息子です.スタックの一番上の左の息子は空ですので、もう親ノードの左の息子の順番で進められません.だから、スタックの一番上の右の息子に補助関数を呼び出します.

//    
public void inorderStack(TreeNode root) {
        Stack s = new Stack();
        inorderStackSupport(root,s);
        TreeNode temp;
        while(!s.empty())
        {
            temp = (TreeNode)s.pop();
            doSomething(temp);
            if(temp.right!=null)
                inorderStackSupport(temp.right,s);
        }
    }
    public void inorderStackSupport(TreeNode root,Stack s){
        while(root.left!=null)
        {
            s.push(root);
            root = root.left;
        }
        s.push(root);
    }

補助関数の役割は、入力された接合点を左の息子の方向に沿ってすべての接合点をスタックに入れることであり、スタックの特性から、親ノードは息子のノードの下にあることを知る.
補助関数を呼び出した後、スタックは、最初のバッチを親ノード->の左の息子順にスタックに入る要素があります.すると、スタックを出る時は左の息子->親ノードです.この時、スタックの一番上はルートの一番左の息子です.最初の巡回とは違って、スタックの要素はまだ対応していません.したがって、まずスタックのトップ要素に対応して処理してから、スタックの一番上の右の息子に補助関数を呼び出します.

//    
public void postorderStack(TreeNode root){
        Stack s = new Stack();
        postorderStackSupport(root,s);
        TreeNode temp,tempL;
        while(!s.empty())
        {
            temp = (TreeNode)s.peek();
            if(temp.right!=null)
                postorderStackSupport(temp.right,s);
            temp = (TreeNode)s.pop();
            doSomething(temp);
            tempL = (TreeNode)s.peek();
            if(temp == tempL.right)
            {
                doSomething(tempL);
                s.pop();
            }
        }
    }
    public void postorderStackSupport(TreeNode root,Stack s) {
        while(root.left!=null)
        {
            s.push(root);
            root = root.left;
        }
        s.push(root);
        while (root.right!= null)
        {
            root = root.right;
            while(root.left!=null)
            {
                s.push(root);
                root = root.left;
            }
            s.push(root);
        }
    }

後の順序は左の息子->右の息子->父の接合点ですので、補助関数はいくつかの変更が必要です.前の二つのタイプについてはルートノードを起点とし、親ノード->左の息子の順に、あるノードに左の息子がいないことを知るだけでいいです.しかし、現在はノードに左の息子がいないだけでなく、ノードに右の息子がいないことを求めています.そうでなければ、ノードは最初に処理すべきノードではないです.
補助関数の助けを借りて、私たちは後から順に要素をスタックに入れることに成功しましたが、無限にあるノードに補助関数を呼び出すことを防止するためには、スタックのノードが現在のスタックの一番上の右の息子かどうかを判断する必要があります.
Morris Traversal実現
前の二つのエルゴード方式はO(n)の空間を使用していますが、このエルゴード方式はO(1)の空間だけが必要です.(これがヤンキーの考え方かもしれません.)
アルゴリズムの考え方は、結点の前駆接合点を自身に向けることによって、木の遍歴を達成することである.実はなぜ前駆を利用してノードを作りますか?木は実は多くの一方向チェーンで構成されていますので、私たちは直接に息子の結点から父の結点にジャンプすることができません.前駆の結点を利用するのはこの問題を解決するテクニックです.

//    
public void preorderMorris(TreeNode root){
        TreeNode cur = root;
        TreeNode pre = null;
        while(cur!=null)
        {
            doSomething(cur);
            if(cur.left==null)
                cur = cur.right;
            else
            {
                pre = cur.left;
                while(pre.right!=null&&pre.right!=cur)
                    pre = pre.right;
                if(pre.right==null)
                {
                    pre.right = cur.right;
                    cur = cur.left;
                }
                else{
                    pre.right = null;
                    cur = cur.right;
                }
            }
        }
    }

先に遍歴中、前駆の結点は左の息子がnode->node.rightに沿っている最後の結点です.
1.まず出力してからにします.そして、左の息子が空かどうかを判断します.暇なら、前駆のノードがありません.
2.左の息子がいるなら、自分の前駆の結点を見つけたり、現在のノードを見つけたりします.
    a.前駆の結点が見つかったら、前駆の結点と現在のノードを接続して、現在の結点を現在の結点の左の息子に安心して置くことができます.(後は接続でこの結点に戻すことができます.)
    b.現在のノードが見つかったら、接続を解除して、現在の結点を現在の結点の右の息子として置く(接続されているので、現在の結点の左の木がすでに満遍なくなったということです)

//    
public void inorderMorris(TreeNode root){
        TreeNode cur = root;
        TreeNode pre = null;
        while(cur!=null)
        {
            if(cur.left==null)
            {
                doSomething(cur);
                cur = cur.right;
            }
            else
            {
                pre = cur.left;
                while(pre.right!=null&&pre.right!=cur)
                    pre = pre.right;
                if(pre.right==null)
                {
                    pre.right = cur;
                    cur = cur.left;
                }
                else{
                    pre.right = null;
                    doSomething(cur);
                    cur = cur.right;
                }
            }
        }
    }

においては、順遍歴と順遍歴との比較が似ているので、説明するまでもない.

//    
public void postorderMorris(TreeNode root){
        TreeNode htemp = new TreeNode(0);
        htemp.left = root;
        TreeNode cur = htemp;
        TreeNode pre = null;
        while(cur!=null)
        {
            if(cur.left==null)
                cur = cur.right;
            else
            {
                pre = cur.left;
                while(pre.right!=null&&pre.right!=cur)
                    pre = pre.right;
                if(pre.right==null)
                {
                    pre.right = cur;
                    cur = cur.left;
                }
                else{
                    printReverse(cur.left,pre);
                    pre.right = null;
                    cur = cur.right;
                }
            }
        }
    }
//      
public void printReverse(TreeNode from,TreeNode to) {
        reverse(from,to);
        TreeNode temp = to;
        while(temp!=from)
        {
            doSomething(temp);
            temp = temp.right;
        }
        doSomething(temp);
        reverse(from,to);
    }
//    
public void reverse(TreeNode from,TreeNode to){
        TreeNode x = from;
        TreeNode y = to;
        TreeNode z;
        while(x!=to)
        {
            z = y.right;
            y.right = x;
            x = y;
            y = z;
        }
    }

後続のエルゴードの実現は同様に複雑であり、チェーンテーブルを逆順序で出力するために、追加の結点httempと補助関数reversePrint()を借りる必要がある.
後に続く前駆の接合は、前の2つの遍歴と同じです.
1.現在のノードの左の息子が空かどうかを判断し、空欄であれば前駆結点がないと説明する.
2.左の息子が空でないなら、自分の前駆の結点を見つけたり、現在のノードを見つけたりします.
    a.前駆結点が見つかったら、前駆結点と現在のノードを接続し、現在の結点を現在の結点の左の息子とする.(左息子の最優先順位を保証しました)
    b.現在の結点自分が見つかったら、現在の結点の左の息子と前駆の結点の間の経路上のすべての結点を倒順に出力します.(右の息子->父の結点の順番を保証します.現在の結点を現在の結点の右の息子にします.
これでやっとまとめたと思いますが、なんだかまとまりがつかないような気がします.やはり理解が足りないからでしょう.