最常见的软件工程师面试题(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 node
	static 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 BTree

	public 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();
	}
}