2. - (void)viewDidLoad {
    3.     [super viewDidLoad];
    4.     Node *node1 = [[Node alloc] init];
    5.     Node *node2 = [[Node alloc] init];
    6.     Node *node3 = [[Node alloc] init];
    7.     Node *node4 = [[Node alloc] init];
    8.     Node *node5 = [[Node alloc] init];
    9.     Node *node6 = [[Node alloc] init];
    10.     Node *node7 = [[Node alloc] init];
    11.     Node *node8 = [[Node alloc] init];
    13.     node1.value = 1;
    14.     node2.value = 2;
    15.     node3.value = 3;
    16.     node4.value = 4;
    17.     node5.value = 5;
    18.     node6.value = 6;
    19.     node7.value = 7;
    20.     node8.value = 8;
    22.     node1.left = node2;
    23.     node1.right = node3;
    24.     node2.left = node4;
    25.     node2.right = node5;
    26.     node3.left = node6;
    27.     node3.right = node7;
    28.     //    node4.right = node8;
    30.     //    先序 头左右     1245367
    31.     //    中序 左头右        4251637
    32.     //    后序  左右头    4526731
    34.     //    [self preOrderRecur:node1];
    35.     //    [self midOrderRecur:node1];
    36.     //    [self postOrderRecur:node1];
    38.     //创建二叉树
    39.   self.head = [self creatTree:@[@1,@2,@3,@4,@5,@6,@7]];
    40. [self widthOrder:node1];
    41.     // Do any additional setup after loading the view.
    42. }
    44. //递归-先序遍历（头左右）
    45. -(void)preOrderRecur:(Node *)head{
    46.     if (head == nil) {
    47.         return;
    48.     }
    50.     NSLog(@"%i",head.value);
    51.     [self preOrderRecur:head.left];
    52.     [self preOrderRecur:head.right];
    54. }
    56. -(Node *)creatTree:(NSArray *)arry{
    57.     static int  count = 0;
    58.     if (arry.count== 0) {
    59.         return nil;
    60.     }
    62.     Node *node = [[Node alloc]init];
    63.     if (count < arry.count) {
    64.         node.value = [arry[count++] intValue];
    65.         if (node.value == 0) {
    66.             return nil;
    67.         }
    68.         node.left = [self creatTree:arry];
    69.         node.right = [self creatTree:arry];
    71.     }
    72.     return node;
    77. }
    79. //递归-中序遍历（左头右）
    80. -(void)midOrderRecur:(Node *)head{
    81.     if (head == nil) {
    82.         return;
    83.     }
    85.     [self midOrderRecur:head.left];
    86.     NSLog(@"%i",head.value);
    87.     [self midOrderRecur:head.right];
    89. }
    91. //递归-后序遍历（左右头）
    92. -(void)postOrderRecur:(Node *)head{
    93.     if (head == nil) {
    94.         return;
    95.     }
    97.     [self postOrderRecur:head.left];
    98.     [self postOrderRecur:head.right];
    100. }
    101. /**
    102. //非递归-先序遍历（头左右）
    103. 使用栈，先进后出
    104. 1先把头节点放入站中，从栈中弹出一个节点cur
    105. 2 打印（处理）cur
    106. 3 先压cur的右节点，再压左节点（如果有的话）
    107. 4周而复始
    108. */
    109. -(void)preOrderUnRecur:(Node *)head{
    110.     NSLog(@"pre-order-unrecur");
    112.     if (head != nil) {
    113.         NSMutableArray *stack = [NSMutableArray array];
    114.         [stack addObject:head];
    115.         while (stack.count) {
    116.             head = stack.lastObject;
    117.             [stack removeLastObject];
    118.             NSLog(@"%i",head.value);
    119.             if (head.right != nil) {
    120.                 [stack addObject:head.right];
    121.             }
    123.             if (head.left != nil) {
    124.                 [stack addObject:head.left];
    125.             }
    126.         }
    127.     }
    129. }
    131. /**
    132. //非递归-后序遍历
    133. 使用两个栈，先进后出
    134. 1初始化两个栈，stack， shoustack（回收站），先把头节点放入站中，从栈中弹出一个节点cur
    135. 2 将cur放入 回收栈，
    136. 3 先压cur的左节点，再压右节点（如果有的话）
    137. 4周而复始
    138. 5打印回收栈里的节点（先进后出）
    140. */
    141. -(void)postOrderUnRecur:(Node *)head{
    142.     NSLog(@"post-order-unrecur");
    144.     if (head != nil) {
    145.         NSMutableArray *stack = [NSMutableArray array];
    146.         NSMutableArray *shouStack = [NSMutableArray array];
    147.         [stack addObject:head];
    148.         while (stack.count) {
    149.             head = stack.lastObject;
    150.             [stack removeLastObject];
    151.             [shouStack addObject:head];
    153.             if (head.left != nil) {
    154.                 [stack addObject:head.left];
    155.             }
    157.             if (head.right != nil) {
    158.                 [stack addObject:head.right];
    159.             }
    160.         }
    162.         while (shouStack.count) {
    163.             NSLog(@"%i",((Node *)shouStack.lastObject).value);
    164.             [shouStack removeLastObject];
    165.         }
    167.     }
    169. }
    171. /**
    172. //非递归-中序遍历
    173. 使用栈
    174. 1每颗子树，整棵树左边界进栈，
    175. 2然后依次弹出的过程中，打印弹出的节点，并对弹出的节点的右树进行第一步的循环
    176. 3周而复始
    177. */
    178. -(void)midOrderUnRecur:(Node *)head{
    179.     NSLog(@"min-order-unrecur");
    181.     if (head != nil) {
    182.         NSMutableArray *stack = [NSMutableArray array];
    184.         while (stack.count || head!= nil) {
    185.             if (head != nil) {
    186.                 [stack addObject:head];
    187.                 head = head.left;
    188.             } else {
    189.                 head = stack.lastObject;
    190.                 [stack removeLastObject];
    191.                 NSLog(@"%i",head.value);
    192.                 head = head.right;
    193.             }
    194.         }
    195.     }
    196. }
    199. //深度优先遍历：
    200. //对于二叉树来说，它的深度优先遍历就是它的先序遍历
    203. /**
    204. 宽度优先遍历 :
    205. 使用队列的特性：先进先出
    206. 1 先把头结点放进队列中
    207. 2 取出一节点记作cur，然后打印cur
    208. 3 先压cur的左节点，再压cur的右节点，
    209. 4周而复始就可以了。
    210. */
    211. -(void)widthOrder:(Node *)head{
    212.     if (head == nil) {
    213.         return;
    214.     }
    215.     NSMutableArray *queue = [NSMutableArray array];
    216.     [queue addObject:head];
    217.     while (queue.count) {
    218.         Node *cur = queue.firstObject;
    219.         [queue removeObjectAtIndex:0];
    220.         NSLog(@"%i",cur.value);
    221.         if (cur.left != nil) {
    222.             [queue addObject:cur.left];
    223.         }
    225.         if (cur.right != nil) {
    226.             [queue addObject:cur.right];
    227.         }
    228.     }
    230. }
    232. //求和
    233. -(void)sum1:(Node *)head lastnum:(int) lastnum{
    234.     if (head == nil) {
    235.         return;
    236.     }
    237.     static int sum = 0;
    238.     int lastnumber = lastnum*10 + head.value;
    241.     if (head.left == nil && head.right == nil) {
    242.         sum+= lastnumber;
    243.         NSLog(@"求和%i",sum);
    244.     }
    246.     if (head.left != nil) {
    247.         [self sum1:head.left lastnum:lastnumber];
    248.     }
    250.     if (head.right != nil) {
    251.         [self sum1:head.right lastnum:lastnumber];
    252.     }
    254. }
    258. //void DepthFirstSearch(BitNode *root)
    259. //41 {
    260. //42     stack<BitNode*> nodeStack;
    261. //43     nodeStack.push(root);
    262. //44     while (!nodeStack.empty())
    263. //45     {
    264. //46         BitNode *node = nodeStack.top();
    265. //47         cout << node->data << ' ';
    266. //48         nodeStack.pop();
    267. //49         if (node->right)
    268. //50         {
    269. //51             nodeStack.push(node->right);
    270. //52         }
    271. //53         if (node->left)
    272. //54         {
    273. //55             nodeStack.push(node->left);
    274. //56         }
    275. //57     }
    276. //58 }
    277. //59
    280. //60 //广度优先搜索
    281. //61 void BreadthFirstSearch(BitNode *root)
    282. //62 {
    283. //63     queue<BitNode*> nodeQueue;
    284. //64     nodeQueue.push(root);
    285. //65     while (!nodeQueue.empty())
    286. //66     {
    287. //67         BitNode *node = nodeQueue.front();
    288. //68         cout << node->data << ' ';
    289. //69         nodeQueue.pop();
    290. //70         if (node->left)
    291. //71         {
    292. //72             nodeQueue.push(node->left);
    293. //73         }
    294. //74         if (node->right)
    295. //75         {
    296. //76             nodeQueue.push(node->right);
    297. //77         }
    298. //78     }
    299. //79 }
    303. @end