이 진 트 리 기본 조작 및 면접 문제 (원 하 는 것 은 모두 있 습 니 다)
58663 단어 데이터 구조
typedef char BDataType;
typedef struct BTNode
{
BDataType data;
struct BTNode* Lchild;
struct BTNode* Rchild;
}BTNode;
생 성 노드:
BTNode *BuyBTNode(BDataType data)
{
BTNode* newNode = (BTNode*)malloc(sizeof(BTNode));
if(NULL == newNode)
{
assert(0);
return NULL;
}
newNode->Lchild = NULL;
newNode->Rchile = NULL;
newNode->data = data;
return newNode;
}
1. 이 진 트 리 만 들 기.(앞 순서 생 성) (1) 시퀀스 색인 이 시퀀스 길이 보다 적 고 현재 색인 요 소 는 유효 요소 입 니 다.(2) 루트 노드 를 만 듭 니 다.(3) 뿌리 노드 의 왼쪽 트 리 를 만 듭 니 다.(4) 뿌리 노드 의 오른쪽 하위 트 리 를 만 듭 니 다.
// root , 。index 。
void CreateBinTree(BTNode **root,char *str,int size,int *index)
{
assert(root);
assert(index);
if(*index < size && str[*index] != '#')
{
*root = BuyBTNode(str[*index]);
++(*index);
CreateBinTree(&(*root)->Lchild,str,size,index);
++(*index);
CreatrBinTree(&(*root)->Rchild,str,size,index);
}
}
2. 앞 순 서 는 반복 적 으로 이 루어 진다.(1) 뿌리 노드 를 옮 겨 다 닌 다.(2) 뿌리 노드 를 옮 겨 다 니 는 왼쪽 나무.(3) 뿌리 노드 를 옮 겨 다 니 는 오른쪽 나무.
void PreOrder(BTNode *root)
{
if(root)
{
printf("%c ",root->data);
PreOrder(root->Lchild);
PreOrder(root->Rchild);
}
}
3. 중간 순 서 는 반복 적 으로 이 루어 진다.(1) 뿌리 노드 를 옮 겨 다 니 는 왼쪽 나무.(2) 뿌리 노드 를 옮 겨 다 닌 다.(3) 뿌리 노드 를 옮 겨 다 니 는 오른쪽 나무.
void InOrder(BTNode *root)
{
if(root)
{
InOrder(root->Lchild);
printf("%c ",root->data);
InOrder(root->Rchild);
}
}
4. 후 순 서 는 반복 적 으로 이 루어 진다.(1) 뿌리 노드 를 옮 겨 다 니 는 왼쪽 나무.(2) 뿌리 노드 를 옮 겨 다 니 는 오른쪽 나무.(3) 뿌리 노드 를 옮 겨 다 닌 다.
void PostOrder(BTNode *root)
{
if(root)
{
PostOrder(root->Lchild);
PostOrder(root->Rchild);
printf("%c ",root->data);
}
}
5. 이 진 트 리 복사 하기.이 진 트 리 앞 순 서 를 옮 겨 다 니 는 것 과 유사 합 니 다.(1) 뿌리 노드 를 복사 합 니 다.(2) 뿌리 노드 의 왼쪽 나 무 를 복사 합 니 다.(3) 뿌리 노드 의 오른쪽 나 무 를 복사 합 니 다.
BTNode *CopyBinTree(BTNode *root)
{
BTNode *newRoot = NULL;
if(root)
{
newRoot = BuyBTNode(root->data);
if(root->Lchild)
newRoot->Lchild = CopyBinTree(root->Lchild);
if(root->Rchild)
newRoot->Rchild = CopyBinTree(root->Rchild);
}
return newRoot;
}
6. 이 진 트 리 의 노드 개 수 를 구하 세 요.(1) 좌우 서브 트 리 의 노드 갯 수 입 니 다.
int GetBTNodeCount(BTNode *root)
{
if(NULL == root)
{
return 0;
}
return GetBTNodeCount(root->Lchild)+GetBTNodeCount(root->Rchild)+1;
}
7. 이 진 트 리 의 잎 노드 의 개 수 를 구하 세 요.잎 노드: 왼쪽 아이 도 오른쪽 아이 도 없다.(1) 좌우 자나무 의 잎 노드 의 개수.
int GetLeafNodeCount(BTNode *root)
{
if(NULL == root)
{
return 0;
}
if(NULL == root->Lchild && NULL == root->Rchild)
{
return 1;
}
return GetLeafNodeCount(root->Lchild)+GetLeafNodeCount(root->Rchild);
}
8. 이 진 트 리 중 K 층 노드 의 개 수 를 구하 세 요.(1) 좌우 글자 수 에서 K - 1 층 노드 의 개 수 를 구한다.
int GetKLevelNodeCount(BTNode *root,int K)
{
if(NULL == root)
{
return 0;
}
if(K == 1)
{
return 1;
}
return GetKLevelNodeCount(root->Lchild,K-1)+GetKLevelNodeCount(root->Rchild,K-1);
}
9. 이 진 트 리 높이 구하 기.(1) 이 진 트 리 의 좌우 자나무 가 높 은 나무의 높이 를 구한다.
int GetBinTreeHeight(BTNode *root)
{
if(NULL == root)
{
return 0;
}
int LeftHeight = 0;
int RightHeight = 0;
LeftHeight = GetBinTreeHeight(root->Lchild);
RightHeight = GetBinTreeHeight(root->Rchild);
return LeftHeight>RightHeight?LeftHeight+1:RightHeight+1;
}
10. 두 갈래 나 무 를 없 애 라 (1) 뿌리 노드 의 왼쪽 나 무 를 없 애 라.(2) 뿌리 노드 의 오른쪽 나 무 를 없앤다.(3) 뿌리 노드 를 소각 한다.
void DestroyBinTree(BTNode **root)
{
assert(*root);
if(NULL == *root)
{
return;
}
DestroyBinTree(&(*root)->Lchild);
DestroyBinTree(&(*root)->Rchild);
free(*root);
*root = NULL;
}
11. 이 진 트 리 의 왼쪽 아이 노드 를 구한다.
BTNode *LeftNode(BTNode *root)
{
if(NULL == root)
{
return NULL;
}
return root->Lchild;
}
12. 이 진 트 리 의 오른쪽 아이 노드 를 구한다.
BTNode *LeftNode(BTNode *root)
{
if(NULL == root)
{
return NULL;
}
return root->Rchild;
}
13. 이 진 트 리 에서 가장 먼 노드 사이 의 거 리 를 구한다.(1) 현재 노드 의 깊이 와 현재 노드 를 뿌리 로 하 는 서브 트 리 의 최대 거 리 를 계산한다.
int Max_distance(BTNode *root, int *m)
{
if (NULL == root)
{
return 0;
}
int* max = m;
int LeftDepth = Max_distance(root->Lchild, max);
int RightDepth = Max_distance(root->Rchild, max);
if (*max < LeftDepth + RightDepth)
{
*max = LeftDepth + RightDepth;
}
return LeftDepth>RightDepth ? LeftDepth + 1 : RightDepth + 1;
}
(2) 이 진 트 리 에서 가장 먼 노드 거 리 를 계산한다.
int Maxdistance(BTNode *root)
{
if (NULL == root)
{
return 0;
}
int max = 0;
Max_distance(root, &max);
return max;
}
14. 한 노드 가 이 진 트 리 에 있 는 지 판단 한다.(1) 뿌리 노드 여 부 를 판단 한다.그렇지 않 으 면 (2) 로 갑 니 다.(2) 왼쪽 트 리 의 노드 인지 판단 한다.(3) 오른쪽 트 리 의 노드 인지 판단 한다.
int IsBTNodeInBinTree(BTNode *root,BTNode *Node)
{
if((NULL== root)||(NULL == Node))
return 0;
if(Node == root)
return 1;
if(IsBTNodeInBinTree(root->Lchild,Node))
return 1;
return IsBTNodeInBinTree(root->Rchild,Node);
}
15. 한 노드 의 가장 가 까 운 조상 노드 를 구한다.(1) 뿌리 노드 부터 판단 한다.(2) 뿌리 노드 의 왼쪽 아이 나 오른쪽 아이 가 이 노드 라면 뿌리 노드 로 돌아간다.(3) 루트 노드 를 왼쪽 아이 로 업데이트 합 니 다.넘어가다(4) 루트 노드 를 오른쪽 아이 로 업데이트 합 니 다.넘어가다
BTNode* GetBTNodeParent(BTNode *root,BTNode *Node)
{
if((NULL == root)||(NULL == Node)||(root == Node)
return 0;
if((Node == root->Lchild) || (Node == root->Rchild))
return root;
BTNode *parent = NULL;
if(parent = GetBTNodeParent(root->Lchild,Node))
return parent;
return GetBTNodeParent(root->Rchild,Node);
}
16. 이 진 트 리 의 거울 을 구한다.(1) 뿌리 노드 의 좌우 아 이 를 교환 합 니 다.(2) 왼쪽 나무의 좌우 아 이 를 교환 합 니 다.(3) 오른쪽 나무의 좌우 아 이 를 교환 합 니 다.
void MirrorBinTree(BTNode *root)
{
if(root)
{
Swap(&root->Lchild,&root->Rchild);
MirrorBinTree(BTNode *root->Lchild);
MirrorBinTree(BTNode *root->Rchild);
}
}
17. 층 차 를 옮 겨 다 닌 다.루트 노드 를 대기 열 에 넣 습 니 다.(1) 팀 헤드 요 소 를 취한 다.(2) 이 요소 에 접근 합 니 다.(3) 이 노드 의 왼쪽 하위 트 리 가 존재 하면 대기 열 에 들 어 갑 니 다.(4) 이 노드 의 오른쪽 하위 트 리 가 존재 하면 대기 열 에 들 어 갑 니 다.(5) 대상 요 소 를 대기 열 에서 꺼 냅 니 다.(6) 대기 열 이 비어 있 는 지 판단 하고 비어 있 으 면 끝 납 니 다. 그렇지 않 으 면 이동 합 니 다 (1).
void LevelOrder(BTNode *root)
{
if(NULL == root)
return;
Queue q;
QueueInit(&q);
QueuePush(&q,root);
while(!QueueEmpty(&q))
{
BTNode *cur = QueueFront(&q);
printf("%c ",cur->data);
if(cur->Lchild)
QueuePush(&q,cur->Lchild);
if(cur->Rchild)
QueuePush(&q,cur->Rchild);
QueuePop(&q);
}
}
18. 완전 이 진 트 리 인지 판단 한다.루트 노드 를 대기 열 에 넣 습 니 다.(1) 팀 헤드 요 소 를 취한 다.(2) 뿌리 부분 에 왼쪽 아이 도 있 고 오른쪽 아이 도 있 으 면 모두 대열 에 들어간다.(3) 뿌리 부분 에 왼쪽 아이 만 있 고 오른쪽 아이 가 없 으 면 완전 이 진 트 리 이다.(4) 뿌리 부분 이 오른쪽 아이 만 있 고 왼쪽 아이 가 없 으 면 완전히 이 진 트 리 가 아니다.(5) 뿌리 부분 에 왼쪽 아이 가 없고 오른쪽 아이 가 없 으 면 완전 이 진 트 리 이다.(6) 대기 열 을 내 고 빈 대기 열 인지 판단 합 니 다.빈 곳 으로 뛰 어 내리 고, 빈 곳 으로 이동 하지 않 으 면 (1).
int IsCompleteBinTree(BTNode *root)
{
if(NULL == root)
return 0;
int IsFlag = 0;
Queue q;
QueueInit(&q);
QueuePush(&q,root);
while(!QueueEmpty(&q))
{
BTNode *cur = QueueFront(&q);
if(IsFlag)
{
if(cur-Lchild || cur->Rchild)
return 0;
}
else
{
if(cur->Lchild && cur->Rchild)
{
QueuePush(&q,cur->Lchild);
QueuePush(&q,cur->Rchild);
}
else if(cur->Lchild)
{
QueuePush(&q,cur->Lchild);
IsFlag = 1;
}
else if(cur->Rchild)
{
return 0;
}
else
{
IsFlag = 1;
}
}
QueuePop(&q);
}
return 1;
}
19. 앞 순 서 는 반복 되 지 않 고 이 루어 진다.앞 순서 가 뿌리 – > 왼쪽 – > 오른쪽 이기 때문에 스 택 을 통 해 이 루어 질 때 뿌리 노드 를 누 른 후에 눌 러 야 하 는 것 은 왼쪽 아이 노드 가 아니 라 아이 노드 가 있어 야 합 니 다.(1) cur 를 뿌리 로 하 는 이 진 트 리 의 뿌리 노드 를 옮 겨 다 닌 다.스 택 꼭대기 요 소 를 동시에 나 옵 니 다.스 택 이 비어 있 으 면 뛰 어 나 갑 니 다. 그렇지 않 으 면 다음 단 계 를 진행 합 니 다.(2) 오른쪽 아이 가 있 으 면 창고 에 넣 습 니 다.(3) 왼쪽 아이 가 있 으 면 창고 에 넣 습 니 다.
void PreOrderNor1(BTNode *root)
{
if(NULL == root)
return;
Stack s;
StackInit(&s);
StackPush(&s,root);
while(!StackEmpty(&s))
{
BTNode *cur = StackTop(&s);
printf("%c ",cur->data);
StackPop(&s);
if(cur->Rchild)
StackPush(&s,cur->Rchild);
if(cur->Lchild)
StackPush(&s,cur->Lchild);
}
}
void PreOrderNor2(BTNode *root)
{
if(NULL == root)
return;
Stack s;
StackInit(&s);
StackPush(&s,root);
while(!StackEmpty(&s))
{
BTNode *cur = StackTop(&s);
StackPop(&s);
while(cur)
{
printf("%c ",cur->data);
if(cur->Rchild)
StackPush(&s,cur->Rchild);
cur = cur->Lchild;
}
}
}
20. 중간 순서 가 반복 되 지 않 고 이 루어 진다.(1) cur 를 뿌리 로 하 는 이 진 트 리 의 맨 왼쪽 노드 를 찾 아 경로 에 있 는 노드 를 저장 합 니 다.(저장 은 스 택 을 통 해 이 루어 집 니 다) (2) cur 를 뿌리 로 하 는 이 진 트 리 의 뿌리 노드 를 옮 겨 다 닙 니 다.(3) cur 를 뿌리 로 하 는 이 진 트 리 의 오른쪽 아 이 를 옮 겨 다 닌 다.오른쪽 하위 트 리 가 존재 하면 (1) 로 이동 합 니 다. 그렇지 않 으 면 되 돌아 갑 니 다.(리 턴 작업 은 스 택 지붕 을 통 해 이 루어 집 니 다)
void InOrderNor(BTNode *root)
{
if(NULL == root)
return;
Stack s;
StackInit(&s);
BTNode *cur = root;
while(cur || !StackEmpty(&s))
{
while(cur)
{
StackPush(&s,cur);
cur = cur->Lchild;
}
cur = StackTop(&s);
printf("%c ",cur->data);
StackPop(&s);
cur = cur->Rchild;
}
}
21. 후 서 는 반복 되 지 않 고 이 루어 진다.(1) cur 를 뿌리 로 하 는 이 진 트 리 의 맨 왼쪽 노드 를 찾 아 경로 에 있 는 노드 를 저장 합 니 다.(저장 은 스 택 을 통 해 이 루어 집 니 다) (2) 현재 스 택 꼭대기 요소 에 오른쪽 아이 가 있 는 지 판단 합 니 다. 없 으 면 현재 노드 를 옮 겨 다 니 지 않 으 면 cur 를 오른쪽 아이 노드 로 업데이트 합 니 다.
void PostOrderNor(BTNode *root)
{
if(NULL == root)
return;
Stack s;
StackInit(&s);
BTNode* visitNode = NULL;
BTNode* cur = root;
while(cur || !StackEmpty(&s))
{
while(cur)
{
StackPush(&s,cur);
cur = cur->Lchild;
}
cur = StackTop(&s);
if(NULL == cur->Rchild || visitNode == cur->Rchild)
{
printf("%c ",cur->data);
StackPop(&s);
visitNode = cur;
cur = NULL;
}
else
{
cur = cur->Rchild;
}
}
}
어떤 지식 을 제대로 파악 하지 못 할 수도 있 으 니, 여러분 독자 들 은 평론 구역 에서 의견 을 많이 주 십시오!!!
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
정수 반전Udemy 에서 공부 한 것을 중얼거린다 Chapter3【Integer Reversal】 (예) 문자열로 숫자를 반전 (toString, split, reverse, join) 인수의 수치 (n)가 0보다 위 또는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
