数学建模社区-数学中国

标题: 【数据结构】二叉树的遍历：前序，中序，后序的递归结构遍历 [打印本页]
作者: 杨利霞    时间: 2022-9-15 11:55
标题: 【数据结构】二叉树的遍历：前序，中序，后序的递归结构遍历
【数据结构】二叉树的遍历：前序，中序，后序的递归结构遍历
3 m* {- m! m  @7 r7 P$ P* \
/ g" v& h% }7 X. v4 O[color=rgba(0, 0, 0, 0.749019607843137)]文章目录
6 s; M1 C0 Y+ ]( \3 H* h[color=rgba(0, 0, 0, 0.749019607843137)]前言' `9 c: k( X6 g$ W5 u3 b5 l
[color=rgba(0, 0, 0, 0.749019607843137)]1.二叉树的遍历方式
; Y+ ]  g$ K( _/ l[color=rgba(0, 0, 0, 0.749019607843137)]2.二叉树的遍历及相关函数（代码实现）1 u( P8 M8 L+ s9 v) m
[color=rgba(0, 0, 0, 0.749019607843137)]2.1前序/中序/后序的遍历
9 m8 }. H& P0 P  f- [8 u[color=rgba(0, 0, 0, 0.749019607843137)]2.2计算二叉树的大小2 p% J' _/ X  _0 V1 H- z+ T! e
[color=rgba(0, 0, 0, 0.749019607843137)]2.3计算二叉树叶子结点的个数
  Y1 b7 [9 z" s# r$ ^3 J[color=rgba(0, 0, 0, 0.749019607843137)]2.4计算二叉树的高度
: ^3 V& L, q- o7 r9 K: x; P[color=rgba(0, 0, 0, 0.749019607843137)]2.5计算第K层结点的个数
7 Z; u6 R) d5 A' z7 N[color=rgba(0, 0, 0, 0.749019607843137)]2.6二叉树查找! ?& a! U6 A6 U) k
[color=rgba(0, 0, 0, 0.749019607843137)]前言$ [& b) f2 @# |- n% i( `. q& C
[color=rgba(0, 0, 0, 0.749019607843137)]在学习二叉树的遍历之前，我们需要先创建一棵二叉树，然后才能学习其相关的基本操作，由于现在我们对二叉树结构的掌握还在初阶部分，为了降低大家的学习成本，我们先手动快速创建一棵简单的二叉树，快速进入二叉树的操作学习，这个方法在我们调试程序代码的时候，也非常适用。等二叉树结构了解的差不多时，我们再继续研究二叉树真正的创建方式。
9 g6 v. o) v; d) c, I/ ^[color=rgba(0, 0, 0, 0.749019607843137)]
7 V5 z1 W8 e% e) |) I/ B
2 q# G) t2 j( G[color=rgba(0, 0, 0, 0.749019607843137)]1.二叉树的遍历方式( w$ k2 }4 k: M" T4 n* B
[color=rgba(0, 0, 0, 0.749019607843137)]
: X4 j; f% C6 ~
- z! F* {8 a* ?[color=rgba(0, 0, 0, 0.749019607843137)]按照规则，二叉树的遍历有：前序/中序/后序的递归结构遍历访问顺序：2 C1 f  Q4 W4 ^, o# k
[color=rgba(0, 0, 0, 0.749019607843137)]3 x8 F2 e1 l& i
% w) i0 O! |- X( C, H6 M
[color=rgba(0, 0, 0, 0.749019607843137)]1. 前序遍历（先序，先根):根——左子树——右子树( ]* X4 ^: L) m
[color=rgba(0, 0, 0, 0.749019607843137)]
5 k+ T9 N0 X) j) k  R5 W
5 d0 j9 R, K4 \) O& _, h[color=rgba(0, 0, 0, 0.749019607843137)], @7 ^: ~3 D, ]( r  w3 s2 y8 W

0 E# b; E4 }$ z( E; V; @2 i[color=rgba(0, 0, 0, 0.749019607843137)]2. 中序遍历（中根）：左子树——根——右子树- ^; \! w3 ^; i+ u# B# N) u3 _
[color=rgba(0, 0, 0, 0.749019607843137)]) A8 i2 g, p8 i
8 o+ Q- w+ J  F3 t! D3 a5 z: V2 W: I
[color=rgba(0, 0, 0, 0.749019607843137)]! x9 O; A( D- ^# T3 E
- k6 O1 r" P0 K. O  s
[color=rgba(0, 0, 0, 0.749019607843137)]3. 后序遍历（后根）：左子树——右子树——根( n# P/ \) Y( Y0 E
[color=rgba(0, 0, 0, 0.749019607843137)]
/ E3 h- u: s$ w7 ~1 E* o9 _( p7 X/ h
. E( g& C) R. k[color=rgba(0, 0, 0, 0.749019607843137)]
# ?% B0 q3 d+ F, c+ E  y8 d2 f
: X( _4 D- m7 w# x[color=rgba(0, 0, 0, 0.749019607843137)]2.二叉树的遍历及相关函数（代码实现）
  X5 t  @0 h3 x. J& `7 U[color=rgba(0, 0, 0, 0.749019607843137)]思路：分而治之
7 _. u. e) ], H. d7 I[color=rgba(0, 0, 0, 0.749019607843137)]1.首先我们要用简单的方式先创建出一棵二叉树，并赋予数据；
, U, }( h! l: _+ I2 K$ t& r$ Q1 F[color=rgba(0, 0, 0, 0.749019607843137)]2.采用递归的方式，分别实现前序/中序/后序遍历这棵二叉树；- o6 h; E: ]- X+ |" v! I4 B! C
[color=rgba(0, 0, 0, 0.749019607843137)]3.尝试计算这个二叉树的大小（利用递归）；, K9 U% n2 W( M4 v
[color=rgba(0, 0, 0, 0.749019607843137)]4.尝试计算叶子结点的个数（利用递归）；
  P) ?$ G  r  @. e[color=rgba(0, 0, 0, 0.749019607843137)]5.尝试计算二叉树的高度（利用递归）；
3 {9 R( ~1 @; r+ n, ]! v[color=rgba(0, 0, 0, 0.749019607843137)]6.尝试写出计算第K层结点的个数的函数（利用递归）；4 t2 h6 a" b  Y
[color=rgba(0, 0, 0, 0.749019607843137)]7.尝试写出二叉树查找的函数（利用递归）。! y+ G. w' q  v: R8 y
[color=rgba(0, 0, 0, 0.749019607843137)]
/ g, q: ^+ R2 }9 V# ~& Z" j5 I7 b2 A# R; Q; D& K5 |
[color=rgba(0, 0, 0, 0.749019607843137)]2.1前序/中序/后序的遍历
: Q: e4 M. ^, i3 Y& Q& ^7 o[color=rgba(0, 0, 0, 0.749019607843137)]#define _CRT_SECURE_NO_WARNINGS 1
( V5 l3 D! p2 ]8 B- G[color=rgba(0, 0, 0, 0.749019607843137)]#include<stdio.h>0 E3 ~2 {# u1 f5 k' e
[color=rgba(0, 0, 0, 0.749019607843137)]#include<assert.h>
* R9 a6 B' \' ^, Y3 L4 H[color=rgba(0, 0, 0, 0.749019607843137)]#include<stdlib.h>$ D! L; A; C; K* p8 C' N+ ]5 A
[color=rgba(0, 0, 0, 0.749019607843137)]
1 N" D, O( Q% R* ~6 U
% e- z: ]* {# e$ P1 y( U  _[color=rgba(0, 0, 0, 0.749019607843137)]typedef int BTDataType;5 Y* Q1 j/ v' ?8 Y
[color=rgba(0, 0, 0, 0.749019607843137)]
$ g& ^7 w9 S9 Q' K8 C
# z3 H- v0 _9 u+ M/ V[color=rgba(0, 0, 0, 0.749019607843137)]//定义二叉树结点的结构体
/ g( N' H/ c! `* L. c4 K+ L[color=rgba(0, 0, 0, 0.749019607843137)]typedef struct BinaryTreeNode
* ?8 S& V& J% x' u[color=rgba(0, 0, 0, 0.749019607843137)]{) ?( g( ~* ^: c
[color=rgba(0, 0, 0, 0.749019607843137)]        BTDataType data;
# q- X/ L7 u  A2 ^4 l[color=rgba(0, 0, 0, 0.749019607843137)]        struct BinaryTreeNode* left;
; f  _! m. K% I( |% o[color=rgba(0, 0, 0, 0.749019607843137)]        struct BinaryTreeNode* right;
# d" W/ v) S4 \% @8 y# H[color=rgba(0, 0, 0, 0.749019607843137)]}BTNode;
2 k5 j. u8 {, D& r' q' }[color=rgba(0, 0, 0, 0.749019607843137)]* X3 ]7 Z! E" ~- X- C
, m- K2 Y% K: Z' M# P7 L# M  [( j
[color=rgba(0, 0, 0, 0.749019607843137)]//前序遍历
5 W/ P4 h  T" a7 r* t[color=rgba(0, 0, 0, 0.749019607843137)]void PreOrder(BTNode* root)# r2 s( h# F! u, H7 j
[color=rgba(0, 0, 0, 0.749019607843137)]{
+ B  R! p6 p( z; m( w[color=rgba(0, 0, 0, 0.749019607843137)]        if (root == NULL)9 v  R' D2 z& s( W3 ]
[color=rgba(0, 0, 0, 0.749019607843137)]        {& T3 D0 ?1 N/ L5 f  K
[color=rgba(0, 0, 0, 0.749019607843137)]                printf("NULL ");
9 B8 d$ S; q" o. B$ d' \( A[color=rgba(0, 0, 0, 0.749019607843137)]                return;
; h" i0 I! ]/ b[color=rgba(0, 0, 0, 0.749019607843137)]        }
" e% u; t( g  @  l5 W5 f[color=rgba(0, 0, 0, 0.749019607843137)]        printf("%d ", root->data);
" n8 j$ Y, ], |7 m& K9 W( {[color=rgba(0, 0, 0, 0.749019607843137)]        PreOrder(root->left);
2 B+ V; b- V9 s% D% ?, O, {3 {) e* {[color=rgba(0, 0, 0, 0.749019607843137)]        PreOrder(root->right);0 x" f* d5 l, |6 X6 _  `
[color=rgba(0, 0, 0, 0.749019607843137)]}
" X4 e7 |5 G6 n0 b3 B" j# |[color=rgba(0, 0, 0, 0.749019607843137)]//中序遍历5 w. @3 `. L8 m  y! b5 C, f
[color=rgba(0, 0, 0, 0.749019607843137)]void InOrder(BTNode* root)
0 @5 T* Y7 P) c' U5 z4 q5 X[color=rgba(0, 0, 0, 0.749019607843137)]{3 U. y; F5 _& J8 Y9 J
[color=rgba(0, 0, 0, 0.749019607843137)]        if (root == NULL)
& f" w& w- m) H! W# P0 B2 O- s[color=rgba(0, 0, 0, 0.749019607843137)]        {
, _+ o7 w1 j' B" K4 ^[color=rgba(0, 0, 0, 0.749019607843137)]                printf("NULL ");
6 E6 }2 p, {( b" i5 ], f0 `$ w[color=rgba(0, 0, 0, 0.749019607843137)]                return;
% q  j' `" d$ Q[color=rgba(0, 0, 0, 0.749019607843137)]        }
! x7 m- |+ }1 _0 j3 |0 S1 ^[color=rgba(0, 0, 0, 0.749019607843137)]        InOrder(root->left);
  m0 H% j2 U; @. l5 F[color=rgba(0, 0, 0, 0.749019607843137)]        printf("%d ", root->data);3 i3 c3 I' `5 C1 j
[color=rgba(0, 0, 0, 0.749019607843137)]        InOrder(root->right);
( Y8 q# A7 O7 r; c. s* c[color=rgba(0, 0, 0, 0.749019607843137)]}
7 ?: w' C4 d# R3 Q& e3 v! h- E[color=rgba(0, 0, 0, 0.749019607843137)]//后序遍历( B, }0 j8 b: e$ G
[color=rgba(0, 0, 0, 0.749019607843137)]void PostOrder(BTNode* root)0 \" z4 e! ~3 T5 I3 f5 P: u
[color=rgba(0, 0, 0, 0.749019607843137)]{0 V& n8 P, G( b& h4 m/ F
[color=rgba(0, 0, 0, 0.749019607843137)]        if (root == NULL)
1 w5 h4 @% a) ^% V: a- @  p[color=rgba(0, 0, 0, 0.749019607843137)]        {
4 _) w# o3 E; T7 L) E4 u+ A[color=rgba(0, 0, 0, 0.749019607843137)]                printf("NULL ");
. ?" Y! z. Y: C( D3 k! ?6 t5 X( j7 v[color=rgba(0, 0, 0, 0.749019607843137)]                return;) ~2 v, f. I5 p) A7 h. z
[color=rgba(0, 0, 0, 0.749019607843137)]        }
" i' _# t5 x! o[color=rgba(0, 0, 0, 0.749019607843137)]        PostOrder(root->left);
% U. {# O! b& i/ Q. K! h! p[color=rgba(0, 0, 0, 0.749019607843137)]        PostOrder(root->right);: X1 X1 H% e( }" c& b5 q0 C/ `
[color=rgba(0, 0, 0, 0.749019607843137)]        printf("%d ", root->data);
% Q; T3 }0 B9 |7 I" X! v3 P[color=rgba(0, 0, 0, 0.749019607843137)]}" `9 X4 \8 Q& e0 ]
[color=rgba(0, 0, 0, 0.749019607843137)]//先创建一个简单的二叉树结构" l5 f+ B2 D( G; Z' y! _/ h9 e; R% ]
[color=rgba(0, 0, 0, 0.749019607843137)]BTNode* CreateTree()
% l# n- Z( t/ G4 S: K( V[color=rgba(0, 0, 0, 0.749019607843137)]{7 B- O& ]. g7 y; K
[color=rgba(0, 0, 0, 0.749019607843137)]        //先动态开辟6个结点的空间
# M1 Z3 \: I9 A" q: }+ j; q0 N7 d[color=rgba(0, 0, 0, 0.749019607843137)]        BTNode* n1 = (BTNode*)malloc(sizeof(BTNode));
1 k8 K- _0 ^6 v[color=rgba(0, 0, 0, 0.749019607843137)]        assert(n1);
2 T" o+ v4 c) g! o[color=rgba(0, 0, 0, 0.749019607843137)]        BTNode* n2 = (BTNode*)malloc(sizeof(BTNode));8 r2 h1 i1 N4 F9 |4 M
[color=rgba(0, 0, 0, 0.749019607843137)]        assert(n2);$ {3 p* z4 z% C8 z; h! U& K) a" s
[color=rgba(0, 0, 0, 0.749019607843137)]        BTNode* n3 = (BTNode*)malloc(sizeof(BTNode));
; q, b/ H, P! t$ K[color=rgba(0, 0, 0, 0.749019607843137)]        assert(n3);
2 |* d( S/ d% _( x[color=rgba(0, 0, 0, 0.749019607843137)]        BTNode* n4 = (BTNode*)malloc(sizeof(BTNode));
! i3 [6 T( [* I$ p[color=rgba(0, 0, 0, 0.749019607843137)]        assert(n4);% l3 ^# Y5 g* Z  G% F9 s6 D. v
[color=rgba(0, 0, 0, 0.749019607843137)]        BTNode* n5 = (BTNode*)malloc(sizeof(BTNode));5 [$ Z7 \' J4 ~( b
[color=rgba(0, 0, 0, 0.749019607843137)]        assert(n5);
$ @& F) @2 ~( o! a' w[color=rgba(0, 0, 0, 0.749019607843137)]        BTNode* n6 = (BTNode*)malloc(sizeof(BTNode));
8 c5 }, s5 T% @[color=rgba(0, 0, 0, 0.749019607843137)]        assert(n6);
2 L8 V: y& j! ]/ L& T8 f% h[color=rgba(0, 0, 0, 0.749019607843137)]
0 B1 X% h6 Q: ]* |5 q- n" X+ Q" N6 ]7 C2 S, B6 c
[color=rgba(0, 0, 0, 0.749019607843137)]        n1->data = 1;) \' @$ D! `0 T
[color=rgba(0, 0, 0, 0.749019607843137)]        n2->data = 2;# e$ a* O) ?6 |
[color=rgba(0, 0, 0, 0.749019607843137)]        n3->data = 3;& [+ ^6 Q* j$ e. p3 h6 Q3 n" f
[color=rgba(0, 0, 0, 0.749019607843137)]        n4->data = 4;
4 U2 H; a  R1 v[color=rgba(0, 0, 0, 0.749019607843137)]        n5->data = 5;- z- P( k  _; t8 e) k! i
[color=rgba(0, 0, 0, 0.749019607843137)]        n6->data = 6;2 D$ L" L: J" y, `" B! N
[color=rgba(0, 0, 0, 0.749019607843137)]& p. h( r2 G( ?& x% |) d7 m* n
4 s# e- p0 U" o" v7 k6 r/ X- l
[color=rgba(0, 0, 0, 0.749019607843137)]        n1->left = n2;# Z+ C1 V. O! \6 A7 M! i; q0 a8 z
[color=rgba(0, 0, 0, 0.749019607843137)]        n1->right = n4;
; M! y. E' V5 D6 _! S' I7 F[color=rgba(0, 0, 0, 0.749019607843137)]        n2->left = n3;5 h- Z7 b& F( _' w: k
[color=rgba(0, 0, 0, 0.749019607843137)]        n2->right = NULL;
1 w, E) L- x: R' U$ F9 ^[color=rgba(0, 0, 0, 0.749019607843137)]        n3->left = NULL;0 d7 Z- E) z) H9 S- J; p+ @* H
[color=rgba(0, 0, 0, 0.749019607843137)]        n3->right = NULL;  k6 N( v3 `- A" O% _0 h# V
[color=rgba(0, 0, 0, 0.749019607843137)]        n4->left = n5;: S: j8 j) a* Q% X. o
[color=rgba(0, 0, 0, 0.749019607843137)]        n4->right = n6;8 [+ w# y7 |( G
[color=rgba(0, 0, 0, 0.749019607843137)]        n5->left = NULL;7 r! B0 i" {+ R* I# _' ?
[color=rgba(0, 0, 0, 0.749019607843137)]        n5->right = NULL;! s0 C0 y$ S" ~) O. A
[color=rgba(0, 0, 0, 0.749019607843137)]        n6->left = NULL;
/ [. |% ^( v9 [& S[color=rgba(0, 0, 0, 0.749019607843137)]        n6->right = NULL;; J+ d7 V: w+ o$ R
[color=rgba(0, 0, 0, 0.749019607843137)]
" X$ {: ?+ t. V7 E2 |* H* D& q( P! S* C; F
[color=rgba(0, 0, 0, 0.749019607843137)]        return n1;
0 g. J7 c, p* j2 l8 T6 ?; O- |; h[color=rgba(0, 0, 0, 0.749019607843137)]}, l, r" z( w/ q3 I7 s. u3 g
[color=rgba(0, 0, 0, 0.749019607843137)]* |0 v5 |3 o3 M
3 v% l" h  P+ g# k+ D+ T0 l
[color=rgba(0, 0, 0, 0.749019607843137)]int main()7 p. p4 X0 g9 W
[color=rgba(0, 0, 0, 0.749019607843137)]{- S' W$ a. t% N$ C
[color=rgba(0, 0, 0, 0.749019607843137)]        //先创建一个简单的二叉树结构
# E, U; o3 V6 E  t[color=rgba(0, 0, 0, 0.749019607843137)]        BTNode* root = CreateTree();
8 }' P% N6 p( j* J& \- ^, D, }[color=rgba(0, 0, 0, 0.749019607843137)], l% U6 y* l& _+ v. i+ s
/ C  K; \7 _" l8 K- P
[color=rgba(0, 0, 0, 0.749019607843137)]        //二叉树前序遍历/ d" T! E; M# {" M. E
[color=rgba(0, 0, 0, 0.749019607843137)]        printf("二叉树前序遍历:");3 B0 [& b& U  O/ u
[color=rgba(0, 0, 0, 0.749019607843137)]        PreOrder(root);7 P9 n2 ~+ u, b& |/ l, n5 L8 p
[color=rgba(0, 0, 0, 0.749019607843137)]        printf("\n");
5 J# o' ^, x+ T' o[color=rgba(0, 0, 0, 0.749019607843137)]        //二叉树中序遍历: i; ]! I9 g1 Q. a0 [# y& F  C
[color=rgba(0, 0, 0, 0.749019607843137)]        printf("二叉树中序序遍历:");. F  ^$ \0 Z2 o: p# n( x
[color=rgba(0, 0, 0, 0.749019607843137)]        InOrder(root);( H8 L  w4 n6 G) t. u7 Y
[color=rgba(0, 0, 0, 0.749019607843137)]        printf("\n");6 f" Y+ H1 |( Z/ Z# c' t6 I
[color=rgba(0, 0, 0, 0.749019607843137)]        //二叉树后序遍历- ^2 H0 i6 e1 D' t
[color=rgba(0, 0, 0, 0.749019607843137)]        printf("二叉树后序遍历:");
  p  K) ^% q2 O" G  b# ^: i[color=rgba(0, 0, 0, 0.749019607843137)]        PostOrder(root);
" p& }$ g. U! j1 y[color=rgba(0, 0, 0, 0.749019607843137)]        printf("\n");' n$ i4 M: w9 P9 n8 w
[color=rgba(0, 0, 0, 0.749019607843137)]
, |; A. p) w4 [
7 A* c# ]9 k8 ?; k0 e[color=rgba(0, 0, 0, 0.749019607843137)]        return 0;5 L3 j* d$ {; }" X
[color=rgba(0, 0, 0, 0.749019607843137)]}( U; F$ P8 B& {/ ^8 }; e% T4 F
[color=rgba(0, 0, 0, 0.749019607843137)]18 M2 X( d1 m' z$ `
[color=rgba(0, 0, 0, 0.749019607843137)]2
5 F- S) n5 I3 F' H6 o6 X( y+ h[color=rgba(0, 0, 0, 0.749019607843137)]3
# s, N# B7 V4 N[color=rgba(0, 0, 0, 0.749019607843137)]43 n# }. ^0 K- B
[color=rgba(0, 0, 0, 0.749019607843137)]5
" M& Q( B. T5 d& |% G# \% Z[color=rgba(0, 0, 0, 0.749019607843137)]6
7 Z" P8 z2 J8 e[color=rgba(0, 0, 0, 0.749019607843137)]7  X+ e% p; x4 W& T& B( y
[color=rgba(0, 0, 0, 0.749019607843137)]8
, u4 U: G- O1 `1 u3 g[color=rgba(0, 0, 0, 0.749019607843137)]9* [" ^9 F, a8 k) ^$ l
[color=rgba(0, 0, 0, 0.749019607843137)]104 T" g6 l4 T5 u) C. H! Y
[color=rgba(0, 0, 0, 0.749019607843137)]11
; {& Q4 u& B* O' ~% }[color=rgba(0, 0, 0, 0.749019607843137)]12
7 r& b/ F( b& P/ T6 H8 H6 d$ V[color=rgba(0, 0, 0, 0.749019607843137)]13
. {4 e$ o* W$ J& R[color=rgba(0, 0, 0, 0.749019607843137)]14
' g5 ], P* F7 C5 G0 `; _: \[color=rgba(0, 0, 0, 0.749019607843137)]15
4 G. L# J. G  y- S[color=rgba(0, 0, 0, 0.749019607843137)]16* v1 {0 S  N& A) |
[color=rgba(0, 0, 0, 0.749019607843137)]17
6 C0 A! K- j4 u/ _' @! X+ ?" }4 D[color=rgba(0, 0, 0, 0.749019607843137)]18
! o4 K+ k! @1 p- M  a[color=rgba(0, 0, 0, 0.749019607843137)]19" i  F( Z3 Q4 ?. g: T, J
[color=rgba(0, 0, 0, 0.749019607843137)]20
* _7 Z- I  R6 D0 X- o[color=rgba(0, 0, 0, 0.749019607843137)]219 L/ \+ h; K. P$ k5 K& H
[color=rgba(0, 0, 0, 0.749019607843137)]22. [8 m5 J5 B/ F; R
[color=rgba(0, 0, 0, 0.749019607843137)]23* Y, @5 C2 c$ O9 I5 s% D  {8 S
[color=rgba(0, 0, 0, 0.749019607843137)]24
5 b- E3 r: e- r4 z$ I' u[color=rgba(0, 0, 0, 0.749019607843137)]254 B8 E( D* P2 H2 t; M# W7 C: b
[color=rgba(0, 0, 0, 0.749019607843137)]26
1 }9 z5 B( ?3 ~0 C5 D( R8 a: M[color=rgba(0, 0, 0, 0.749019607843137)]27
  l& J0 ~$ z" Z, ^2 ?, H$ h' s[color=rgba(0, 0, 0, 0.749019607843137)]28
9 q/ R  S0 X% p' E. v[color=rgba(0, 0, 0, 0.749019607843137)]29
1 e+ e  }: I8 A+ x: r" b, }[color=rgba(0, 0, 0, 0.749019607843137)]30
' ^. W+ J, |1 o' }+ |[color=rgba(0, 0, 0, 0.749019607843137)]31
) j& S& g- Z( j1 D[color=rgba(0, 0, 0, 0.749019607843137)]32; B2 K( d  ]3 M7 n* E
[color=rgba(0, 0, 0, 0.749019607843137)]33
! Y( ^4 I3 d: x, `0 p; D9 C[color=rgba(0, 0, 0, 0.749019607843137)]34( L, D+ e/ r4 [, `9 f
[color=rgba(0, 0, 0, 0.749019607843137)]353 B8 r' X( g: H: H) i
[color=rgba(0, 0, 0, 0.749019607843137)]364 f$ P3 m, R4 W, n- F& _3 h
[color=rgba(0, 0, 0, 0.749019607843137)]37+ ^  F0 b* ?7 J
[color=rgba(0, 0, 0, 0.749019607843137)]38) Z# s( [& s' \, ~
[color=rgba(0, 0, 0, 0.749019607843137)]39
( \& E; _5 c. v[color=rgba(0, 0, 0, 0.749019607843137)]40) q$ ^: }7 q8 d7 g8 S1 \9 n
[color=rgba(0, 0, 0, 0.749019607843137)]41
9 Q5 b8 E( W) n( J9 B[color=rgba(0, 0, 0, 0.749019607843137)]42
! _: l6 o( N$ q& `* B1 T: C3 [4 [7 \[color=rgba(0, 0, 0, 0.749019607843137)]43, C+ [9 o  `7 l4 d/ o" X1 C
[color=rgba(0, 0, 0, 0.749019607843137)]44
% \) ?3 o: |+ W2 Q( N. {[color=rgba(0, 0, 0, 0.749019607843137)]45
! \! S! O% U7 B8 r4 M[color=rgba(0, 0, 0, 0.749019607843137)]46. y$ m  e2 Q" @. {' g/ Y1 a
[color=rgba(0, 0, 0, 0.749019607843137)]47
2 ?% m9 D7 l. X0 J[color=rgba(0, 0, 0, 0.749019607843137)]48
( G4 h: c& j0 `" y1 K[color=rgba(0, 0, 0, 0.749019607843137)]498 {$ a7 S# O& [( f0 C
[color=rgba(0, 0, 0, 0.749019607843137)]50' l* E0 k3 [$ _4 j  N( p
[color=rgba(0, 0, 0, 0.749019607843137)]51
5 b8 ?$ b4 E2 x0 K[color=rgba(0, 0, 0, 0.749019607843137)]52  y/ D7 f3 a+ m
[color=rgba(0, 0, 0, 0.749019607843137)]53
8 @8 g4 K' Y! Y$ [[color=rgba(0, 0, 0, 0.749019607843137)]545 g/ `9 t8 |' U1 B' z5 W
[color=rgba(0, 0, 0, 0.749019607843137)]558 x' Q: i! Y& F% p4 [) Q$ @
[color=rgba(0, 0, 0, 0.749019607843137)]565 c% Z  ?3 v# J, U4 `" D& R
[color=rgba(0, 0, 0, 0.749019607843137)]572 `! I9 K( h# x; B: @( O: T
[color=rgba(0, 0, 0, 0.749019607843137)]58- ?8 j# h, ?$ h, a, L9 v
[color=rgba(0, 0, 0, 0.749019607843137)]59
8 b5 K) g* l+ j9 f6 O: {; ^0 n[color=rgba(0, 0, 0, 0.749019607843137)]60
5 t" W/ w0 w$ f1 x5 Y[color=rgba(0, 0, 0, 0.749019607843137)]610 c) u$ w1 p  {4 h, R$ ?8 Z* F8 U3 A
[color=rgba(0, 0, 0, 0.749019607843137)]62
) x" F( k3 H6 ~7 o# K3 j% g[color=rgba(0, 0, 0, 0.749019607843137)]63% j' q6 O# p0 Z2 B
[color=rgba(0, 0, 0, 0.749019607843137)]64; a4 r, T7 h" y: Y: l* ~- n
[color=rgba(0, 0, 0, 0.749019607843137)]65" {/ C2 B+ O) m5 G, s. n
[color=rgba(0, 0, 0, 0.749019607843137)]66# P! I! P8 G: q' }# G9 t
[color=rgba(0, 0, 0, 0.749019607843137)]67  h3 m. c- m  R, ]/ n, H7 S! e+ V; @
[color=rgba(0, 0, 0, 0.749019607843137)]68
% _" m# W  J6 Q3 L8 U[color=rgba(0, 0, 0, 0.749019607843137)]69
0 g4 K5 y! i2 V( E5 c# C[color=rgba(0, 0, 0, 0.749019607843137)]70/ M. h5 W8 R; ~, P- }, n
[color=rgba(0, 0, 0, 0.749019607843137)]715 H* r, X# p/ [+ Z6 b& ~+ |. F
[color=rgba(0, 0, 0, 0.749019607843137)]72
( F# B" {, Q  W. k1 O[color=rgba(0, 0, 0, 0.749019607843137)]73; Q  P: _# g, l
[color=rgba(0, 0, 0, 0.749019607843137)]74
5 b6 [$ A& o$ D( \) G9 W1 ~' T[color=rgba(0, 0, 0, 0.749019607843137)]75
: P# y8 s. L2 f" T; b* a[color=rgba(0, 0, 0, 0.749019607843137)]76
. Y2 y: b7 C& X, h9 {# Z+ z[color=rgba(0, 0, 0, 0.749019607843137)]773 \" J0 ^& [8 [  C) i4 x
[color=rgba(0, 0, 0, 0.749019607843137)]78
* L2 J6 m7 n& I5 I1 P[color=rgba(0, 0, 0, 0.749019607843137)]79
/ z8 D) I; o; w5 E' L: G[color=rgba(0, 0, 0, 0.749019607843137)]80
. N  j3 }, ?; ~  X8 G; C4 {! x[color=rgba(0, 0, 0, 0.749019607843137)]81
! l5 u5 {  y4 C7 L[color=rgba(0, 0, 0, 0.749019607843137)]828 V% I' w0 g/ h7 r
[color=rgba(0, 0, 0, 0.749019607843137)]83
) r. M/ V  S4 Z/ T/ H3 N) G[color=rgba(0, 0, 0, 0.749019607843137)]84
& e, I" R3 t; k& S" L! n. w[color=rgba(0, 0, 0, 0.749019607843137)]85
4 s& Y. v- C, t/ d7 K: |% t[color=rgba(0, 0, 0, 0.749019607843137)]86
* k, P5 m3 ?6 b0 y3 u( Z[color=rgba(0, 0, 0, 0.749019607843137)]87
5 R7 a* R# E, b# R[color=rgba(0, 0, 0, 0.749019607843137)]884 H( d9 F# y  x3 F$ E, s7 }0 s
[color=rgba(0, 0, 0, 0.749019607843137)]89
# H: N6 W0 s5 _6 u  }2 z3 y2 t! L[color=rgba(0, 0, 0, 0.749019607843137)]90# d/ o0 K( ~$ n7 }
[color=rgba(0, 0, 0, 0.749019607843137)]91
0 l7 _7 D9 Q; c- x0 e[color=rgba(0, 0, 0, 0.749019607843137)]92- f0 L' @, \: f8 R2 H6 x0 e+ [
[color=rgba(0, 0, 0, 0.749019607843137)]93
! M8 u, i9 V" @7 `7 L6 r0 k$ ][color=rgba(0, 0, 0, 0.749019607843137)]94) q2 }# l  g: w4 L2 }
[color=rgba(0, 0, 0, 0.749019607843137)]95" |0 v0 X" p# q
[color=rgba(0, 0, 0, 0.749019607843137)]96# g9 T% v& F  \3 t( j% M0 P! E) s& U7 K
[color=rgba(0, 0, 0, 0.749019607843137)]979 {+ T4 P+ b" c
[color=rgba(0, 0, 0, 0.749019607843137)]98
7 t# B' ^2 _# s$ a[color=rgba(0, 0, 0, 0.749019607843137)]99! f1 C2 M8 G; _# S) G0 c! {9 v7 A
[color=rgba(0, 0, 0, 0.749019607843137)]100
$ {2 R3 V% y1 p7 e: e[color=rgba(0, 0, 0, 0.749019607843137)]1011 l+ x+ H/ [1 k6 J0 I9 n
[color=rgba(0, 0, 0, 0.749019607843137)]102
6 h* W% g1 A& _+ k$ \4 a[color=rgba(0, 0, 0, 0.749019607843137)]103
: n4 _/ D, `( p[color=rgba(0, 0, 0, 0.749019607843137)]104* c: T# w% g1 p
[color=rgba(0, 0, 0, 0.749019607843137)]105% u/ w1 C4 _2 W3 M/ @
[color=rgba(0, 0, 0, 0.749019607843137)]1064 j8 Y7 _+ l; ~
[color=rgba(0, 0, 0, 0.749019607843137)]107; k+ u, p* z# A) X7 V1 v( O
[color=rgba(0, 0, 0, 0.749019607843137)]108( C% n/ a! N: a8 [, w$ w
[color=rgba(0, 0, 0, 0.749019607843137)]109
8 C$ l/ t3 c' s( S& t( m  `3 L[color=rgba(0, 0, 0, 0.749019607843137)]110
& c2 \1 w' ~1 f3 h0 J[color=rgba(0, 0, 0, 0.749019607843137)]111
$ g& n# d( c0 V6 ?9 F[color=rgba(0, 0, 0, 0.749019607843137)]测试结果：
" J/ d# a7 B, k" c! N, }1 M8 C[color=rgba(0, 0, 0, 0.749019607843137)]: M2 e6 M2 |0 O2 T/ b8 ~, X9 g( f
8 u" q$ R% p- Q
[color=rgba(0, 0, 0, 0.749019607843137)]
# L3 s* S6 O2 e+ Y" C2 f) W
8 w6 B' V. H! P4 b[color=rgba(0, 0, 0, 0.749019607843137)]2.2计算二叉树的大小
5 C6 x' g. n5 n. ][color=rgba(0, 0, 0, 0.749019607843137)]时间复杂度为O(N)
6 f. `3 Y. \$ v8 _7 i- |[color=rgba(0, 0, 0, 0.749019607843137)]" F- }- P" u1 p! L' C: B) ?( k! U
; Q  ?- q  H% ~3 f# O
[color=rgba(0, 0, 0, 0.749019607843137)]//二叉树的大小
# Z  V: f" _+ b# ]: ^% e* G[color=rgba(0, 0, 0, 0.749019607843137)]//法一：全局变量
. ]# U% q/ @0 k+ o; D[color=rgba(0, 0, 0, 0.749019607843137)]//int count = 0;
; Z( c. d$ t7 k& B4 m6 J[color=rgba(0, 0, 0, 0.749019607843137)]//void TreeSize(BTNode* root)
+ r! e* D9 A+ C8 e% I7 W' |) O: Z4 r; j[color=rgba(0, 0, 0, 0.749019607843137)]//{; f2 W4 L/ B3 s! l, x2 k& f
[color=rgba(0, 0, 0, 0.749019607843137)]//        if (root == NULL)# l" _- N9 E" Q
[color=rgba(0, 0, 0, 0.749019607843137)]//        {, L( V5 L) d( W4 a" ^
[color=rgba(0, 0, 0, 0.749019607843137)]//                return;
) k* X/ Z6 U3 N, Q2 Q& t0 x[color=rgba(0, 0, 0, 0.749019607843137)]//        }: {5 E( o: a; a+ n) F% K
[color=rgba(0, 0, 0, 0.749019607843137)]//        count++;
1 e2 O6 @, ~6 o. e0 _: U[color=rgba(0, 0, 0, 0.749019607843137)]//        TreeSize(root->left);
. C1 r1 R) m3 s. Q( s[color=rgba(0, 0, 0, 0.749019607843137)]//        TreeSize(root->right);# R% ^1 u7 Y; ]# c* ^, l* t
[color=rgba(0, 0, 0, 0.749019607843137)]//( B) a; c2 O7 w& M: F$ T, p
[color=rgba(0, 0, 0, 0.749019607843137)]//        return;//函数栈帧层层返回，最后回到根节点1，结束了1的右子树函数，什么都不返回，因为count是全局变量9 a. r/ X3 `, O  n8 l) {* W
[color=rgba(0, 0, 0, 0.749019607843137)]//}
0 v" p; l( [0 U[color=rgba(0, 0, 0, 0.749019607843137)]//法二：子问题思路：分而治之
2 k& _' V7 g# B9 }5 W( _[color=rgba(0, 0, 0, 0.749019607843137)]int TreeSize(BTNode* root)
- d% ^! J# J5 x5 H, q; |; W[color=rgba(0, 0, 0, 0.749019607843137)]{
) t1 \* f1 {0 \' @[color=rgba(0, 0, 0, 0.749019607843137)]        return root == NULL ? 0 : TreeSize(root->left) + TreeSize(root->right) + 1;
) @. S6 c7 P! V0 L3 E[color=rgba(0, 0, 0, 0.749019607843137)]}- Y" h9 P2 M! E1 ^& ]* i& E
[color=rgba(0, 0, 0, 0.749019607843137)]1
9 S* B5 ?" U! p  _[color=rgba(0, 0, 0, 0.749019607843137)]2
' l7 I! Z0 E; ]: x- Q! e[color=rgba(0, 0, 0, 0.749019607843137)]31 @9 ]# ]  H0 N
[color=rgba(0, 0, 0, 0.749019607843137)]4
2 M( q0 i$ |6 @) C6 u% q+ u( g' ~[color=rgba(0, 0, 0, 0.749019607843137)]5
% x8 W7 \1 }2 ~( Z6 y- F3 h- }[color=rgba(0, 0, 0, 0.749019607843137)]6; Z, c9 M) K: p9 J$ y
[color=rgba(0, 0, 0, 0.749019607843137)]73 E' K9 c+ ~8 F6 [
[color=rgba(0, 0, 0, 0.749019607843137)]8
2 q! j2 t8 h- a- z[color=rgba(0, 0, 0, 0.749019607843137)]9
. ~9 U5 @+ k2 u! Z7 @; `[color=rgba(0, 0, 0, 0.749019607843137)]10
, m/ @8 D; i) Y) D[color=rgba(0, 0, 0, 0.749019607843137)]11
7 e( Y( x4 E+ q% y' y, l. @[color=rgba(0, 0, 0, 0.749019607843137)]12# u% p2 R! g  j; d
[color=rgba(0, 0, 0, 0.749019607843137)]13
' Z( p; Y# P) J. a; x[color=rgba(0, 0, 0, 0.749019607843137)]14
" t, X. f: a2 X+ k' N[color=rgba(0, 0, 0, 0.749019607843137)]152 r$ @" B2 }! W9 z9 A( t, X* [
[color=rgba(0, 0, 0, 0.749019607843137)]16) \1 j( x0 ~% f6 c2 o7 r3 |) N, R
[color=rgba(0, 0, 0, 0.749019607843137)]171 i: r2 a; s. w% W/ ^- S$ v
[color=rgba(0, 0, 0, 0.749019607843137)]181 _$ G( g: q. G+ r- e2 C1 s- {
[color=rgba(0, 0, 0, 0.749019607843137)]19
# K5 P: j5 N2 L: U5 h9 }[color=rgba(0, 0, 0, 0.749019607843137)]20
- G! u2 F4 o& z5 m- J/ ~* n! q[color=rgba(0, 0, 0, 0.749019607843137)]2.3计算二叉树叶子结点的个数" Q: m! P8 N( n4 A( Z! T
[color=rgba(0, 0, 0, 0.749019607843137)]//计算二叉树叶子结点的个数
3 W: X4 J" ?% c# |[color=rgba(0, 0, 0, 0.749019607843137)]int TreeLeafSize(BTNode* root)0 g0 l1 ~- k, X8 m' P
[color=rgba(0, 0, 0, 0.749019607843137)]{
0 J' `4 d: u2 J+ B[color=rgba(0, 0, 0, 0.749019607843137)]        if (root == NULL)//首先得考虑空树的情况,0个叶子结点
& t, _( O  }' s' B[color=rgba(0, 0, 0, 0.749019607843137)]        {7 e) U- s4 M# ], I" ~
[color=rgba(0, 0, 0, 0.749019607843137)]                return 0;4 @" G, U, w! Q' u
[color=rgba(0, 0, 0, 0.749019607843137)]        }5 I- H$ l6 r* l: M" _+ R
[color=rgba(0, 0, 0, 0.749019607843137)]        //叶子结点的特征就是左右子树为空
4 c+ ]9 F" i) G  U[color=rgba(0, 0, 0, 0.749019607843137)]        if (root->left == NULL && root->right == NULL)& h3 a3 C; n  X1 C
[color=rgba(0, 0, 0, 0.749019607843137)]        {$ j: @+ f$ t" P4 ~
[color=rgba(0, 0, 0, 0.749019607843137)]                return 1;
" q6 R3 |: \6 }. s! u1 i8 K[color=rgba(0, 0, 0, 0.749019607843137)]        }6 A" c6 m% M2 j8 k
[color=rgba(0, 0, 0, 0.749019607843137)]        return TreeLeafSize(root->left) + TreeLeafSize(root->right);
: J' d+ l+ @0 C' r$ z[color=rgba(0, 0, 0, 0.749019607843137)]}
$ F4 q) q. y% _) b: K; X[color=rgba(0, 0, 0, 0.749019607843137)]12 k8 s* K, C) T
[color=rgba(0, 0, 0, 0.749019607843137)]2
% R" h% ]6 q+ {9 {5 b/ g[color=rgba(0, 0, 0, 0.749019607843137)]3
8 A1 k) ~5 k0 F# `7 C' w# t/ N[color=rgba(0, 0, 0, 0.749019607843137)]4
! I! v' c' r6 Y[color=rgba(0, 0, 0, 0.749019607843137)]5
! T* M, |) `. _[color=rgba(0, 0, 0, 0.749019607843137)]6" n) z4 O- S# o2 S% j1 o
[color=rgba(0, 0, 0, 0.749019607843137)]7
3 |* }0 C, m& R[color=rgba(0, 0, 0, 0.749019607843137)]8
' e5 ?5 n# Z6 }% E0 A# X[color=rgba(0, 0, 0, 0.749019607843137)]9; N8 i; T7 e+ I# e8 p: b  J/ H
[color=rgba(0, 0, 0, 0.749019607843137)]10
# |9 Q/ d8 Z6 T9 Q' X' q[color=rgba(0, 0, 0, 0.749019607843137)]11
* W* w* s$ V$ m[color=rgba(0, 0, 0, 0.749019607843137)]12
2 Q9 C& U& \/ y+ e[color=rgba(0, 0, 0, 0.749019607843137)]13/ I) {& x/ n- Z# h
[color=rgba(0, 0, 0, 0.749019607843137)]14' j9 k, v0 V# |9 c9 ~
[color=rgba(0, 0, 0, 0.749019607843137)]2.4计算二叉树的高度8 m9 F* Y% o, t/ Y$ ]0 H, V# g+ Y
[color=rgba(0, 0, 0, 0.749019607843137)]int TreeHeight(BTNode* root)
% x/ ?6 b/ q, |2 B& u, b. b% f[color=rgba(0, 0, 0, 0.749019607843137)]{( t0 v" F- ~' u- J
[color=rgba(0, 0, 0, 0.749019607843137)]        //空树高度为0
' J- b7 V' r# K2 n% W[color=rgba(0, 0, 0, 0.749019607843137)]        if (root == NULL)' Q/ I. j/ T/ U& u
[color=rgba(0, 0, 0, 0.749019607843137)]        {
) \1 X1 V7 |5 _( a7 ~$ {[color=rgba(0, 0, 0, 0.749019607843137)]                return 0;
% N8 A+ x. ^- e% [7 t[color=rgba(0, 0, 0, 0.749019607843137)]        }
8 Y3 R3 ]4 ?5 b, m[color=rgba(0, 0, 0, 0.749019607843137)]        //树的高度是较高的那棵子树
+ {6 V: \% ?& e' B1 J2 M$ d1 y6 M/ n[color=rgba(0, 0, 0, 0.749019607843137)]        int lh = TreeHeight(root->left);//左子树的高度
. s- x$ S7 G$ X3 k[color=rgba(0, 0, 0, 0.749019607843137)]        int rh = TreeHeight(root->right);//右子树的高度( b7 `- d' U. g- w# X$ b; w$ u
[color=rgba(0, 0, 0, 0.749019607843137)]0 D; s8 X7 c7 r; B, ~9 ~) E+ a

& Y  U: b3 ]' z! n/ L7 Z  W[color=rgba(0, 0, 0, 0.749019607843137)]        return lh > rh ? lh + 1 : rh + 1;2 A' F# i' S. m0 M! |
[color=rgba(0, 0, 0, 0.749019607843137)]}
" x; M( x" y5 k3 J% t4 `3 {# e* N[color=rgba(0, 0, 0, 0.749019607843137)]1  s0 i/ V6 R6 J$ F/ Z# s7 K
[color=rgba(0, 0, 0, 0.749019607843137)]2
2 e6 }+ R3 e+ P& M[color=rgba(0, 0, 0, 0.749019607843137)]3
) P  N* ]4 \5 |5 |, z$ Y, b7 F[color=rgba(0, 0, 0, 0.749019607843137)]4. k" o, t1 n9 s3 F; g" V/ h- K
[color=rgba(0, 0, 0, 0.749019607843137)]5
% z4 t( D7 W) _, \+ v! B[color=rgba(0, 0, 0, 0.749019607843137)]6' J- b2 _: q' A' n0 e
[color=rgba(0, 0, 0, 0.749019607843137)]7
$ S& y% q" y5 }[color=rgba(0, 0, 0, 0.749019607843137)]8& T% `' i$ F1 V; `) U
[color=rgba(0, 0, 0, 0.749019607843137)]9
# S$ u2 W. h$ d8 g2 y5 U( {! E[color=rgba(0, 0, 0, 0.749019607843137)]107 A0 O# y2 n. Y
[color=rgba(0, 0, 0, 0.749019607843137)]117 c, F3 \3 U7 R% y( R0 f
[color=rgba(0, 0, 0, 0.749019607843137)]12
* C! k% H) @5 _[color=rgba(0, 0, 0, 0.749019607843137)]13* g1 _6 y+ t- g/ @" l% I
[color=rgba(0, 0, 0, 0.749019607843137)]2.5计算第K层结点的个数
* m7 B" I) u- R6 T[color=rgba(0, 0, 0, 0.749019607843137)], s' t4 C* K6 d+ r% l, H2 x% {
+ r) C3 s4 X/ a
[color=rgba(0, 0, 0, 0.749019607843137)]
, f$ R8 z% \) [/ |( |# Y+ j. c+ o  c0 T; A
[color=rgba(0, 0, 0, 0.749019607843137)]求第K层的结点个数，转换成求子树第K-1层的结点个数。举个栗子：如果我们要求这棵二叉树第3层的结点个数（为3），就转换成求左子树根结点2的第2层的结点个数+右子树4第二层的结点个数。。。4 W5 ]2 g# {, c. l- i
[color=rgba(0, 0, 0, 0.749019607843137)]
4 Q/ O' X; F0 ~  D1 L6 c7 L. h" W8 \: q- o4 L9 P! L# |
[color=rgba(0, 0, 0, 0.749019607843137)]//计算第K层结点的个数
, U/ W, M* J' M" q* o, F3 f, k* X[color=rgba(0, 0, 0, 0.749019607843137)]int TreeLevel(BTNode* root,int K)& s$ r6 l" ^* G: H5 T1 [! ]9 z4 U
[color=rgba(0, 0, 0, 0.749019607843137)]{
3 X! @$ u- j$ a; J[color=rgba(0, 0, 0, 0.749019607843137)]        assert(K > 0);
: c2 o& w7 R6 D, p[color=rgba(0, 0, 0, 0.749019607843137)]        if (root == NULL)
. T2 d8 `1 l9 f3 `( }+ {[color=rgba(0, 0, 0, 0.749019607843137)]        {
; `' y. R3 u1 l+ _, P8 P/ N[color=rgba(0, 0, 0, 0.749019607843137)]                return 0;
0 J3 {- z7 }& A& t' w[color=rgba(0, 0, 0, 0.749019607843137)]        }0 i- L0 V0 Q! O0 l
[color=rgba(0, 0, 0, 0.749019607843137)]        //如果是第一层(递归出口)# T; r9 c8 s7 c/ n+ R
[color=rgba(0, 0, 0, 0.749019607843137)]        if (K == 1)
  L  }! l% y3 y% |0 P[color=rgba(0, 0, 0, 0.749019607843137)]        {
. B5 o3 z& f- p% X% F[color=rgba(0, 0, 0, 0.749019607843137)]                return 1;
3 w; e$ W5 F% \  e  r[color=rgba(0, 0, 0, 0.749019607843137)]        }
# F8 B) ^2 u$ g[color=rgba(0, 0, 0, 0.749019607843137)]        //转换成子树的第K-1层
2 X% H' M: c( y[color=rgba(0, 0, 0, 0.749019607843137)]        return TreeLevel(root->left,K-1) + TreeLevel(root->right,K-1);
8 E! l% I7 j+ {8 S8 B[color=rgba(0, 0, 0, 0.749019607843137)]}
7 [- w; c$ t# _) ~& G$ y[color=rgba(0, 0, 0, 0.749019607843137)]1
# _8 r( C9 k" e& }5 m9 R[color=rgba(0, 0, 0, 0.749019607843137)]2
9 I1 m2 }- b0 y5 Z; j8 N2 o# w[color=rgba(0, 0, 0, 0.749019607843137)]32 b# L  J7 m( a* A, C
[color=rgba(0, 0, 0, 0.749019607843137)]4: @7 G! f" [7 o* f# l
[color=rgba(0, 0, 0, 0.749019607843137)]5; d' R" H) p% U/ S# L
[color=rgba(0, 0, 0, 0.749019607843137)]66 P2 }& S$ D8 k& |# R$ s# S) ?
[color=rgba(0, 0, 0, 0.749019607843137)]77 _- a8 d* C) x# g/ L/ H
[color=rgba(0, 0, 0, 0.749019607843137)]85 |" n. A& z/ D1 h1 ]/ b
[color=rgba(0, 0, 0, 0.749019607843137)]9: Q" E- O' p/ ?7 U1 {( X; A" ~. Q
[color=rgba(0, 0, 0, 0.749019607843137)]104 P* ~2 W$ K8 e
[color=rgba(0, 0, 0, 0.749019607843137)]115 C% J- d" T- f' o8 F* @
[color=rgba(0, 0, 0, 0.749019607843137)]12
0 X1 ]6 s: E' {[color=rgba(0, 0, 0, 0.749019607843137)]13$ A$ z6 b! ]9 X; v
[color=rgba(0, 0, 0, 0.749019607843137)]14. ^! K/ \* z% N+ z
[color=rgba(0, 0, 0, 0.749019607843137)]15
, T/ ^' t8 S  S3 }5 w! }[color=rgba(0, 0, 0, 0.749019607843137)]166 D$ P# o# N- e$ n# b& }
[color=rgba(0, 0, 0, 0.749019607843137)]2.6二叉树查找
% k) \9 y) q9 h; O' N  v4 C[color=rgba(0, 0, 0, 0.749019607843137)]//二叉树查找
8 o7 j- V# g" \% x[color=rgba(0, 0, 0, 0.749019607843137)]BTNode* TreeFind(BTNode* root, BTDataType data)5 k$ s3 {# x1 |) ]$ d
[color=rgba(0, 0, 0, 0.749019607843137)]{. N) b0 x; h4 W: {3 O* k/ Q( R
[color=rgba(0, 0, 0, 0.749019607843137)]        if (root == NULL)
% S8 w- O# N0 U8 r) [- e/ P( A[color=rgba(0, 0, 0, 0.749019607843137)]        {; W4 ^4 W" W7 v
[color=rgba(0, 0, 0, 0.749019607843137)]                return NULL;2 h, v; L0 F5 |0 F! J0 X
[color=rgba(0, 0, 0, 0.749019607843137)]        }9 j* |* j7 j2 e7 z! k8 ]$ a, z, c8 I
[color=rgba(0, 0, 0, 0.749019607843137)]        if (root->data == data)$ _" d# h7 |9 F! [1 x9 ?4 p
[color=rgba(0, 0, 0, 0.749019607843137)]        {
! L( V8 x, M! u+ d" Y& ~/ s[color=rgba(0, 0, 0, 0.749019607843137)]                return root;2 [. L$ c; H  z7 R4 E0 C; x
[color=rgba(0, 0, 0, 0.749019607843137)]        }: s3 d; \  Q- t  Z- o
[color=rgba(0, 0, 0, 0.749019607843137)]        //先查找左子树! X$ `* ]8 K5 _% Y
[color=rgba(0, 0, 0, 0.749019607843137)]        BTNode* lret = TreeFind(root->left, data);2 k4 c. s, o; |1 O7 d- K
[color=rgba(0, 0, 0, 0.749019607843137)]        if (lret)$ b1 M" I+ M  k* U- ^4 [3 t, G
[color=rgba(0, 0, 0, 0.749019607843137)]                return lret;
$ H3 b; R: t  ^1 B0 T) U' r[color=rgba(0, 0, 0, 0.749019607843137)]        //再查找右子树
% w1 `; I5 p) q3 n3 e[color=rgba(0, 0, 0, 0.749019607843137)]        BTNode* rret = TreeFind(root->right, data);
- |. ~6 T* ]! T. Q[color=rgba(0, 0, 0, 0.749019607843137)]        if (rret)
% T7 g7 z% k: |' X0 w[color=rgba(0, 0, 0, 0.749019607843137)]                return rret;$ D7 M3 R6 C5 K
[color=rgba(0, 0, 0, 0.749019607843137)]        return NULL;+ y$ ?) ?6 N! I  o! p; |
[color=rgba(0, 0, 0, 0.749019607843137)]}
( q& l) j4 C7 b$ g! U& D6 k  ][color=rgba(0, 0, 0, 0.749019607843137)]————————————————
3 C' a2 F* z& `2 r5 a2 R[color=rgba(0, 0, 0, 0.749019607843137)]版权声明：本文为CSDN博主「SouLinya」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。4 U" m7 o  I3 J5 \
[color=rgba(0, 0, 0, 0.749019607843137)]原文链接：https://blog.csdn.net/weixin_63449996/article/details/126841212
1 n5 ~6 ]# U$ }' [0 h
3 A5 `8 k- [" |$ u8 _: B9 D. Y" z# Y) i: @2 A# @$ b6 r3 H
[color=rgba(0, 0, 0, 0.75)]
4 b( q( v; I; N* u; i" `# t$ n* \  E' S- C: L3 T
, |- h7 j( A: s  [( M$ r. y
0 j- V& k5 l$ k1 K# y" I




欢迎光临 数学建模社区-数学中国 (http://www.madio.net/) Powered by Discuz! X2.5