1 #include <stdio.h>  2 #include <stdlib.h>  3 #include <math.h>  4 #include <stack>  5 #include <queue>  6   7 using namespace std;  8   9 typedef int ItemType; 10 typedef struct Node{ 11     ItemType data; 12     struct Node *lchild, *rchild; 13 }Node, *PNode; 14 //递归创建添加新节点 15 void insertNode(PNode *root, ItemType data) 16 { 17     if(*root == NULL) 18     { 19         *root = (PNode)malloc(sizeof(Node)); 20         (*root)->data =http://www.mamicode.com/ data; 21         (*root)->lchild = (*root)->rchild = NULL; 22     } 23     else 24     { 25         if(data < (*root)->data) 26             insertNode(&(*root)->lchild, data); 27         else 28             insertNode(&(*root)->rchild, data); 29     } 30 } 31 //递归前序遍历 32 void preOrder(PNode root) 33 { 34     if(root == NULL) 35         return; 36     printf("%d ", root->data); 37     preOrder(root->lchild); 38     preOrder(root->rchild); 39 } 40 //递归中序遍历 41 void inOrder(PNode root) 42 { 43     if(root == NULL) 44         return; 45     inOrder(root->lchild); 46     printf("%d ", root->data); 47     inOrder(root->rchild); 48 } 49 //递归后续遍历 50 void postOrder(PNode root) 51 { 52     if(root == NULL) 53         return; 54     postOrder(root->lchild); 55     postOrder(root->rchild); 56     printf("%d ", root->data); 57 } 58 //非递归前序遍历 59 void preOrder_NonRecursion(PNode root) 60 { 61     stack<PNode> s; 62     PNode p = root; 63     while(p != NULL || !s.empty()) 64     { 65         if(p != NULL) 66         { 67             printf("%d ", p->data); 68             s.push(p); 69             p = p->lchild; 70         } 71         else 72         { 73             p = s.top(); 74             s.pop(); 75             p = p->rchild; 76         } 77     } 78 } 79 //非递归中序遍历 80 void inOrder_NonRecursion(PNode root) 81 { 82     stack<PNode> s; 83     PNode p = root; 84     while(p != NULL || !s.empty()) 85     { 86         if(p != NULL) 87         { 88             s.push(p); 89             p = p->lchild; 90         } 91         else 92         { 93             p = s.top(); 94             printf("%d ", p->data); 95             s.pop(); 96             p = p->rchild; 97         } 98     } 99 }100 //非递归后续遍历101 void postOrder_NonRecursion(PNode root)102 {103     stack<pair<PNode, bool> > s;104     PNode p = root;105     while(p != NULL || !s.empty())106     {107         if(p != NULL)108         {109             s.push(make_pair(p, false));110             p = p->lchild;111         }112         else113         {114             if(s.top().second == false)115             {116                 s.top().second = true;117                 p = s.top().first->rchild;118             }119             else120             {121                 printf("%d ", s.top().first->data);122                 s.pop();123             }124         }125     }126 }127 //层级遍历128 void levelOrder(PNode root)129 {130     queue<PNode> q;131     PNode p = root;132     if(p != NULL)133         q.push(p);134     while(!q.empty())135     {136         p = q.front();137         printf("%d ", p->data);138         if(p->lchild != NULL)139             q.push(p->lchild);140         if(p->rchild != NULL)141             q.push(p->rchild);142         q.pop();143     }144 }145 //求一层的所有节点146 void specifyLevelNode(PNode root, int h)//h是指定的高度147 {148     if(root == NULL)149         return;150     queue<PNode> q;151     PNode p = root;152     q.push(p);153     int last_level_number = 1;//用来标记以上所有层多少个154     int visit_number = 0;155     int in_queue_number = 1;//入队的多少个156     int height = 0;157     while (!q.empty())158     {159         visit_number++;160         p = q.front();161         q.pop();162 163         if (p->lchild != NULL)164         {165             q.push(p->lchild);166             in_queue_number++;167             if (h - 2 == height)/*因为这个高度执行到后面才++， 所以h要减一，168             还有就是当前是p->lchild而不是p，所以在减一*/169                 printf("%d ", p->lchild->data);170         }171         if(p->rchild != NULL)172         {173             q.push(p->rchild);174             in_queue_number++;175             if (h - 2== height)//同上176                 printf("%d ", p->rchild->data);177         }178 179         if(visit_number == last_level_number)180         {181             height++;182             last_level_number = in_queue_number;183         }184     }185 }186 //递归求树的深度187 int getDepth(PNode root)188 {189     int d1, d2;190     if(root == NULL)191         return 0;192     d1 = getDepth(root->lchild);193     d2 = getDepth(root->rchild);194     return (d1 > d2 ? d1 : d2) + 1;195 }196 //非递归求数的深度197 int getDepth_NonRecursion(PNode root)198 {199     if(root == NULL)200         return 0;201     queue<PNode> q;202     PNode p = root;203     q.push(p);204     int last_level_number = 1;//用来标记以上所有层多少个205     int visit_number = 0;206     int in_queue_number = 1;//入队的多少个207     int height = 0;208     while (!q.empty())209     {210         visit_number++;211         p = q.front();212         q.pop();213 214         if (p->lchild != NULL)215         {216             q.push(p->lchild);217             in_queue_number++;218         }219         if(p->rchild != NULL)220         {221             q.push(p->rchild);222             in_queue_number++;223         }224 225         if(visit_number == last_level_number)226         {227             height++;228             last_level_number = in_queue_number;229         }230     }231     return height;232 }233 //求二叉树中相距最远的两个节点之间的距离234 int getMaxDistance(PNode root)235 {236     if(root == NULL)237         return 0;238     return getDepth(root->lchild) + getDepth(root->rchild);239 }240 //求两节点的最近的共同祖先241 void getCommonAncestor(PNode root, ItemType n1, ItemType n2)242 {243     if(root == NULL)244         return;245     while((n1 < root->data && n2 < root->data) || (n1 > root->data && n2 > root->data) )246     {247         if(n1 < root->data)248             root = root->lchild;249         else250             root = root->rchild;251     }252     printf("latest common ancestor: %d\n", root->data);253 }254 255 //求路径和为指定值的所有路径256 257 int main()258 {259     int n;260     scanf("%d", &n);261     int t;262     PNode root = NULL;263     for(int i = 0; i < n; i++)264     {265         scanf("%d", &t);266         insertNode(&root, t);267     }268     printf("Previous Order Traverse:\n");269     preOrder(root);270     printf("\nIn Order Traverse:\n");271     inOrder(root);272     printf("\nPost Order Traverse:\n");273     postOrder(root);274     printf("\nNon-Recursion Previous Order Traverse:\n");275     preOrder_NonRecursion(root);276     printf("\nNon-Recursion In Order Traverse:\n");277     inOrder_NonRecursion(root);278     printf("\nNon-Recursion Post Order Traverse:\n");279     postOrder_NonRecursion(root);280     printf("\nLevel Order Traverse:\n");281     levelOrder(root);282     printf("\nThe depth of tree: %d\n", getDepth(root));283     printf("The depth of tree(Non-Recursion): %d\n", getDepth_NonRecursion(root));284     specifyLevelNode(root, 3);//求第三层的所有节点285     printf("\nThe max distance: %d\n", getMaxDistance(root));286     getCommonAncestor(root, 7, 4);//测试数据，得出7和4的最近祖先287     288     return 0;289 }