# C++ 완전 이진트리

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151

#pragma once //================================ // 완전 이진 트리 // // 배열을 이용한 구현 //================================ /*NULL 의 경우 0으로 정의 되있는경우가 있으므로, 다른이름으로 정의해준다.. (중복되면 안되므로)*/ #define MAXNODE 100 #define nodeNULL -1 //빈노드를 의미 #include <iostream> template<typename T> class cBinaryTreeByArray { public: cBinaryTreeByArray(); void insert(T num); void Traverse(int type); // type -> 순회방법 typedef struct completeBinaryTreeByArray { T Item; int leftChild; // memorize index num int rightChild;// memorize index num }completeBinaryTreeByArray; private: /*Insert*/ void insertIn(T num, int subRoot); /* Traverse */ // 출력을 목적으로 작성된 순회메소드. void preOrder(int subRoot); void inOrder(int subRoot); void postOrder(int subRoot); completeBinaryTreeByArray completeTree[MAXNODE]; int curNodeNum; //현재 노드 갯수 int root; // 최상위 루트 }; template<typename T> cBinaryTreeByArray<T>::cBinaryTreeByArray() { // 최상위 루트 root = 0; // 현재 노드 갯수 초기화. 현재 노드 갯수는 배열 인덱스 범위와 1의 차이 curNodeNum = 0; // 구조체 배열 초기화. for (int i = 0; i < MAXNODE; i++) { completeTree[i].Item = 0; completeTree[i].leftChild = nodeNULL; completeTree[i].rightChild = nodeNULL; } } template<typename T> void cBinaryTreeByArray<T>::insert(T num) { insertIn(num, root); } template<typename T> void cBinaryTreeByArray<T>::insertIn(T num, int subRoot) { if (curNodeNum == 0) // 최상위 루트가 존재하지 않는다면. { completeTree[curNodeNum].Item = num; completeTree[2 * curNodeNum + 1].leftChild = nodeNULL; // 2k+2 completeTree[2 * curNodeNum + 2].rightChild = nodeNULL; // 2k+2 curNodeNum++; } else if (completeTree[subRoot].leftChild == nodeNULL) // 왼쪽이 비었다. { completeTree[curNodeNum].Item = num; completeTree[2 * curNodeNum + 1].leftChild = nodeNULL; completeTree[2 * curNodeNum + 2].rightChild = nodeNULL; // 새 노드생성후 부모 노드의 왼쪽에 붙여준다. completeTree[subRoot].leftChild = curNodeNum; curNodeNum++; } else if (completeTree[subRoot].rightChild == nodeNULL) // 오른쪽이 비었다. { completeTree[curNodeNum].Item = num; completeTree[2 * curNodeNum + 1].leftChild = nodeNULL; completeTree[2 * curNodeNum + 2].rightChild = nodeNULL; // 새 노드생성후 부모 노드의 왼쪽에 붙여준다. completeTree[subRoot].rightChild = curNodeNum; curNodeNum++; } else insertIn(num, ++subRoot); // root 넘버는 1씩 증가하므로 } template<typename T> void cBinaryTreeByArray<T>::Traverse(int type) { switch (type) { case 0: preOrder(root); break; case 1: inOrder(root); break; case 2: postOrder(root); break; default: break; } } template<typename T> void cBinaryTreeByArray<T>::preOrder(int subRoot) { if (subRoot != nodeNULL) // baseCase { std::cout << completeTree[subRoot].Item << std::endl; preOrder(completeTree[subRoot].leftChild); preOrder(completeTree[subRoot].rightChild); } } template<typename T> void cBinaryTreeByArray<T>::inOrder(int subRoot) { if (subRoot != nodeNULL) { inOrder(completeTree[subRoot].leftChild); std::cout << completeTree[subRoot].Item << std::endl; inOrder(completeTree[subRoot].rightChild); } } template<typename T> void cBinaryTreeByArray<T>::postOrder(int subRoot) { if (subRoot != nodeNULL) { postOrder(completeTree[subRoot].leftChild); postOrder(completeTree[subRoot].rightChild); std::cout << completeTree[subRoot].Item << std::endl; } }