1 #include <cstdio>  2 #include <cstdlib>  3 #include <queue>  4 #include <stack>  5   6 #define null 0  7 #define NEXTLINE printf("\n")  8 #define MAX(x, y) ((x)>(y)?(x):(y))  9  10 int max = 1<<31; 11 int min = ~(1<<31); 12  13 typedef int Item; 14 typedef struct node *link; 15 struct node { 16     Item item; 17     link l, r; 18 }; 19 // 初始化树  20 link 21 InitTree(Item item) 22 { 23     link t = (link)malloc(sizeof *t); 24     if (t == null) { 25         return null; 26     } 27     t->item = item; 28     t->l = null; 29     t->r = null; 30     return t; 31 } 32 // 加入左子节点  33 link 34 AddLeftNode(link t, Item item) 35 { 36     if (t == null) { 37         return null; 38     } 39     link newNode = (link)malloc(sizeof *newNode); 40     if (newNode == null) { 41         return null; 42     } 43     t->l = newNode; 44     newNode->item = item; 45     newNode->l = null; 46     newNode->r = null; 47     return newNode; 48 } 49 // 加入右子节点  50 link 51 AddRightNode(link t, Item item) 52 { 53     if (t == null) { 54         return null; 55     } 56     link newNode = (link)malloc(sizeof *newNode); 57     if (newNode == null) { 58         return null; 59     } 60     t->r = newNode; 61     newNode->item = item; 62     newNode->l = null; 63     newNode->r = null; 64     return newNode; 65 } 66 // 打印节点中的内容  67 void 68 PrintItem(link t) 69 { 70     printf("%d\t", t->item); 71 } 72 // 前序遍历(递归)  73 void 74 PreTraverse(link t) 75 { 76     if (t == null) { 77         return; 78     } 79     PrintItem(t); 80     PreTraverse(t->l); 81     PreTraverse(t->r); 82 } 83 // 中序遍历(递归)  84 void 85 InTraverse(link t) 86 { 87     if (t == null) { 88         return; 89     } 90     InTraverse(t->l); 91     PrintItem(t); 92     InTraverse(t->r); 93 } 94 // 后序遍历(递归)  95 void 96 PostTraverse(link t) 97 { 98     if (t == null) { 99         return;100     }101     PostTraverse(t->l);102     PostTraverse(t->r);103     PrintItem(t);104 }105 // 层次遍历(非递归) 106 void107 LevelTraverse(link t)108 {109     if (t == null) {110         return;111     }112     std::queue<link> linkQueue;113     linkQueue.push(t);114     while (!linkQueue.empty()) {115         PrintItem(t = linkQueue.front());116         linkQueue.pop();117         if (t->l != null) linkQueue.push(t->l);118         if (t->r != null) linkQueue.push(t->r);119     }120 }121 // 前序遍历(非递归) 122 void123 PreTraverseNR(link t)124 {125     if (t == null) {126         return;127     }128     std::stack<link> linkStack;129     linkStack.push(t);130     while (!linkStack.empty()) {131         PrintItem(t = linkStack.top());132         linkStack.pop();133         if (t->r != null) linkStack.push(t->r);134         if (t->l != null) linkStack.push(t->l);135     }136 }137 // 找最大节点 138 void139 FindMax(link t)140 {141     if (t == null) {142         return;143     }144     if (max < t->item) {145         max = t->item;146     }147     FindMax(t->l);148     FindMax(t->r);149 }150 // 找最小节点 151 void152 FindMin(link t)153 {154     if (t == null) {155         return;156     }157     if (min > t->item) {158         min = t->item;159     }160     FindMin(t->l);161     FindMin(t->r);162 }163 // 计算深度(从0开始计算) 164 int165 CountDepth(link t)166 {167     if (t == null) {168         return -1;169     }170     return MAX(CountDepth(t->l), CountDepth(t->r)) + 1;171 }172 // 计算所有节点数目 173 int174 CountNodes(link t)175 {176     if (t == null) {177         return 0;178     }179     return CountNodes(t->l) + CountNodes(t->r) + 1;180 }181 // 计算叶子节点数目 182 int183 CountLeaves(link t)184 {185     if (t == null) {186         return 0;187     }188     if (!CountLeaves(t->l) && !CountLeaves(t->r)) {189         return 1;190     }191     return CountLeaves(t->l) + CountLeaves(t->r);192 }193 // 清空一棵树 194 void195 DeleteTree(link t)196 {197     if (t == null) {198         return;199     }200     if (!(t->l) && !(t->r)) {201         free(t);202         return;203     }204     DeleteTree(t->l);205     DeleteTree(t->r);206     free(t);207 }208 209 int210 main(int argc, char** argv)211 {212     link t, t1, t2, t3, t4;213     t = InitTree(1);214     t1 = AddLeftNode(t, 2);215     t2 = AddRightNode(t, 3);216     t3 = AddLeftNode(t1, 4);217     t4 = AddRightNode(t1, 5);218     219     220     PreTraverse(t);221     NEXTLINE;222     InTraverse(t);223     NEXTLINE;224     PostTraverse(t);225     NEXTLINE;226     LevelTraverse(t);227     NEXTLINE;228     PreTraverseNR(t);229     NEXTLINE;230  231     FindMax(t);232     FindMin(t);233     printf("Maxima Item in tree: %d\n", max);234     printf("Minima Item in tree: %d\n", min);235     236     printf("Depth of the tree(start from 0): %d\n", CountDepth(t));237  238     printf("Number of the nodes of the tree: %d\n", CountNodes(t));239     240     printf("Number of the leaves of the tree: %d\n", CountLeaves(t));241     242     243     DeleteTree(t);244     245     system("pause");246     return 0;247 }