트리

트리

Terminology

• Tree: a finite set of one or more nodes s.t.

1. there is a specially designated node called the root
2. the remaining nodes are partitioned into n>= disjoint(교집합이 없는) sets T1, T2, ...Tn where each of there sets is a tree. (T1, T2, ... Tn: subtrees of the root)

Terminology(2)

• degree of a node: number of subtrees of the node.(노드에 붙어있는 subtree의 수)
• degree of a tree: maximun degree of the nodes in the tree.(노드의 degree의 최댓값)
• leaf(terminal node): a node with degree zero(서브트리가 없는 상태의 노드)
• parent, children, grand parent, grand children
• siblings: children of same parent.

Terminology(3)

• ancestors of a node: all the nodes along the path from the root to the node
• decendants of a node: all the nodes that are in its subtrees.
• level of a node
• height(depth) of a tree: maximum level of any node in the tree.
  (height와 depth는 위에서 아래, 아래에서 위로 보는 시점의 차이일 뿐 같은 의미임.)
• branch: 노드와 노드를 잇는 선(edge)

Representation of Trees(1)

1. List Representation - ( : level 증가, ): level 감소
   (A(B(E(K,L)F),C(G),D(H(M)I,J)))
   - fixed sized node is preferable
   - two link fields per node(left, right)

children node 가리키는 link tree node가 동일한 structure 가져야됨. link field 개수 같아야됨.
또는 최다 children 개수만큼 link field 개수 고정해야함.
->link field의 개수는 tree의 degree와 같게 만들면 general한 tree 만들 수 있음.
-> 한 degree만 엄청 크면 메모리 낭비가 심할 수 있음.
해결법: binary tree(이진 트리)를 쓴다!

Representation of Trees(2)

• Left Child-Right Sibling Representation:
  general한 tree를 이진 트리로 바꾸는 방법:
  노드의 left child는 child로 놔두과 left child의 sibling들을 서로 링크, 그리고 parent와 연결 끊기.
  그러면 general한 tree를 binary tree로 바꿀 수 있다.
  Right Siblingd은 Right Child로 바뀜.

Binary Trees (이진 트리)

• Definition) Binary Tree:
  Finite set of nodes that is either empty or consists of a root and two disjoint binary trees called the left subtree and the right subtree.

Tree vs. Binary Tree

• Binary tree와 tree의 차이점:
  • there is no tree with zero nodes.(트리는 노드가 있어야 한다.)
  • there is an empty binary tree.(이진트리는 empty일 수 있다.)
  • binary tree의 children은 순서를 갖는다.
  • Tree의 children은 순서를 갖지 않는다.

---

root A - right child B 와 root A - left child B 의 두 binary tree는 같지 않다.(순서가 존재하므로)

양의 정수 n (n > 0) 를 scanf_s 로 입력 받은 뒤, recursive function 을 이용하여 linked representation 으로 다음
규칙에 따라 binary tree 를 구성한 뒤, inorder traversal 결과를 화면 출력하라.

• data 값이 n 인 root node 를 생성한다.
• root 를 포함하여 tree 내의 모든 node 에 대해, node N 의 data 값이 k 이면, N 의 left child 는 k*2 를, N 의 right
  child 는 k+2 를 data 값으로 갖게 한다.
• node 의 data 값 k 가 k>5 이면 leaf node 가 되도록 (child 를 갖지 않도록) 처리한다.

#include <iostream>
#include <fstream>

using namespace std;

typedef struct node* treePointer;
typedef struct node {
	int data;
	treePointer leftChild, rightChild;
};
// 재귀로 이진트리 생성하기
// 부모노드 포인터 매개변수로 
treePointer recur(treePointer ptr) {
	treePointer leftNode, rightNode;

	leftNode = (treePointer)malloc(sizeof(*leftNode));
	rightNode = (treePointer)malloc(sizeof(*rightNode));

	if (ptr->data > 5) {
		ptr->leftChild = NULL; ptr->rightChild = NULL;
		return ptr;
	}
	leftNode->data = ptr->data * 2; //node의 데이터에 ptr->data*2값 넣음
	ptr->leftChild = recur(leftNode); //rightChild는 node를 가리킴

	rightNode->data = ptr->data + 2;
	ptr->rightChild = recur(rightNode); 

	return ptr;
}

void inorder(treePointer ptr) {
	if (ptr) {
		inorder(ptr->leftChild);
		printf("%d ", ptr->data);
		inorder(ptr->rightChild);
	}
}
int main() {
	printf("2022117156 독어독문학과 박상준\n");
	treePointer root;
	root = (treePointer)malloc(sizeof(*root));
	scanf_s("%d", &root->data);
	recur(root);
	inorder(root);
}

//    2
//  4   4
// 8 6 8 6