이 진 트 리 기본 조작 - 개인 총화

이 진 트 리: 각 노드 값 에 대해 트 리 를 반복 하지 않 습 니 다 (동시에 뒷 순 서 를 얻 습 니 다): (앞 순서 + 중간 순서 로 트 리 를 만 듭 니 다)

TreeNode* build( vector<int>pre , vector<int>in ) {
	if( !pre.size() || !in.size() ) {
		return NULL ;
	}
	TreeNode* rt = new TreeNode(pre[0]);
	for( int i = 0 ; i < in.size() ; i++ ) {
		if( in[i] == pre[0] ) {
			vector<int>p1( pre.begin() + 1 , pre.begin() + i + 1 );
			vector<int>v1( in.begin() , in.begin() + i ) ;
			rt->l = build( p1 , v1 );
			vector<int>p2( pre.begin() + i + 1 , pre.end() );
			vector<int>v2( in.begin() + i + 1 , in.end() ) ;
			rt->r = build( p2 , v2 );
			//res.push_back(rt->val);
			//         
			break ;
		}
	}
	return rt ;
}

두 갈래 나무의 깊이:

    int TreeDepth(TreeNode* rt){
        if( rt == NULL ) return 0 ; 
        return max( TreeDepth( rt -> left ) , TreeDepth( rt -> right ) ) + 1 ; 
    }

다음 코드 는 앞 순서 에 따라 나 무 를 만 들 고 재 귀적 버 전과 비 재 귀적 버 전의 앞, 중, 뒤 를 옮 겨 다 니 는 것 을 포함 합 니 다. 대학원 에 진학 할 때 쓴 것 이기 때문에 구조 체 는 비교적 비인간 적 입 니 다.창고 등 도 모두 시 뮬 레이 션 한 것 이다.

#include 
#include 
#define ElemType char
#define MaxSize 20 
using namespace std;
typedef struct BiTNode{
    ElemType data ;
    struct BiTNode  *lchild , *rchild ;
}BiTNode , *BiTree ;
typedef struct {
    BiTNode *data[MaxSize] ;
    int top ; 
}SqStack ; 

void InitStack( SqStack &s ){
    s.top = -1 ;
}

bool IsEmpty( SqStack s ){
    if( ~s.top ) return false ;
    return true ; 
}

void Push( SqStack &s , BiTNode *x ){
    s.data[++s.top] = x ; 
}

BiTree Pop( SqStack &s ){
    return s.data[s.top--] ;
}

BiTree GetTop( SqStack s ){
    return s.data[s.top] ;
}

void PreOrderTraverse_recur( BiTree b ){ // recursive
    printf("%c ", b -> data );
    if( b -> lchild ) PreOrderTraverse_recur( b -> lchild ) ;
    if( b -> rchild ) PreOrderTraverse_recur( b -> rchild ) ;
}

void InOrderTraverse_recur( BiTree b ){ // recursive
    if( b -> lchild ) InOrderTraverse_recur( b -> lchild ) ; 
    printf("%c ",b -> data );
    if( b -> rchild ) InOrderTraverse_recur( b -> rchild ) ;
}

void PostOrderTraverse_recur( BiTree b ){ // recursive
    if( b -> lchild ) PostOrderTraverse_recur( b -> lchild ) ; 
    if( b -> rchild ) PostOrderTraverse_recur( b -> rchild ) ;
    printf("%c ",b -> data );
}

void PreOrderTraverse( BiTree b ){
    SqStack s ; 
    InitStack( s ) ; 
    BiTNode *p = b ;
    while( p || !IsEmpty(s) ){
        while( p ){
            printf("%c ",p->data);
            Push( s , p ) ;
            p = p -> lchild ;
        }  
        if( !IsEmpty(s) ){
            p = Pop(s) ;
            p = p -> rchild ; 
        }
    }
}

void InOrderTraverse( BiTree b ){
    SqStack s ; InitStack( s ) ;
    BiTNode *p = b ;
    while( p || !IsEmpty(s) ){
        if( p ){
            Push( s , p ) ;
            p = p -> lchild ; 
        }else{
            p = Pop( s ) ;
            printf("%c ",p->data) ;
            p = p -> rchild ; 
        }
    }
}

void PostOrderTraverse( BiTree b ){
    SqStack s ; InitStack( s ) ;
    BiTNode *p = b ;
    BiTNode *r = NULL ; 
    while( p || !IsEmpty(s) ){
        if(p){
            Push( s , p ) ;
            p = p -> lchild ;
        }else{
            p = GetTop( s ) ; 
            if( p -> rchild && r != p -> rchild ) p = p -> rchild ;
            else{
                p = Pop( s ) ;
                printf("%c ",p->data) ;
                r = p ;
                p = NULL ; 
            }
        }
    }
}


char c ; 
void PreOrderBuild( BiTree &b ){
    scanf("%c",&c) ;
    if( c == '#' ) return ; 
    b = new BiTNode() ; 
    b -> data = c ;     
    PreOrderBuild( b -> lchild ) ;
    PreOrderBuild( b -> rchild ) ;
}

int main(){
    BiTree b ;
    PreOrderBuild( b ) ; 
    // non-recursive
    printf("PreOrderTraverse: 
");
    PreOrderTraverse( b ) ;puts("");
    printf("InOrderTraverse: 
");
    InOrderTraverse( b ) ;puts("") ;
    printf("PostOrderTraverse: 
");
    PostOrderTraverse( b ) ;puts("") ; 
    // recursive
    printf("PreOrderTraverse(recursive): 
");
    PreOrderTraverse_recur( b ) ;puts("");
    printf("InOrderTraverse(recursive): 
");
    InOrderTraverse_recur( b ) ;puts("") ;
    printf("PostOrderTraverse(recursive): 
");
    PostOrderTraverse_recur( b ) ; 
    return 0;
}
/*
ABC##DE#G##F###
PreOrderTraverse:
A B C D E G F
InOrderTraverse:
C B E G D F A
PostOrderTraverse:
C G E F D B A
PreOrderTraverse(recursive):
A B C D E G F
InOrderTraverse(recursive):
C B E G D F A
PostOrderTraverse(recursive):
C G E F D B A
*/

그리고

//         ，                 ， 2，2
/*
	2 			2
	 2        2	     2 , 2
*/

위 에서 아래로 이 진 트 리 의 모든 노드 를 인쇄 하고 같은 층 의 노드 는 왼쪽 에서 오른쪽으로 인쇄 합 니 다.

   vector<int> PrintFromTopToBottom(TreeNode* rt) {
    vector<int> res;
    if( rt == NULL ) return res;
	queue<TreeNode*>q;
	q.push( rt ) ;
	while( !q.empty() ){
		TreeNode* tmp = q.front() ; 
		q.pop() ; 
		res.push_back( tmp -> val ) ;
		if( tmp -> left ) q.push( tmp -> left ) ;
		if( tmp -> right ) q.push( tmp -> right ) ; 
	}
	return res ; 
   }

이 진 트 리 와 특정한 값 의 모든 경로

struct TreeNode {
	int val;
	struct TreeNode *left;
	struct TreeNode *right;
	TreeNode(int x) :
			val(x), left(NULL), right(NULL) {
	}
};
    

    vector<vector<int> > res ; 
    vector<int> a ;
    void dfs( TreeNode* rt , int sum , int k ){
        if( sum == k ) {
            res.push_back(a) ; 
            return ; 
        }
        
        if( rt -> left ) {
            a.push_back( rt -> left -> val ) ;
            dfs( rt -> left , sum + rt -> left -> val , k ) ;
            a.pop_back( ) ;
        }
        if( rt -> right ) {
            a.push_back( rt -> left -> val ) ;
            dfs( rt -> right , sum + rt -> right -> val , k ) ;
            a.pop_back( ) ;
        }
    }
    vector<vector<int> > FindPath(TreeNode* rt,int k) {
        if( rt == NULL ) return res ; 
        a.push_back( rt -> val ) ;
        dfs( rt , rt -> val , k ) ; 
        return res ; 
    }

중간 순서 로 이 진 트 리 의 다음 노드 를 옮 겨 다 닙 니 다. 중간 순 서 는 왼쪽 뿌리 오른쪽 입 니 다. 지정 한 노드 nt 에 접근 하면 nt 에 오른쪽 하위 트 리 가 있 으 면 다음 노드 는 오른쪽 하위 트 리 의 가장 왼쪽 노드 입 니 다. nt 에 오른쪽 하위 트 리 가 없 으 면:

nt 의 부모 노드 가 비어 있 으 면 다음 노드 가 비어 있 습 니 다

nt 부모 노드 가 비어 있 지 않 으 면:

nt 가 부모 노드 의 왼쪽 아이 라면 다음 노드 는 부모 노드

이다.

만약 에 nt 가 부모 노드 오른쪽 아이 라면 다음 노드 는 nt 에서 조상 노드 Pparent 로 옮 겨 다 니 는 것 이다. 첫 번 째 왼쪽 아이 노드 의 아버지 - 예 를 들 어

       1
     2
     	3    
     	   3 。    ，         ，      1

    struct TreeLinkNode {
        int val;
        struct TreeLinkNode *left;
        struct TreeLinkNode *right;
        struct TreeLinkNode *next; //   
        TreeLinkNode(int x) :val(x), left(NULL), right(NULL), next(NULL) {
        }
    };
    TreeLinkNode* GetNext(TreeLinkNode* nt){
    	TreeLinkNode* res ; 
        if( nt == NULL ) return NULL ; 
		if( nt -> right ){ //nt    
			nt = nt -> right ; 
			while( nt -> left ) nt = nt -> left ; 
			res = nt ; 
		}else{ //nt    
			if( nt -> next == NULL ) res = NULL ;  //nt     
			else{//nt   
				if( nt -> next -> left == nt ) res = nt -> next ;  //nt       
				else{ //nt       
					TreeLinkNode* p = nt ; 
					TreeLinkNode* pParent = p -> next ; 
					while( pParent && p == pParent -> right ){ //          
						p = pParent ;
						pParent = pParent -> next ; 
					}
					res = pParent ;//           
				}
			}
		} 
    	return res ; 
    }

이 진 트 리 가 미 러 인지 확인 하기 (대칭):

    bool checkMirror( TreeNode* l , TreeNode* r ){
       if( l == NULL && r == NULL ) return true ;
       if( l == NULL || r == NULL  ) return false ;
       
       if( l -> val == r -> val ) return checkMirror( l -> left , r -> right ) && checkMirror( l -> right , r -> left ) ;     
       return false ; 
    }
    bool isSymmetrical(TreeNode* rt){
        if( rt == NULL ) return true ;
        return checkMirror(rt->left ,rt->right) ; 
    }

위 에서 아래로 두 갈래 나 무 를 층 별로 인쇄 하고 같은 층 의 결점 은 왼쪽 에서 오른쪽으로 출력 합 니 다.각 층 마다 한 줄 씩 출력 합 니 다.

vector<vector<int> > Print(TreeNode* rt) {
    vector<vector<int> >res ; 
    if( rt == NULL ) return res ; 
    int c = 1 ; 
    queue<TreeNode*>q;
    q.push(rt) ;
    vector<int>t ;
    int lev = 0 ;
    while( !q.empty() ){
        int k = 0 ;
        while( c-- ){     
            TreeNode* tmp = q.front() ; q.pop() ;
            t.push_back(tmp->val) ; 
            if( tmp -> left ){
                q.push( tmp -> left ) ; k ++ ;
            }
            if( tmp -> right ){
                q.push( tmp -> right ) ; k ++ ;
            }
        }    
            res.push_back(t) ; 
            t.clear() ; 
            c = k ;
    }
    return res ; 
}

직렬 화, 역 직렬 화 이 진 트 리: 직렬 화: 이 진 트 리 를 특정한 스 트 리밍 방식 의 결과 에 따라 특정한 형식 으로 문자열 로 저장 하여 메모리 에 만들어 진 이 진 트 리 를 오래 저장 할 수 있 습 니 다.직렬 화 할 때 어떤 기 호 를 통 해 빈 노드 (\ #) 를 표시 합 니 다!결점 * * * 값 의 끝 을 표시 합 니 다 (value!).역 직렬 화: 어떤 스 트 리밍 순서에 따라 얻 은 직렬 화 문자열 결과 str, 이 진 트 리 재 구성.

struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};
string s = "" ; 
void preOrder( TreeNode* rt ){
    stringstream ss ;
    if( rt == NULL ) { s += '#' ; return ; }
    ss << ( rt -> val ) ; 
    string t ; ss >> t ;
    s += t ;
    s += "!" ; 
    ss.str("") ;
    preOrder( rt -> left ) ;
    preOrder( rt -> right ) ;
}
char* Serialize(TreeNode *rt) {
    preOrder(rt) ; 
    char t[10000] ;
    strcpy( t , s.c_str() ) ;  
    char* p = t ;
    return p ;
}
vector<int>sq ;
int tot = -1 ;
TreeNode* reBuild( TreeNode* rt ){
    tot ++ ; 
    if( sq[tot] == -1 ) rt = NULL ;
    else{
        rt = new TreeNode(sq[tot]) ;
        rt -> left = reBuild( rt -> left ) ; 
        rt -> right = reBuild( rt -> right ) ;     
    }
    return rt ; 
}

TreeNode* Deserialize(char *str) {
    int len = strlen(str) ; 
    string tmp = "" ; 
    for( int i = 0 ; i < len ; i++ ){
        if( str[i] == '!' ){
            sq.push_back( atoi( tmp.c_str() ) ); 
            tmp = "" ;    
        }else if( str[i] == '#' ){
            sq.push_back(-1) ;
        }else tmp += str[i] ; 
    }
    TreeNode* rt = NULL ; 
    rt = reBuild( rt ) ;
    return rt ; 
}

이 진 트 리 임의의 두 노드 거리 (LCA 알고리즘)

#include 
using namespace std;
const int AX = 4e4 + 666 ;
struct Node{
	int to , w ; 
	Node( int to , int w ):to(to),w(w){}
};
vector<Node>v[AX];
vector<int>q[AX];
vector<int>id[AX];
int res[206] ; 
int dis[AX] ; 
int pre[AX] ; 
int vis[AX] ; 
int T , n , m ;
int find( int x ){
	return pre[x] == x ? x : pre[x] = find(pre[x]) ; 
}
void mix( int x , int y ){
	x = find(x) ;
	y = find(y) ; 
	if( x != y ){
		pre[x] = y ; 
	}
}
void Tarjan( int x , int sum ){
	dis[x] = sum ; 
	vis[x] = 1 ; 
	for( int i = 0 ; i < v[x].size() ; i++ ){
		int y = v[x][i].to ;
		if( vis[y] ) continue ; 
		Tarjan( y , sum + v[x][i].w ) ;
		mix( y , x );
	}
	for( int i = 0 ; i < q[x].size() ; i++ ){
		if( vis[q[x][i]] ){
			res[id[x][i]] = dis[x] + dis[q[x][i]] - 2 * dis[find(q[x][i])] ;
		}
	}
}
int main() {
	int x , y , w ; 
	scanf("%d",&T);
	while( T-- ) {
		scanf("%d%d",&n,&m);
		for( int i = 1 ; i <= n ; i++ ){
			vis[i] = 0 ; dis[i] = 0 ; pre[i] = i ; res[i] = 0 ; 
			v[i].clear(); q[i].clear(); id[i].clear() ; 
		}
		for( int i = 1 ; i <= n ; i++ ) {
			scanf("%d%d",&x,&y);
			if( x != -1 ) v[i].push_back(Node(x,1));
			if( y != -1 ) v[i].push_back(Node(y,1));
		}
		for( int i = 0 ; i < m ; i++ ){
			scanf("%d%d",&x,&y);
			q[x].push_back(y);
			q[y].push_back(x);
			id[x].push_back(i);
			id[y].push_back(i);
		}
		Tarjan( 1 , 0 );
		for( int i = 0 ; i < m ; i++ ){
			printf("%d
",res[i]);
		}
	}
	return 0 ;
}

두 갈래 검색 트 리: 중간 순서 증가 미 러 의 중간 순서 감소
하나씩 삽 입 된 트 리:

#include 
using namespace std;
int n ;
vector<char>pre_v;
vector<char>in_v;
vector<char>res;
struct TreeNode {
	char val ;
	TreeNode *l ;
	TreeNode *r ;
	TreeNode( char val ) : val(val) , l(NULL), r(NULL) {}
};
TreeNode* build( TreeNode* rt , int x ) {
	if( !rt ) {
		rt = new TreeNode(x);
	}else if( x < rt -> val ) {
		rt -> l = build( rt -> l , x );
	}else if( x >= rt -> val ) {
		rt -> r = build( rt -> r , x );
	}
	return rt ;
}
void pre_order( TreeNode *rt ) {
	printf("%d ", rt -> val );
	if( rt -> l ) pre_order( rt-> l ) ;
	if( rt -> r ) pre_order( rt -> r ) ;
}

void in_order( TreeNode *rt ) {
	if( rt -> l ) in_order( rt -> l ) ;
	printf("%d ",rt -> val );
	if( rt -> r ) in_order( rt -> r ) ;
}
void post_order( TreeNode *rt ) {
	if( rt -> l ) post_order( rt -> l ) ;
	if( rt -> r ) post_order( rt -> r ) ;
	printf("%d ",rt -> val );
}


int main() {
	int n , x ;
	scanf("%d",&n);
	TreeNode* rt = NULL ;
	for( int i = 0 ; i < n ; i++ ) {
		scanf("%d",&x);
		rt = build(rt,x);
	}
	pre_order(rt);
	puts("");
	in_order(rt);
	puts("");
	post_order(rt);
	return 0 ;
}

BST 트 리 인지 확인 하기:

bool check_min( TreeNode* rt ) {
	if( rt -> l == NULL && rt -> r == NULL ) return true ;
	if( rt -> l && rt -> r ) return ( check_min( rt -> l ) && check_min( rt -> r )
		                                  && rt -> val >= rt -> l -> val && rt -> val <= rt -> r -> val ) ;
	if( rt -> l && rt -> r == NULL ) return ( check_min( rt -> l ) && rt -> val >= rt -> l -> val );
	if( rt -> r && rt -> l == NULL ) return ( check_min( rt -> r ) && rt -> val <= rt -> r -> val );
}

BST 트 리 인지 확인 하기

bool check_min( int l , int r ){
	if( l > r ) return true ;
	int m = l + 1 ;
	int rt = pre[l] ;
	while( pre[m] < rt && m <= r ) m ++ ; //left_tree
	for( int i = m ; i <= r ; i++ ){
		if( pre[i] < rt ) return false ;
	}
	if( !check_min( l + 1 , m - 1 ) || !check_min( m , r ) ) return false ;
	res.push_back(rt);//    
	return true;
}

이 진 트 리 미 러: (각 노드 좌우 아이 교환)

struct TreeNode {
	int val;
	struct TreeNode *left;
	struct TreeNode *right;
	TreeNode(int x) :
			val(x), left(NULL), right(NULL) {
	}
};
void Mirror(TreeNode *rt) {
    if( rt == NULL ) return ;
	queue<TreeNode*>q ;
	q.push(rt) ;
	TreeNode* tmp ;
	TreeNode* t ;
	while( !q.empty() ){
		tmp = q.front() ; 
		q.pop() ; 
		t = tmp -> left ; 
		tmp -> left = tmp -> right;
		tmp -> right = t ;
		if( tmp -> left ) q.push(tmp -> left);
		if( tmp -> right ) q.push(tmp -> right);
	}
}

이 진 트 리 의 k 번 째 결점 을 검색 하여 그 중의 k 번 째 작은 결점 을 찾 아 라.

    vector<TreeNode*> res ; 
    void InOrder( TreeNode* rt ){
        if( rt == NULL ) return ;
        InOrder( rt -> left ) ; 
        res.push_back( rt ) ; 
        InOrder( rt -> right ) ; 
    }
    TreeNode* KthNode(TreeNode* rt, int k){
        if( rt == NULL || !k ) return NULL ; 
        InOrder( rt ) ; 
        if( k > (int)res.size() ) return NULL ; 
        return res[k-1] ; 
    }

균형 이 진 트 리: 판단:

    int getHigh( TreeNode* rt ){
        if( rt == NULL ) return 0 ; 
        int lh = getHigh( rt -> left ) ;  
        int rh = getHigh( rt -> right ) ; 
        if( lh == -1 || rh == -1 || abs( lh - rh ) > 1 ) return -1 ;
        return max( lh ,rh ) + 1 ; 
    }
    
    bool IsBalanced_Solution( TreeNode* rt ){
        return ( getHigh( rt ) != -1 )  ;
    }