두 갈래 나무 각종 반복 조작

카탈로그
1 두 갈래 나무 깊이 구하기
1.1 반복 실현
1.2 비귀속 실현(대기열)
1.3 비귀속 실현(창고)
2 가닥나무 높이 구하기
3 두 갈래 나무 순서대로
3.1 반복 버전
3.2 비귀속 버전
3.3 순서를 이용하여 두 갈래 나무 만들기
4 두 갈래 나무의 순서
4.1 반복 버전
4.2 비귀속 버전
5 두 갈래 나무 뒤에 차례대로
5.1 반복 버전
5.2 비귀속 버전
6 두 갈래 나무층 서열 두루
7 두 갈래 나무 깊이 우선 반복
8 두 갈래 나무 넓이 우선 훑어보기
9 두 갈래 나무 노드 사이의 최대 거리를 구한다
10 두 갈래 나뭇잎 노드 수량 계산
11 두 갈래 나무의 뿌리 노드에서 지정한 노드로의 경로 가져오기
12 두 경로의 마지막 공통 노드 가져오기
13 두 결점을 얻은 최근 공동 조상
본고는 두 갈래 나무에 관한 각종 역행 알고리즘을 총결하였다.
먼저 두 갈래 나무 노드 구조체를 정의합니다

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

1 두 갈래 나무 깊이 구하기

1.1 반복 실현

나무 한 그루에 결점이 하나만 있다면 그 깊이는 1이다.

뿌리 결점이 왼쪽 나무만 있고 오른쪽 나무가 없다면 나무의 깊이는 왼쪽 나무의 깊이에 1을 더하고 1을 더하면 뿌리 노드라는 층을 더한다

만약에 왼쪽 나무와 오른쪽 나무가 있다면 나무의 깊이는 왼쪽, 오른쪽 나무 중 깊이가 비교적 큰 값에 1

을 더해야 한다.

    int TreeDepth(TreeNode* pRoot)
    {
     if(pRoot==NULL)
            return 0;

        int nleft = TreeDepth(pRoot->left);
        int nright = TreeDepth(pRoot->right);

        return (nleft>nright)?(nleft+1):(nright+1);

    }

1.2 비귀속 실현(대기열)

층마다 depth++;

각 층마다 변수len를 사용하여 이 층의 결점 개수, 즉 대기열의 현재 길이를 기록한 다음에 순서대로 대기열에서 이 층의 len 결점에 접근하여 대기열len 요소를 대기열에서 내보내고 다음 층을 대기열에 넣어야 한다.

int TreeDepth(TreeNode* pRoot)
    {
     queue q;
        if(!pRoot) return 0;
        q.push(pRoot);
        int level=0;
        while(!q.empty()){
            int len=q.size();
            level++;
            while(len--){
                TreeNode* tem=q.front();
                q.pop();
                if(tem->left) q.push(tem->left);
                if(tem->right) q.push(tem->right);
            }
        }
        return level;
    }

1.3 비귀속 실현(창고)

#include 
#include 
using namespace std;
typedef struct BinTree
{
    int data;
    BinTree *lc;
    BinTree *rc;
}BTNode,*BinTree;
int max(int a,int b)
{
    return (a>b)?a:b;
}

int BinTreeDepth(BinTree T)
{
    stack s;
    BinTree p = T,r = NULL;
    int depth=0;
    while(p||!s.empty())
    {
        if(p)
        {    // 
            s.push(p);
            int size = s.size();// 
            depth = max(depth,size);// 
            p = p->lc;
        }
        else
        {    // 
            p = s.top();
            if(p->rc&&p->rc!=r)// ， 
            {
                p = p->rc;
                s.push(p);
                int size = s.size();// 
                depth = max(depth,size);// 
                p = p->lc;
            }else
            {
                p=s.top();
                s.pop();
                cout<data<

2 가닥나무 높이 구하기

깊이를 구하는 것과 마찬가지로 유일한 차이점은 뿌리 노드에 대해 깊이는 1이고 높이는 0이다.

int Height(TreeNode *node)
{
    if(node == NULL)
        return -1;
    else
        return 1 + Max(Height(node->left),Height(node->right));
}

3 두 갈래 나무 순서대로

3.1 반복 버전

    void preOrderTraverse(TreeNode *root) {  
        if (root != NULL) {  
            cout<val<left);  
            preOrderTraverse(root->right);  
        }  
    }

3.2 비귀속 버전


void PreOrder(TreeNode* pRoot)// ， 
{
	if (pRoot == NULL)
		return;
	stack s;
	TreeNode *p = pRoot;
	while (p != NULL || !s.empty())
	{
		if (p != NULL)
		{
			cout << p->val << " ";
			s.push_back(p);
			p = p->left;
		}
		else
		{
			p = s.pop();
			p = p->right;
		}
	}
	cout << endl;
}

3.3 순서를 이용하여 두 갈래 나무 만들기

// 
void CreateBiTree(BiTree &T)
{
	char c;
	cin >> c;
	if ('#' == c)
		T=NULL;
	else
	{
		T = (BiNode* ) malloc(sizeof(BiNode));
		T->val = c;
		CreateBiTree(T->left);
		CreateBiTree(T->right);
	}
}

4 두 갈래 나무의 순서

4.1 반복 버전

    void inOrderTraverse(TreeNode* root) {  
        if (root != NULL) {  
            inOrderTraverse(root->left);  
            cout<val<right);  
        }  
    }

4.2 비귀속 버전

   void inOrderTraverse(TreeNode* root) {  
        stack s;  
        TreeNode* pNode = root;  
        while (pNode != null || !stack.isEmpty()) {  
            if (pNode != null) {  
                s.push(pNode);  
                pNode = pNode->left;  
            } else { //pNode == null && !stack.isEmpty()  
                TreeNode node = s.pop();  
                cout<val<right;  
            }  
        }  
    }

5 두 갈래 나무 뒤에 차례대로

5.1 반복 버전

public void postOrderTraverse(TreeNode root) {  
        if (root != null) {  
            postOrderTraverse(root.left);  
            postOrderTraverse(root.right);  
            System.out.print(root.val+"  ");  
        }  
    }

5.2 비귀속 버전


void PostOrder(BiTree &T)// （ ）， 
{
	if (T == NULL)
		return;
	vector S1,S2;
	BiNode *p ;// 
	S1.push_back(T);
	while (!S1.empty())
	{
		p = S1[S1.size() - 1];
		S1.pop_back();
		S2.push_back(p);
		if (p->left)
			S1.push_back(p->left);
		if (p->right)
			S1.push_back(p->right);
	}
	while (!S2.empty())
	{
		cout << S2[S2.size() - 1]->val << " ";
		S2.pop_back();
	}
	cout << endl;
}

6 두 갈래 나무층 서열 두루

   void levelTraverse(TreeNode* root) {  
        if (root == NULL) {  
            return;  
        }  
        queue q;  
        queue.push_back(root);  
        while (!q.empty()) {  
            TreeNode* node = q.pop_front();  
            cout<val<left != NULL) {  
                q.push_back(node->left);  
            }  
            if (node->right != NULL) {  
                q.push_back(node->right);  
            }  
        }  
    }

7 두 갈래 나무 깊이 우선 반복

깊이 우선순위는 선순위입니다.


// 
void depthFirstSearch(Tree root){
    stack nodeStack; 
    nodeStack.push(root);
    Node *node;
    while(!nodeStack.empty()){
	    node = nodeStack.top();
		cout<data;// 
        nodeStack.pop();
        if(node->rchild){
            nodeStack.push(node->rchild);  // 
        }
        if(node->lchild){
            nodeStack.push(node->lchild);  // 
        }
    }
}

8 두 갈래 나무 넓이 우선 훑어보기

광도 우선은 사실 층층이 누적되어 있어 대열을 이용하면 실현하기 쉽다.


// 
void breadthFirstSearch(Tree root){
    queue nodeQueue;  // C++ STL 
    nodeQueue.push(root);
    Node *node;
    while(!nodeQueue.empty()){
        node = nodeQueue.front();
        nodeQueue.pop();
        cout<data;// 
        if(node->lchild){
            nodeQueue.push(node->lchild);  // 
        }
        if(node->rchild){
            nodeQueue.push(node->rchild);  // 
        }
    }
}

9 두 갈래 나무 노드 사이의 최대 거리를 구한다


int GetMaxDistance(BiTree &T)// ， 
{
	if (T == NULL)
		return 0;
	int Distance = TreeDepth(T->left) + TreeDepth(T->right);
	int l_Distance = GetMaxDistance(T->left);
	int r_Distance = GetMaxDistance(T->right);
	Distance = (Distance > r_Distance) ? Distance : r_Distance;
	Distance = (Distance > l_Distance) ? Distance : l_Distance;
	return Distance;
}

10 두 갈래 나뭇잎 노드 수량 계산


int CountLeafNode(BiTree &T)// ， 
{
	if (T == NULL)
		return 0;
	if (T->left == NULL&&T->right == NULL)
		return 1;
	return CountLeafNode(T->left)+CountLeafNode(T->right);
}

11 두 갈래 나무의 뿌리 노드에서 지정한 노드로의 경로 가져오기

//  
void GetNodePath(BiNode* T, BiNode* Node, vector& Path,int &found)
{
	if (T == NULL)
		return;
	Path.push_back(T);
	if (T == Node)
		found = 1;
	if (!found)
	{
		GetNodePath(T->left, Node, Path, found);
	}
	if (!found)
	{
		GetNodePath(T->right, Node, Path, found);
	}
	if (!found)
		Path.pop_back();
	else
		return;
}

12 두 경로의 마지막 공통 노드 가져오기

// 
BiNode* GetLastCommonNode(const vector Path1, const vector Path2)
{
	vector::const_iterator iter1 = Path1.begin();
	vector::const_iterator iter2 = Path2.begin();
	BiNode *p = NULL;
	while ( iter1 != Path1.end() && iter2 != Path2.end() && *iter1 != *iter2 )
	{
		if (*iter1 == *iter2)
			p = *iter1;
		iter1++;
		iter2++;
	}
	return p;
}

13 두 결점을 얻은 최근 공동 조상

// 
BiNode* GetLastCommonParent(BiNode* T, BiNode* Node1, BiNode* Node2)
{
	if (T == NULL || Node1 == NULL || Node2 == NULL)
		return NULL;
	vector Path1, Path2;
	int found1 = 0;
	int found2 = 0;
	GetNodePath(T, Node1, Path1,found1);
	GetNodePath(T, Node2, Path2, found2);
	return GetLastCommonNode(Path1,Path2);
}

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

Python3를 사용하여 빠른 배열 정렬

2020년 새해 복 많이 받으세요.저는 ryuichi69라고 합니다.오늘도 알고리즘 연습의 성과, 연습을 설명하는 동시에 이 글을 썼다.솔직히 이해하기 쉽게 쓰느라 힘들었는데 설명하기 어려운 부분, 요건 누락 등이 ...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.