最常见的程序员面试题(7)二叉树转链表

二叉树通过遍历可以用于转化成一个链表(插入构建链表)。但是如果没有而外的链表呢? 这就用到"线索化二叉树"，也就是一个二叉树(可以是排序二叉树)在座遍历(例如中序)的时候，去更新每个节点的"前驱"和"后继"的节点关系，得到一个二叉链表。然后从最左节点开始，遍历所有的"后继"节点，就得到一个二叉链表的所有数据。分别用C++和Java来实现。

#include<functional>using namespace std;template<class Comp>class node{    size_t data;    node* pLeft;    node* pRight;    bool lTag;//true表示node*pLeft/pRight是线索,false表示指针    bool rTag;public:    node( size_t d ):        data(d),        pLeft(nullptr),        pRight(nullptr),        lTag(true),        rTag(true)    {}    void append( node* p ){        if( Comp()( p->data, data ) ){            appendLeft( p );        }else{            appendRight( p );        }    }    void appendLeft( node* p ){        if( pLeft == nullptr ){            pLeft = p;        }else{            pLeft->append( p );        }        lTag=false;    }    void appendRight( node* p ){        if( pRight == nullptr ){            pRight = p;        }else{            pRight->append( p );        }        rTag=false;    }    ~node(){        if(pLeft && (lTag==false))delete pLeft;        if(pRight&& (rTag==false))delete pRight;    }    void printTree(){//中序遍历打印        if(pLeft)pLeft->printTree();        printf("%d,",data);        if(pRight)pRight->printTree();    }    void ToThreadedBinarytree(){//中序线索2叉树        static node* pre=nullptr;        if(pLeft){            pLeft->ToThreadedBinarytree();        }else{            pLeft=pre;            lTag=true;        }        if(pre){            if(pre->pRight==nullptr){                pre->pRight=this;                pre->rTag=true;            }                 }        pre=this;        if(pRight){            pRight->ToThreadedBinarytree();        }    }    void printList(){        node*p=this;        while(p->pLeft && (p->lTag==false)){            p=p->pLeft;        }//找到当前树的最左节点        p->printThreaded();    }    void printThreaded(){//寻找后继结点并打印        printf("%d,",data);        if(rTag){            if(pRight)pRight->printThreaded();        }else{            if(pRight)pRight->printList();        }    }};template<class T>struct sortedTree{    node<T>* pRoot;    sortedTree():pRoot(nullptr){}    ~sortedTree(){if(pRoot)delete pRoot;}    void append( size_t n ){        node<T>* p=new node<T>(n);        if( pRoot == nullptr ){            pRoot = p;        }else{            pRoot->append( p );        }    }    void printTree(){        if(pRoot)pRoot->printTree();    }    void convertList(){        if(pRoot){            pRoot->ToThreadedBinarytree();            printf("\n");            pRoot->printList();        }    }};int main(int argc, char* const argv[]){    sortedTree< less<size_t> > tree;    tree.append( 3 );    tree.append( 7 );    tree.append( 4 );    tree.append( 2 );    tree.append( 5 );    tree.append( 1 );    tree.append( 6 );    tree.printTree();    printf("\n");    tree.convertList();//打印线索化的二叉树    printf("\n");    return 0;}

public class TreeToList{static class node{node pLeft;node pRight;boolean lTag;//true代表是线索boolean rTag;int data;node(int d){data=d;pLeft=null;pRight=null;lTag=false;rTag=false;}void append(node n){if(data>n.data){appendLeft(n);}else{appendRight(n);}}void appendLeft(node n){if(pLeft==null){pLeft=n;}else{pLeft.append(n);}lTag=false;}void appendRight(node n){if(pRight==null){pRight=n;}else{pRight.append(n);}rTag=false;}void printNode(){if(pLeft !=null){pLeft.printNode();}System.out.println(","+data);if(pRight!=null){pRight.printNode();}}static node pre;static{pre=null;}void ToThreadedBinaryTree(){if(pLeft!=null){pLeft.ToThreadedBinaryTree();}else{pLeft=pre;lTag=true;}if(pre!=null){if(pre.pRight==null){pre.pRight=this;pre.rTag=true;}}pre=this;if(pRight!=null){pRight.ToThreadedBinaryTree();}}void printList(){node p=this;while(p.pLeft!=null && p.lTag==false){p=p.pLeft;}//找到当前树的最左节点p.printThreaded();}void printThreaded(){System.out.println(","+data);if(rTag){if(pRight!=null){pRight.printThreaded();}}else{if(pRight!=null){pRight.printList();}}}}//end class nodestatic class BTree{node pRoot;void append(node n){if(pRoot==null){pRoot=n;}else{pRoot.append(n);}}void printTree(){if(pRoot!=null){pRoot.printNode();}}void convertList(){if(pRoot!=null){pRoot.ToThreadedBinaryTree();pRoot.printList();}}}//end class BTreepublic static void main(String[] args) {BTree t=new BTree();t.append(new node(3));t.append(new node(7));t.append(new node(4));t.append(new node(2));t.append(new node(5));t.append(new node(1));t.append(new node(6));t.printTree();System.out.println("========");t.convertList();}}