C 언어 이 진 트 리 에서 흔히 볼 수 있 는 조작 에 대한 상세 한 설명
기본 개념
각 결점 에는 최대 두 그루 의 나무 가 있 는데,왼쪽 나무 와 오른쪽 나 무 는 순서 가 뒤 바 뀌 어 서 는 안 된다.
성질:
1.비 공 이 진 트 리 의 n 층 에는 많아야 2^(n-1)개의 요소 가 있다.
2.깊이 가 h 인 이 진 트 리 는 많아야 2^h-1 개의 결점 이 있다.
만 이 진 트 리:모든 터미널 은 같은 차원 에 있 고 터미널 노드 가 아 닌 도 수 는 2 입 니 다.
이 진 트 리 에 깊이 가 h 이면 포 함 된 결 점 수 는 2^h-1 입 니 다.
완전 이 진 트 리:가장 큰 층 차 를 제외 하고 이 진 트 리 가 되 고 층 차 가 가장 큰 층 의 모든 결점 이 왼쪽으로 나란히 있 습 니 다.즉,왼쪽 의 위치 에 집중 되 어 빈 위치 가 있어 서 는 안 됩 니 다.
완전 이 진 트 리 에 대해 하나의 결점 을 i 로 설정 하면 그의 아버지 노드 는 i/2 이 고 2i 는 왼쪽 노드 이 며 2i+1 은 오른쪽 노드 이다.
저장 구조
순서 저장 소:
데이터 구 조 를 고정된 배열 에 저장 합 니 다.
#define LENGTH 100
typedef char datatype;
typedef struct node{
datatype data;
int lchild,rchild;
int parent;
}Node;
Node tree[LENGTH];
int length;
int root;
옮 겨 다 니 는 속도 에 있어 서 어느 정도 장점 이 있 지만 차지 하 는 공간 이 비교적 커서 비주류 이 진 트 리 이다.이 진 트 리 는 보통 체인 으로 저장 된다.체인 메모리:
typedef char datatype;
typedef struct BinNode{
datatype data;
struct BinNode* lchild;
struct BinNode* rchild;
}BinNode;
typedef BinNode* bintree; //bintree
세 갈래 나무 가 널 려 있다.트 리 의 모든 노드 에 접근 하고 한 번 만 접근 합 니 다.뿌리 노드 의 위치 에 따라 앞 순 서 를 옮 겨 다 니 고 중간 순 서 를 옮 겨 다 니 며 뒤 순 서 를 옮 겨 다 닌 다.
앞 순서 옮 겨 다 니 기:뿌리 노드->왼쪽 트 리->오른쪽 트 리
중간 순서:왼쪽 하위 트 리->뿌리 노드->오른쪽 하위 트 리
뒤 순 옮 겨 다 니 기:왼쪽 하위 트 리->오른쪽 하위 트 리->뿌리 노드
다음 나무의 세 가지 옮 겨 다 니 기
이전 순서:abdefgc
중간 순서:debgfac
다음 순서 옮 겨 다 니 기:edgfbca
4.옮 겨 다 니 는 실현
재 귀적 실현(이전 순 서 를 예 로 들 면 다른 것 은 출력 위치 만 조금 다 를 뿐)
void preorder(bintree t){
if(t){
printf("%c ",t->data);
preorder(t->lchild);
preorder(t->rchild);
}
}
비 재 귀적 실현뿌리 노드 를 옮 겨 다 니 고 돌아 오기 때문에 저장 해 야 합 니 다.후진 선 출 의 특징 을 고려 하여 스 택 저장 소 를 선택 하 십시오.수량 이 확정 되 어 순서대로 저장 합 니 다.
#define SIZE 100
typedef struct seqstack{
bintree data[SIZE];
int tag[SIZE]; //
int top; //top
}seqstack;
void push(seqstack *s,bintree t){
if(s->top == SIZE){
printf("the stack is full
");
}else{
s->top++;
s->data[s->top]=t;
}
}
bintree pop(seqstack *s){
if(s->top == -1){
return NULL;
}else{
s->top--;
return s->data[s->top+1];
}
}
1.앞 순서 옮 겨 다 니 기
void preorder_dev(bintree t){
seqstack s;
s.top = -1; // top , -1
if(!t){
printf("the tree is empty
");
}else{
while(t || s.stop != -1){
while(t){ // ,
printf("%c ",t->data);
push(&s,t);
t= t->lchild;
}
t=pop(&s);
t=t->rchild;
}
}
}
2.중간 순서 로 옮 겨 다 니 기
void midorder(bintree t){
seqstack s;
s.top = -1;
if(!t){
printf("the tree is empty!
");
}else{
while(t ||s.top != -1){
while(t){
push(&s,t);
t= t->lchild;
}
t=pop(&s);
printf("%c ",t->data);
t=t->rchild;
}
}
}
3.후 순 옮 겨 다 니 기마지막 으로 루트 노드 에 한 번 더 접근해 야 하기 때문에 루트 노드 에 두 번 방문 해 야 합 니 다.표지 판 을 끼 우 는 방법 을 채택 하여 이 문 제 를 해결 하 다.
이 코드 는 매우 복잡 해서 자신 이 있 는 친구 에 게 독립 적 으로 써 볼 수 있다.어쨌든 나 는 오랫동안 썼 다.논리 가 어렵 지 않 아서 나 는 논리 도 를 한 장 그 렸 다.
코드:
void postorder_dev(bintree t){
seqstack s;
s.top = -1;
if(!t){
printf("the tree is empty!
");
}else{
while(t || s.top != -1){ // t 。
while(t){
push(&s,t);
s.tag[s.top] = 0; // ,0 ,1
t= t->lchild;
}
if(s.tag[s.top] == 0){ // ,
t= s.data[s.top]; // t , !
s.tag[s.top]=1;
t=t->rchild;
}else {
while (s.tag[s.top] == 1){ // , pop
t = pop(&s);
printf("%c ",t->data);
}
t = NULL; // t 。 ,
}
}
}
}
4.층 차 를 옮 겨 다 니 기:즉,각 층 이 왼쪽 에서 오른쪽으로 출력 하 는 것 이다.요 소 는 선진 적 인 선 출 특성 을 저장 해 야 하기 때문에 대기 열 로 저장 합 니 다.
대기 열의 정의:
#define MAX 1000
typedef struct seqqueue{
bintree data[MAX];
int front;
int rear;
}seqqueue;
void enter(seqqueue *q,bintree t){
if(q->rear == MAX){
printf("the queue is full!
");
}else{
q->data[q->rear] = t;
q->rear++;
}
}
bintree del(seqqueue *q){
if(q->front == q->rear){
return NULL;
}else{
q->front++;
return q->data[q->front-1];
}
}
두루 실현 하 다.
void level_tree(bintree t){
seqqueue q;
bintree temp;
q.front = q.rear = 0;
if(!t){
printf("the tree is empty
");
return ;
}
enter(&q,t);
while(q.front != q.rear){
t=del(&q);
printf("%c ",t->data);
if(t->lchild){
enter(&q,t->lchild);
}
if(t->rchild){
enter(&q,t->rchild);
}
}
}
5.앞 순 서 를 옮 겨 다 니 는 결 과 를 이용 하여 이 진 트 리 생 성
// , , , , ,
void createtree(bintree *t){
datatype c;
if((c=getchar()) == '#')
*t = NULL;
else{
*t = (bintree)malloc(sizeof(BinNode));
(*t)->data = c;
createtree(&(*t)->lchild);
createtree(&(*t)->rchild);
}
}
6.이 진 트 리 찾기
bintree search_tree(bintree t,datatype x){
if(!t){
return NULL;
}
if(t->data == x){
return t;
}else{
if(!search_tree(t->lchild,x)){
return search_tree(t->rchild,x);
}
return t;
}
}
7.결산 점수 개 수 를 집계 한다.
int count_tree(bintree t){
if(t){
return (count_tree(t->lchild)+count_tree(t->rchild)+1);
}
return 0;
}
8.두 나무 가 같은 지 비교
int is_equal(bintree t1,bintree t2){
if(!t1 && !t2){ //
return 1;
}
if(t1 && t2 && t1->data == t2->data){ //
if(is_equal(t1->lchild,t2->lchild))
if(is_equal(t1->rchild,t2->rchild)){
return 1;
}
}
return 0;
}
9.이 진 트 리 의 깊이 구하 기
int hight_tree(bintree t){
int h,left,right;
if(!t){
return 0;
}
left = hight_tree(t->lchild);
right = hight_tree(t->rchild);
h = (left>right?left:right)+1;
return h;
}
본 고 에서 말 한 것 이 여러분 의 C 언어 프로 그래 밍 에 도움 이 되 기 를 바 랍 니 다.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
C 언어 체인 시계는 뱀을 탐식하는 작은 게임을 실현한다본고의 실례는 여러분에게 C 언어 체인표가 뱀 탐식 게임을 실현하는 구체적인 코드를 공유하여 참고하도록 하였으며, 구체적인 내용은 다음과 같다. 프로젝트 이름: 뱀놀이 운영 환경: Linux 프로그래밍 언어: C 언...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.