数学建模社区-数学中国

标题: 【数据结构】二叉树的遍历：前序，中序，后序的递归结构遍历 [打印本页]
作者: 杨利霞    时间: 2022-9-15 11:55
标题: 【数据结构】二叉树的遍历：前序，中序，后序的递归结构遍历
【数据结构】二叉树的遍历：前序，中序，后序的递归结构遍历6 J9 v6 f4 P+ t6 z
7 \+ U( B+ A5 x' s7 i* S$ S
[color=rgba(0, 0, 0, 0.749019607843137)]文章目录
, E' h$ S$ f% E: M[color=rgba(0, 0, 0, 0.749019607843137)]前言7 u4 X$ L" `8 A1 J# g
[color=rgba(0, 0, 0, 0.749019607843137)]1.二叉树的遍历方式, K; d  Y6 T0 y: M/ j( f
[color=rgba(0, 0, 0, 0.749019607843137)]2.二叉树的遍历及相关函数（代码实现）9 N2 j$ o1 C; O
[color=rgba(0, 0, 0, 0.749019607843137)]2.1前序/中序/后序的遍历/ w; y+ M. p& j( W% b& }
[color=rgba(0, 0, 0, 0.749019607843137)]2.2计算二叉树的大小1 c" O0 c3 x8 y. H! V
[color=rgba(0, 0, 0, 0.749019607843137)]2.3计算二叉树叶子结点的个数4 q. o# @% U/ r( [8 j/ J
[color=rgba(0, 0, 0, 0.749019607843137)]2.4计算二叉树的高度$ W6 s. ]) e- _) Q  d
[color=rgba(0, 0, 0, 0.749019607843137)]2.5计算第K层结点的个数! t! h. ?- y8 W5 P( u
[color=rgba(0, 0, 0, 0.749019607843137)]2.6二叉树查找
% K5 ?: ?, R3 M; \[color=rgba(0, 0, 0, 0.749019607843137)]前言7 D; S3 q, }+ K& D, Z. _- v7 x
[color=rgba(0, 0, 0, 0.749019607843137)]在学习二叉树的遍历之前，我们需要先创建一棵二叉树，然后才能学习其相关的基本操作，由于现在我们对二叉树结构的掌握还在初阶部分，为了降低大家的学习成本，我们先手动快速创建一棵简单的二叉树，快速进入二叉树的操作学习，这个方法在我们调试程序代码的时候，也非常适用。等二叉树结构了解的差不多时，我们再继续研究二叉树真正的创建方式。
; T5 o0 U( l% _/ G5 M: O[color=rgba(0, 0, 0, 0.749019607843137)]
& K& Y7 A. v4 r  `( g% [3 g3 r$ p/ V
[color=rgba(0, 0, 0, 0.749019607843137)]1.二叉树的遍历方式
' E: k% O4 d! r3 w$ M[color=rgba(0, 0, 0, 0.749019607843137)]
1 m' e, [0 U" g' |. X- a2 P  ]6 F/ I  o* c: A3 t# P" R
[color=rgba(0, 0, 0, 0.749019607843137)]按照规则，二叉树的遍历有：前序/中序/后序的递归结构遍历访问顺序：( b5 P1 |5 C3 o
[color=rgba(0, 0, 0, 0.749019607843137)]( M7 {% \" X' I$ b

* I. s/ |! X  n( `* E' m[color=rgba(0, 0, 0, 0.749019607843137)]1. 前序遍历（先序，先根):根——左子树——右子树
$ g0 s4 U9 R9 Y- t[color=rgba(0, 0, 0, 0.749019607843137)]" U. f& f$ l! N' M! u2 q. N
" i1 A8 A- M5 g" G
[color=rgba(0, 0, 0, 0.749019607843137)]
3 |% G. p5 q$ _* M& L( R
: V" ?7 s: i, H[color=rgba(0, 0, 0, 0.749019607843137)]2. 中序遍历（中根）：左子树——根——右子树
* L+ S/ v6 h2 l; r# C( ]3 W[color=rgba(0, 0, 0, 0.749019607843137)]
' u; ^; ]7 o# d- a' E& F
2 _: g+ z3 ^' B, n" V/ J  H  B[color=rgba(0, 0, 0, 0.749019607843137)]/ K5 L2 `( L- o& d9 J1 R

* W( n; t$ o, Z[color=rgba(0, 0, 0, 0.749019607843137)]3. 后序遍历（后根）：左子树——右子树——根
7 ]. ]8 l+ q# T[color=rgba(0, 0, 0, 0.749019607843137)]
% e- B$ B& _4 m2 S" {4 e' w: D4 P2 b
" w  ]/ v- R( b- e" _2 S# i[color=rgba(0, 0, 0, 0.749019607843137)]
' ^, n7 }) x0 V- T: g0 _
* B& j& m& [& \) J. T4 J: R[color=rgba(0, 0, 0, 0.749019607843137)]2.二叉树的遍历及相关函数（代码实现）5 i% W4 m9 r2 S
[color=rgba(0, 0, 0, 0.749019607843137)]思路：分而治之! ~" N( D. R" U$ o
[color=rgba(0, 0, 0, 0.749019607843137)]1.首先我们要用简单的方式先创建出一棵二叉树，并赋予数据；
' @  ?5 E  W. t1 T4 C" V[color=rgba(0, 0, 0, 0.749019607843137)]2.采用递归的方式，分别实现前序/中序/后序遍历这棵二叉树；
0 {6 l8 A4 ^( d' O% d" u2 W4 U[color=rgba(0, 0, 0, 0.749019607843137)]3.尝试计算这个二叉树的大小（利用递归）；; T( S% r% A( X# F. e9 ~8 K
[color=rgba(0, 0, 0, 0.749019607843137)]4.尝试计算叶子结点的个数（利用递归）；, w  t& c, G, j/ e
[color=rgba(0, 0, 0, 0.749019607843137)]5.尝试计算二叉树的高度（利用递归）；
" [( F0 u0 P% D9 J  Y% n' z4 v[color=rgba(0, 0, 0, 0.749019607843137)]6.尝试写出计算第K层结点的个数的函数（利用递归）；8 w7 `! u+ @# G) |5 Z
[color=rgba(0, 0, 0, 0.749019607843137)]7.尝试写出二叉树查找的函数（利用递归）。
, j! }# A* m( F: c[color=rgba(0, 0, 0, 0.749019607843137)]4 Y) G5 d4 m& T" H; q. o5 R

- X& n5 ]; o( R7 c4 @: H; y% ?! |( B[color=rgba(0, 0, 0, 0.749019607843137)]2.1前序/中序/后序的遍历8 I  t8 Z% Y! _4 E: ]3 F
[color=rgba(0, 0, 0, 0.749019607843137)]#define _CRT_SECURE_NO_WARNINGS 1) Y* N% v- @4 |% V7 S& u
[color=rgba(0, 0, 0, 0.749019607843137)]#include<stdio.h>
& s& ~7 b! k4 c% d) w6 m[color=rgba(0, 0, 0, 0.749019607843137)]#include<assert.h>
8 G/ I9 [# Y5 z1 N5 ^( R* w5 U[color=rgba(0, 0, 0, 0.749019607843137)]#include<stdlib.h>
# @$ P5 ^' R9 C- ]3 I[color=rgba(0, 0, 0, 0.749019607843137)]' H! |* q" d7 z7 I5 o( O6 x
: {/ B& _, }2 ?: {
[color=rgba(0, 0, 0, 0.749019607843137)]typedef int BTDataType;
" x& b, h: q7 f! y) w# i$ Y( e[color=rgba(0, 0, 0, 0.749019607843137)]; X' Y3 I2 s% G5 ~
1 [- g2 n" o4 @( T% q; z
[color=rgba(0, 0, 0, 0.749019607843137)]//定义二叉树结点的结构体
/ d* x/ n0 H+ Q4 G' }4 A, ]; f[color=rgba(0, 0, 0, 0.749019607843137)]typedef struct BinaryTreeNode; A/ S) n' j+ B
[color=rgba(0, 0, 0, 0.749019607843137)]{( O% R# J5 g6 |- F
[color=rgba(0, 0, 0, 0.749019607843137)]        BTDataType data;
/ C/ U$ t- @8 K. B; h4 m[color=rgba(0, 0, 0, 0.749019607843137)]        struct BinaryTreeNode* left;5 S8 J! ~2 N& ^- V
[color=rgba(0, 0, 0, 0.749019607843137)]        struct BinaryTreeNode* right;
5 K! B% B& j* ]3 z' k, S[color=rgba(0, 0, 0, 0.749019607843137)]}BTNode;  z+ V2 r. X2 y- p
[color=rgba(0, 0, 0, 0.749019607843137)]4 I. G+ t% a* x! K# }

2 i: @' I* H, I2 b3 J& u$ g4 U2 `[color=rgba(0, 0, 0, 0.749019607843137)]//前序遍历
7 p8 |2 z  ?5 {0 j* M- v% f2 _[color=rgba(0, 0, 0, 0.749019607843137)]void PreOrder(BTNode* root)
3 ^0 l* Y4 z, ~8 n( z% g4 y[color=rgba(0, 0, 0, 0.749019607843137)]{
6 ?2 E5 L3 R0 ]6 ~* L8 D9 p; p[color=rgba(0, 0, 0, 0.749019607843137)]        if (root == NULL)4 M6 P( V" S* {! ?
[color=rgba(0, 0, 0, 0.749019607843137)]        {" T$ m3 n1 `! F1 W7 M% q
[color=rgba(0, 0, 0, 0.749019607843137)]                printf("NULL ");: G% v% t' b8 F. @
[color=rgba(0, 0, 0, 0.749019607843137)]                return;
5 t8 W2 z- h1 u) m8 T6 s! r  R[color=rgba(0, 0, 0, 0.749019607843137)]        }* f* m9 c# V( e7 a- I
[color=rgba(0, 0, 0, 0.749019607843137)]        printf("%d ", root->data);
, X9 D9 s' W, t) W- E- k[color=rgba(0, 0, 0, 0.749019607843137)]        PreOrder(root->left);
) G$ q4 y) C; \/ h[color=rgba(0, 0, 0, 0.749019607843137)]        PreOrder(root->right);  V- C& l2 n9 |5 h& S0 G
[color=rgba(0, 0, 0, 0.749019607843137)]}
( D% d2 d' {3 T, W8 @# d) @% j2 {[color=rgba(0, 0, 0, 0.749019607843137)]//中序遍历
' O" T) ]5 ^# x[color=rgba(0, 0, 0, 0.749019607843137)]void InOrder(BTNode* root)
6 y5 ~5 g2 U% B[color=rgba(0, 0, 0, 0.749019607843137)]{3 A4 B; Z+ H% E* j" A" f" \
[color=rgba(0, 0, 0, 0.749019607843137)]        if (root == NULL)
6 j; [5 R: A) o) h, ?+ @4 r8 p2 e[color=rgba(0, 0, 0, 0.749019607843137)]        {; _* ]: i2 Q; }% f) h+ K
[color=rgba(0, 0, 0, 0.749019607843137)]                printf("NULL ");; C# v5 l7 n7 X7 T, r* Q1 r# Y
[color=rgba(0, 0, 0, 0.749019607843137)]                return;
: P0 l9 \+ x0 u4 |. e9 ?[color=rgba(0, 0, 0, 0.749019607843137)]        }* N" ?! i* Q% c  I
[color=rgba(0, 0, 0, 0.749019607843137)]        InOrder(root->left);8 \1 m9 ~* l- j% k9 j" U$ ~
[color=rgba(0, 0, 0, 0.749019607843137)]        printf("%d ", root->data);
( T8 R8 S1 p, b/ y9 d( W- x. u[color=rgba(0, 0, 0, 0.749019607843137)]        InOrder(root->right);! n6 V# ~/ X" D8 w! F5 V
[color=rgba(0, 0, 0, 0.749019607843137)]}- _7 i, N1 p. \+ s
[color=rgba(0, 0, 0, 0.749019607843137)]//后序遍历
/ k7 ]7 Y% `( c8 N: r& c[color=rgba(0, 0, 0, 0.749019607843137)]void PostOrder(BTNode* root)7 J1 [: r& S$ e9 s' C; i" _4 U
[color=rgba(0, 0, 0, 0.749019607843137)]{, z8 \% c* [1 |* b) E
[color=rgba(0, 0, 0, 0.749019607843137)]        if (root == NULL)
! T0 x  G7 V, W% Y" }+ D[color=rgba(0, 0, 0, 0.749019607843137)]        {, }3 ?( e# y, {3 {
[color=rgba(0, 0, 0, 0.749019607843137)]                printf("NULL ");
7 d& k! o( v6 ?3 P) l+ X" X[color=rgba(0, 0, 0, 0.749019607843137)]                return;+ j1 X: k4 B# s+ a8 O! h) i
[color=rgba(0, 0, 0, 0.749019607843137)]        }
7 z* z; U) }6 p/ n& W( T3 m( K8 f[color=rgba(0, 0, 0, 0.749019607843137)]        PostOrder(root->left);& ~0 f, z( ]- g. I9 L
[color=rgba(0, 0, 0, 0.749019607843137)]        PostOrder(root->right);
& S7 @4 d3 O$ x7 t" q[color=rgba(0, 0, 0, 0.749019607843137)]        printf("%d ", root->data);
$ G! z4 S0 Y9 V1 D% {0 \+ o4 d[color=rgba(0, 0, 0, 0.749019607843137)]}6 g! I9 _, \' B
[color=rgba(0, 0, 0, 0.749019607843137)]//先创建一个简单的二叉树结构
& z6 q& d' y6 l" l) @[color=rgba(0, 0, 0, 0.749019607843137)]BTNode* CreateTree()+ s$ F9 H3 ~( d& q: Y3 F' W" V
[color=rgba(0, 0, 0, 0.749019607843137)]{
4 [5 g$ v' Y0 l4 o+ d! {- T; y[color=rgba(0, 0, 0, 0.749019607843137)]        //先动态开辟6个结点的空间8 v4 x! T/ e0 B/ u  }0 J& j
[color=rgba(0, 0, 0, 0.749019607843137)]        BTNode* n1 = (BTNode*)malloc(sizeof(BTNode));* m6 H9 z" \+ G5 l2 v: C
[color=rgba(0, 0, 0, 0.749019607843137)]        assert(n1);
2 f- I# A- G; s6 Z5 I* r[color=rgba(0, 0, 0, 0.749019607843137)]        BTNode* n2 = (BTNode*)malloc(sizeof(BTNode));1 u; J6 n( a, R; B7 A- ~5 V& b
[color=rgba(0, 0, 0, 0.749019607843137)]        assert(n2);
8 H& V( o/ R' O1 |' k' Q* p[color=rgba(0, 0, 0, 0.749019607843137)]        BTNode* n3 = (BTNode*)malloc(sizeof(BTNode));
2 k0 b) v1 K# j; ]' C; G7 [1 h/ |[color=rgba(0, 0, 0, 0.749019607843137)]        assert(n3);0 k" Z, Y2 x* J" w* e
[color=rgba(0, 0, 0, 0.749019607843137)]        BTNode* n4 = (BTNode*)malloc(sizeof(BTNode));
: X- N+ O: ~' x: {/ m$ U8 ]& Q[color=rgba(0, 0, 0, 0.749019607843137)]        assert(n4);- w- s, Q( W, J! F3 I0 V
[color=rgba(0, 0, 0, 0.749019607843137)]        BTNode* n5 = (BTNode*)malloc(sizeof(BTNode));
/ Z( u. _: [1 E9 O5 j) ^[color=rgba(0, 0, 0, 0.749019607843137)]        assert(n5);
% c5 m/ h. D' I! f' y8 z9 n8 W- \. Z[color=rgba(0, 0, 0, 0.749019607843137)]        BTNode* n6 = (BTNode*)malloc(sizeof(BTNode));- L% U+ R& |* [. s: D- D' \
[color=rgba(0, 0, 0, 0.749019607843137)]        assert(n6);# k% o' P1 z6 P& g8 s( C
[color=rgba(0, 0, 0, 0.749019607843137)]0 c6 r5 z! I" e$ @8 {5 L

5 L0 A& f; b: r! q2 n6 b  N9 k[color=rgba(0, 0, 0, 0.749019607843137)]        n1->data = 1;* z% c7 R+ ~! X0 o: W3 v8 W0 k
[color=rgba(0, 0, 0, 0.749019607843137)]        n2->data = 2;' b1 Q+ ^+ m- d
[color=rgba(0, 0, 0, 0.749019607843137)]        n3->data = 3;2 {+ D0 b6 t5 ^' C
[color=rgba(0, 0, 0, 0.749019607843137)]        n4->data = 4;
0 [: `" O) x. N9 g/ f[color=rgba(0, 0, 0, 0.749019607843137)]        n5->data = 5;
3 a% H; o  g: h+ R/ t4 x[color=rgba(0, 0, 0, 0.749019607843137)]        n6->data = 6;9 N6 P9 H9 D. G% V6 t; R
[color=rgba(0, 0, 0, 0.749019607843137)]
7 `4 b7 E* v0 r+ e! b1 }5 Z
+ G" G1 ?" a& ~  ?: {6 P[color=rgba(0, 0, 0, 0.749019607843137)]        n1->left = n2;
' ]2 i2 }& O; w! H4 o! o3 j[color=rgba(0, 0, 0, 0.749019607843137)]        n1->right = n4;% d5 `/ d% G- Z$ ~
[color=rgba(0, 0, 0, 0.749019607843137)]        n2->left = n3;
8 a* G1 B# b& X& m( M[color=rgba(0, 0, 0, 0.749019607843137)]        n2->right = NULL;9 Q3 I# z0 e( u5 U' H. q
[color=rgba(0, 0, 0, 0.749019607843137)]        n3->left = NULL;
# _0 W/ ^, I% H) T[color=rgba(0, 0, 0, 0.749019607843137)]        n3->right = NULL;
( U& q2 f( ?/ R2 G; G[color=rgba(0, 0, 0, 0.749019607843137)]        n4->left = n5;, ^$ c2 P* R: h& g$ u3 ^
[color=rgba(0, 0, 0, 0.749019607843137)]        n4->right = n6;
4 i3 R% F. Q) l; j: U8 I[color=rgba(0, 0, 0, 0.749019607843137)]        n5->left = NULL;4 Y' U6 e5 J+ H& G! F4 i3 j! V
[color=rgba(0, 0, 0, 0.749019607843137)]        n5->right = NULL;
; H* B; K" C' o3 v# t( N) x[color=rgba(0, 0, 0, 0.749019607843137)]        n6->left = NULL;# c5 b! l, |3 h4 s
[color=rgba(0, 0, 0, 0.749019607843137)]        n6->right = NULL;
7 a7 Z0 ]6 [2 K- \1 y[color=rgba(0, 0, 0, 0.749019607843137)]
- U( l1 h& i3 f8 P# X
  B( a( i$ q+ a: \, I5 \[color=rgba(0, 0, 0, 0.749019607843137)]        return n1;5 [, w5 A6 o6 \0 O- l5 N$ |9 f, ?
[color=rgba(0, 0, 0, 0.749019607843137)]}8 [" c, |- W  B
[color=rgba(0, 0, 0, 0.749019607843137)]
- ~+ Y+ w/ {! e7 Z' \- q! c5 E" l
[color=rgba(0, 0, 0, 0.749019607843137)]int main()3 e- [' t# t: O; j2 {7 y  n
[color=rgba(0, 0, 0, 0.749019607843137)]{3 i. ^- I2 @( Y3 D9 {& c7 g, y
[color=rgba(0, 0, 0, 0.749019607843137)]        //先创建一个简单的二叉树结构6 T  _2 J, [) g7 F+ G
[color=rgba(0, 0, 0, 0.749019607843137)]        BTNode* root = CreateTree();
' `! r) m: U$ v  Y" w* `( h6 P$ d[color=rgba(0, 0, 0, 0.749019607843137)]
; A0 G. L  I, l4 Z+ d, Q% t- P9 N- _1 v3 c
[color=rgba(0, 0, 0, 0.749019607843137)]        //二叉树前序遍历  a+ i  |- a1 [/ E' w3 }  `: a
[color=rgba(0, 0, 0, 0.749019607843137)]        printf("二叉树前序遍历:");! @) T( F% S8 j* g
[color=rgba(0, 0, 0, 0.749019607843137)]        PreOrder(root);
6 q" X. R# l- y9 R[color=rgba(0, 0, 0, 0.749019607843137)]        printf("\n");
8 {# T: h& e9 l[color=rgba(0, 0, 0, 0.749019607843137)]        //二叉树中序遍历
  x" V4 a2 |7 ~/ r& N/ O0 P[color=rgba(0, 0, 0, 0.749019607843137)]        printf("二叉树中序序遍历:");) V6 f- V5 X3 W5 K
[color=rgba(0, 0, 0, 0.749019607843137)]        InOrder(root);3 e/ X6 T: n$ Q
[color=rgba(0, 0, 0, 0.749019607843137)]        printf("\n");
) j2 z4 g9 [5 b! k9 E7 U[color=rgba(0, 0, 0, 0.749019607843137)]        //二叉树后序遍历
8 u3 [# }. h5 c: j' B+ A, X[color=rgba(0, 0, 0, 0.749019607843137)]        printf("二叉树后序遍历:");
$ [1 \1 t. r; e+ y7 _9 E$ C0 I7 p[color=rgba(0, 0, 0, 0.749019607843137)]        PostOrder(root);; I) s8 s" {+ X4 s
[color=rgba(0, 0, 0, 0.749019607843137)]        printf("\n");$ a4 l5 D- d& K. R
[color=rgba(0, 0, 0, 0.749019607843137)]
  y+ K; w7 g. z* ?7 }. d9 q5 |' N/ Y* `* _* Z
[color=rgba(0, 0, 0, 0.749019607843137)]        return 0;7 N+ v! N' `+ l! ]2 b
[color=rgba(0, 0, 0, 0.749019607843137)]}
+ k3 u6 D. s, A- [; [[color=rgba(0, 0, 0, 0.749019607843137)]1; O% l/ f! E" f- Z  w
[color=rgba(0, 0, 0, 0.749019607843137)]2
, P8 `8 t& N8 _  f. M0 M) B" d[color=rgba(0, 0, 0, 0.749019607843137)]3
& J# Z- l/ L+ S+ [& N[color=rgba(0, 0, 0, 0.749019607843137)]4
& k, m; O% L( q5 O; n, X[color=rgba(0, 0, 0, 0.749019607843137)]5/ E9 f0 f) E$ F& i, _
[color=rgba(0, 0, 0, 0.749019607843137)]6
* B  N/ B: r* x1 x[color=rgba(0, 0, 0, 0.749019607843137)]7( a& k" \6 R$ r# l: Y# a, ?- F
[color=rgba(0, 0, 0, 0.749019607843137)]8
5 e2 [/ `3 N, L5 t: c[color=rgba(0, 0, 0, 0.749019607843137)]9
5 s" m( U2 M* e[color=rgba(0, 0, 0, 0.749019607843137)]108 t  `7 Z7 ]# j1 I8 I2 X
[color=rgba(0, 0, 0, 0.749019607843137)]11
; E7 b0 a# ?/ s% D( v2 ^( y[color=rgba(0, 0, 0, 0.749019607843137)]12
) m/ X- n# x* K' g7 ~[color=rgba(0, 0, 0, 0.749019607843137)]13( d# s% A# o: ^# o
[color=rgba(0, 0, 0, 0.749019607843137)]14
& e( O4 M5 N1 Q& n3 A[color=rgba(0, 0, 0, 0.749019607843137)]15
# o9 d" H) C- x! \7 i( B* H[color=rgba(0, 0, 0, 0.749019607843137)]16% ?' ?; @: \4 q8 W! `
[color=rgba(0, 0, 0, 0.749019607843137)]17! y1 E: j* A. \) H+ E0 }; i* e; w. ?
[color=rgba(0, 0, 0, 0.749019607843137)]18
. E4 E) V( }! s[color=rgba(0, 0, 0, 0.749019607843137)]19/ X4 ?$ v' D8 B$ M; n
[color=rgba(0, 0, 0, 0.749019607843137)]20& d% E3 N# ^  D. ]
[color=rgba(0, 0, 0, 0.749019607843137)]212 C6 \, E- A' W0 {+ }- D7 N
[color=rgba(0, 0, 0, 0.749019607843137)]22
7 O+ H0 Z# w$ X& N; `( b8 n6 r9 K' n- {% b[color=rgba(0, 0, 0, 0.749019607843137)]23, |, G2 s7 v2 U
[color=rgba(0, 0, 0, 0.749019607843137)]24
1 H' \# a3 k% m+ b4 H$ `+ s1 k" r[color=rgba(0, 0, 0, 0.749019607843137)]25+ F" j7 H- a4 E2 X9 ], H
[color=rgba(0, 0, 0, 0.749019607843137)]26
; X. F2 K- P+ i3 L% e[color=rgba(0, 0, 0, 0.749019607843137)]27
8 a; Z2 O- w5 n' z& s" V7 X" l[color=rgba(0, 0, 0, 0.749019607843137)]28
/ Z% y5 z6 r: s$ s! |[color=rgba(0, 0, 0, 0.749019607843137)]295 l, w. b* q: o# M/ q8 X& t* O
[color=rgba(0, 0, 0, 0.749019607843137)]301 L; Q5 y2 k7 Q/ _( ~% {
[color=rgba(0, 0, 0, 0.749019607843137)]31
$ q, Q- z8 `; z' l; t6 h2 T- m[color=rgba(0, 0, 0, 0.749019607843137)]322 ?; f- a. e, B) d
[color=rgba(0, 0, 0, 0.749019607843137)]338 W4 z* f! Z' o+ ?( n% s# Y$ z8 A
[color=rgba(0, 0, 0, 0.749019607843137)]343 h% Y/ I$ z) j; Z1 y* h" V! l: T& t" m
[color=rgba(0, 0, 0, 0.749019607843137)]35
4 \# r6 L3 ~1 J# l* V9 C[color=rgba(0, 0, 0, 0.749019607843137)]36- `# y4 h% h; i, h# M, f
[color=rgba(0, 0, 0, 0.749019607843137)]37/ w" f, l; b% y: {' h- _
[color=rgba(0, 0, 0, 0.749019607843137)]38
* f: u  Q# W6 p[color=rgba(0, 0, 0, 0.749019607843137)]39
/ v6 C& G+ c! M! K, t/ K2 D: Z' C9 `[color=rgba(0, 0, 0, 0.749019607843137)]40; k1 }' P8 s& A
[color=rgba(0, 0, 0, 0.749019607843137)]41
8 m$ ]4 w+ L/ A) _. O[color=rgba(0, 0, 0, 0.749019607843137)]42' r# B3 G+ x! u
[color=rgba(0, 0, 0, 0.749019607843137)]43* F  ]. Z+ @) @1 Y: I* d! Z7 N
[color=rgba(0, 0, 0, 0.749019607843137)]44/ Q+ ^" j& u% o4 S/ C$ S; ?
[color=rgba(0, 0, 0, 0.749019607843137)]45
: g3 k9 D* ^" ?5 Z% l* z5 [% `' @" C[color=rgba(0, 0, 0, 0.749019607843137)]46
9 k, y, |. n+ W' n7 \[color=rgba(0, 0, 0, 0.749019607843137)]47
1 z* b8 J4 ?6 @+ l1 Q; h) Q5 |8 \& y% [[color=rgba(0, 0, 0, 0.749019607843137)]480 S% T, ]  o, Z. K
[color=rgba(0, 0, 0, 0.749019607843137)]49
1 ~& M  O# E: P1 h  E[color=rgba(0, 0, 0, 0.749019607843137)]50
/ j& x  Z! \* }- p  W[color=rgba(0, 0, 0, 0.749019607843137)]51
) v$ Q' ?3 f4 s) V) E, y[color=rgba(0, 0, 0, 0.749019607843137)]525 d' Q, f  N# J( v* w7 F0 J6 o# h
[color=rgba(0, 0, 0, 0.749019607843137)]53
& W/ R. u/ k$ ]5 f" P[color=rgba(0, 0, 0, 0.749019607843137)]54
8 r" `0 y4 l/ A4 [; t[color=rgba(0, 0, 0, 0.749019607843137)]55( ?: L! ?; M) e, p' Z4 y
[color=rgba(0, 0, 0, 0.749019607843137)]56
* O* @  G; s/ _+ h& H5 F6 n: K# w[color=rgba(0, 0, 0, 0.749019607843137)]57. G$ u. M6 ^9 d' I& a1 ^5 m$ G' D. O
[color=rgba(0, 0, 0, 0.749019607843137)]58% O6 `6 m' R# C; n+ I% T8 C
[color=rgba(0, 0, 0, 0.749019607843137)]591 }4 R1 ^9 O9 j0 `
[color=rgba(0, 0, 0, 0.749019607843137)]608 S" I$ f4 W; M% h
[color=rgba(0, 0, 0, 0.749019607843137)]61
8 P# h9 f: F& Y+ r& M6 Y5 n8 |: O[color=rgba(0, 0, 0, 0.749019607843137)]62
! s6 G, [9 l/ i+ y' o0 I[color=rgba(0, 0, 0, 0.749019607843137)]63, n$ Z+ E, C) Y$ ^! s
[color=rgba(0, 0, 0, 0.749019607843137)]64- t$ U& v/ i6 I% F# a, O4 Z
[color=rgba(0, 0, 0, 0.749019607843137)]65
3 [1 l6 b, @- Y6 S: ^- A, M' Q[color=rgba(0, 0, 0, 0.749019607843137)]66
. t! P0 X3 \% i+ f/ p' o[color=rgba(0, 0, 0, 0.749019607843137)]67- b0 {/ U6 c5 s) e, z  c
[color=rgba(0, 0, 0, 0.749019607843137)]68
! I4 G  k# ^" ^& g3 m, a[color=rgba(0, 0, 0, 0.749019607843137)]69
  P3 `( h$ F8 L2 d) `/ m: A[color=rgba(0, 0, 0, 0.749019607843137)]701 N$ T! {, V; |1 j+ N  C
[color=rgba(0, 0, 0, 0.749019607843137)]719 j4 o" C8 t( W' O7 f  T
[color=rgba(0, 0, 0, 0.749019607843137)]72+ Y! f' f! U' K. f+ ?
[color=rgba(0, 0, 0, 0.749019607843137)]73
  x4 V8 Q2 R2 t/ J. s! m[color=rgba(0, 0, 0, 0.749019607843137)]74+ j4 J1 ~: c. C* r7 s1 W# u
[color=rgba(0, 0, 0, 0.749019607843137)]75
* W( \2 j/ n- z9 R" H0 K[color=rgba(0, 0, 0, 0.749019607843137)]76
. I# [9 M9 f" o' P' n7 `[color=rgba(0, 0, 0, 0.749019607843137)]774 G0 E; R: q3 I0 [
[color=rgba(0, 0, 0, 0.749019607843137)]786 I/ ~& B1 U) R' Z3 a
[color=rgba(0, 0, 0, 0.749019607843137)]79
& ~' _8 ]. H" A3 B: J* `[color=rgba(0, 0, 0, 0.749019607843137)]80! m1 H8 @0 |; U0 y
[color=rgba(0, 0, 0, 0.749019607843137)]81
$ m. @0 `7 c5 y$ O5 z& F3 o. M+ y[color=rgba(0, 0, 0, 0.749019607843137)]825 v* A5 w' R0 C
[color=rgba(0, 0, 0, 0.749019607843137)]837 Q+ y7 k7 W+ L- n
[color=rgba(0, 0, 0, 0.749019607843137)]84' y/ v' \+ ]  r1 R5 i2 n
[color=rgba(0, 0, 0, 0.749019607843137)]85
$ b2 a, }  q1 @: A! |. m$ x[color=rgba(0, 0, 0, 0.749019607843137)]86
9 ?. @" _( \/ G[color=rgba(0, 0, 0, 0.749019607843137)]87
% E7 E- x0 x: O% j- C' _[color=rgba(0, 0, 0, 0.749019607843137)]88
) x8 _2 D# |+ Z4 f$ I[color=rgba(0, 0, 0, 0.749019607843137)]897 n/ B0 |; e# C/ l  ~5 T
[color=rgba(0, 0, 0, 0.749019607843137)]90
" g  o% Z  C5 `3 r' G" P# p[color=rgba(0, 0, 0, 0.749019607843137)]91
7 e3 @2 l3 V) s' \% ]+ w2 b[color=rgba(0, 0, 0, 0.749019607843137)]92
8 o% I: b( w6 ^[color=rgba(0, 0, 0, 0.749019607843137)]93+ W0 }  c: S+ e3 N* S  r6 n
[color=rgba(0, 0, 0, 0.749019607843137)]94  s9 l- C* K5 t' H$ Q' d6 x5 W
[color=rgba(0, 0, 0, 0.749019607843137)]95" m4 o1 ]! A( `( s
[color=rgba(0, 0, 0, 0.749019607843137)]96" z$ [. X3 L2 _
[color=rgba(0, 0, 0, 0.749019607843137)]97
. n& L5 X5 h1 I& p+ w0 s% w8 G[color=rgba(0, 0, 0, 0.749019607843137)]98
( ?5 X: @- n/ w% S) U2 h0 D4 ]1 C[color=rgba(0, 0, 0, 0.749019607843137)]996 A4 T) I' V* |+ S/ n4 ]
[color=rgba(0, 0, 0, 0.749019607843137)]100( F0 j# ?/ y* M  u. U. G0 H' t7 Z
[color=rgba(0, 0, 0, 0.749019607843137)]101' D9 S9 W" C% W4 \6 X
[color=rgba(0, 0, 0, 0.749019607843137)]102% S/ b3 D$ n% C% k
[color=rgba(0, 0, 0, 0.749019607843137)]1032 [* w; G7 t/ m) C+ y, i- e: f# z: S
[color=rgba(0, 0, 0, 0.749019607843137)]104
" ^1 Z4 l: p$ N. u5 ~, O[color=rgba(0, 0, 0, 0.749019607843137)]105
0 Z. a5 ~/ O7 k[color=rgba(0, 0, 0, 0.749019607843137)]106
' m- U6 C! E) N; j[color=rgba(0, 0, 0, 0.749019607843137)]107
. s  }6 R3 Y; U. \+ [7 O2 Z0 P: U[color=rgba(0, 0, 0, 0.749019607843137)]108
8 f+ W# f: z% H1 Q; ?3 z# _[color=rgba(0, 0, 0, 0.749019607843137)]109* ^7 T! j2 v8 m: A$ A4 M, x
[color=rgba(0, 0, 0, 0.749019607843137)]110
7 c# I; X+ L; f[color=rgba(0, 0, 0, 0.749019607843137)]111
3 L: S, k7 ]0 ]1 a# E/ n[color=rgba(0, 0, 0, 0.749019607843137)]测试结果：
3 l' Q$ X+ C1 d6 K[color=rgba(0, 0, 0, 0.749019607843137)]
- `! I( G8 x; ^' W& N4 G6 O& D* x- _  h) z
[color=rgba(0, 0, 0, 0.749019607843137)]
, A% H, W7 j) \7 S& ^$ k9 m: `' e, C& A1 |( v* }+ [  x
[color=rgba(0, 0, 0, 0.749019607843137)]2.2计算二叉树的大小& @* I/ n& r2 i6 Q& X
[color=rgba(0, 0, 0, 0.749019607843137)]时间复杂度为O(N)
! n! P+ I, S# ]6 T5 I$ ^6 U' n, K) _[color=rgba(0, 0, 0, 0.749019607843137)]/ I% i  n$ n- _% g( o( A; l

9 e6 r% P" h2 p$ I: c[color=rgba(0, 0, 0, 0.749019607843137)]//二叉树的大小/ o" K1 T0 k( f- O/ N
[color=rgba(0, 0, 0, 0.749019607843137)]//法一：全局变量) |0 i1 }8 n! H% w$ b
[color=rgba(0, 0, 0, 0.749019607843137)]//int count = 0;; _3 i$ W% h( z- `2 i) F) \
[color=rgba(0, 0, 0, 0.749019607843137)]//void TreeSize(BTNode* root)
3 Q! x; d- n2 ~5 ?" G% r[color=rgba(0, 0, 0, 0.749019607843137)]//{& R# b+ h$ t/ `' k+ ~7 X& k
[color=rgba(0, 0, 0, 0.749019607843137)]//        if (root == NULL)9 A: d3 b4 ^0 G, o  O
[color=rgba(0, 0, 0, 0.749019607843137)]//        {5 d$ |2 q9 F/ j- G
[color=rgba(0, 0, 0, 0.749019607843137)]//                return;5 {3 D) D; M  T; z7 {: h/ \8 p0 _' ]
[color=rgba(0, 0, 0, 0.749019607843137)]//        }: t/ }; L! a2 `- T
[color=rgba(0, 0, 0, 0.749019607843137)]//        count++;8 D" E$ O. W3 U
[color=rgba(0, 0, 0, 0.749019607843137)]//        TreeSize(root->left);
) X- D& V  k* a% G+ E7 r[color=rgba(0, 0, 0, 0.749019607843137)]//        TreeSize(root->right);+ u% z1 n- |# H& L* s
[color=rgba(0, 0, 0, 0.749019607843137)]//
' ?) n' Z  T8 Z: _7 O- Q% q# y) D[color=rgba(0, 0, 0, 0.749019607843137)]//        return;//函数栈帧层层返回，最后回到根节点1，结束了1的右子树函数，什么都不返回，因为count是全局变量  Y& ~' |" _$ _, g8 t0 M8 p
[color=rgba(0, 0, 0, 0.749019607843137)]//}! z) N( K0 m" n% V( f
[color=rgba(0, 0, 0, 0.749019607843137)]//法二：子问题思路：分而治之
: v3 B$ o+ I/ L[color=rgba(0, 0, 0, 0.749019607843137)]int TreeSize(BTNode* root)* m9 u6 V% b* x( P
[color=rgba(0, 0, 0, 0.749019607843137)]{
5 l( {# k; K+ s, f6 c[color=rgba(0, 0, 0, 0.749019607843137)]        return root == NULL ? 0 : TreeSize(root->left) + TreeSize(root->right) + 1;
$ h+ G# Y+ K- {1 S  I* y1 h; l[color=rgba(0, 0, 0, 0.749019607843137)]}! g. w- Y8 W+ _8 F$ ]; [- x+ @
[color=rgba(0, 0, 0, 0.749019607843137)]1, {' o# e5 |6 y; J0 V' ~0 X
[color=rgba(0, 0, 0, 0.749019607843137)]2, `8 h5 R: t* Z& Q% n
[color=rgba(0, 0, 0, 0.749019607843137)]3
/ W7 _2 Y% }" `, Y9 ~  L2 N: T[color=rgba(0, 0, 0, 0.749019607843137)]4" a7 U" c" B0 W
[color=rgba(0, 0, 0, 0.749019607843137)]5
/ E* N! n' Z  B1 a8 X( X5 J[color=rgba(0, 0, 0, 0.749019607843137)]6
% d7 K% e+ T2 i- i! K# U[color=rgba(0, 0, 0, 0.749019607843137)]7
. q* T- l: P( h: |- k& B2 Z[color=rgba(0, 0, 0, 0.749019607843137)]8
" i! m& e- c" _[color=rgba(0, 0, 0, 0.749019607843137)]96 I: D0 R9 \7 ^1 @
[color=rgba(0, 0, 0, 0.749019607843137)]100 v8 W6 _. l( B" T9 Z9 z. \" T& B
[color=rgba(0, 0, 0, 0.749019607843137)]11# l: Q9 Y% [2 Y& K! z3 }
[color=rgba(0, 0, 0, 0.749019607843137)]12# K6 z& o5 L) k- R
[color=rgba(0, 0, 0, 0.749019607843137)]13
; H" l$ B( a$ A6 @[color=rgba(0, 0, 0, 0.749019607843137)]14
4 p/ |6 p) d5 T[color=rgba(0, 0, 0, 0.749019607843137)]152 p7 v. h0 S2 m! C
[color=rgba(0, 0, 0, 0.749019607843137)]16
! ~. T! M% |& U/ Y$ R[color=rgba(0, 0, 0, 0.749019607843137)]17
) t/ f' J/ S) c; m7 t; u[color=rgba(0, 0, 0, 0.749019607843137)]18
* |# _# w6 z% k, |7 I[color=rgba(0, 0, 0, 0.749019607843137)]199 G0 }$ o  a. E& k$ z
[color=rgba(0, 0, 0, 0.749019607843137)]20
  G, U, O; x& V  S* g7 }[color=rgba(0, 0, 0, 0.749019607843137)]2.3计算二叉树叶子结点的个数
2 {/ ?$ o- y6 u! S+ K2 d[color=rgba(0, 0, 0, 0.749019607843137)]//计算二叉树叶子结点的个数# _0 z6 p8 H8 J
[color=rgba(0, 0, 0, 0.749019607843137)]int TreeLeafSize(BTNode* root)
! B3 f4 \% E: a; R[color=rgba(0, 0, 0, 0.749019607843137)]{' J6 k( m2 ]- C' Z  |
[color=rgba(0, 0, 0, 0.749019607843137)]        if (root == NULL)//首先得考虑空树的情况,0个叶子结点
& `# ^& y2 z+ P2 F[color=rgba(0, 0, 0, 0.749019607843137)]        {
! ?5 P6 U0 V6 {4 ?( q$ r[color=rgba(0, 0, 0, 0.749019607843137)]                return 0;
  |% D! R2 k9 `, t) a[color=rgba(0, 0, 0, 0.749019607843137)]        }
1 o( H9 U, w8 ~' J) S5 K% r. a/ I[color=rgba(0, 0, 0, 0.749019607843137)]        //叶子结点的特征就是左右子树为空. ^2 G$ e5 b9 N8 J- f8 U0 @
[color=rgba(0, 0, 0, 0.749019607843137)]        if (root->left == NULL && root->right == NULL)4 z  Z8 J1 w. @
[color=rgba(0, 0, 0, 0.749019607843137)]        {
& B5 x1 }& [8 ^% u; Q[color=rgba(0, 0, 0, 0.749019607843137)]                return 1;- ^; \' l& Y4 w3 z( P: w. \! G
[color=rgba(0, 0, 0, 0.749019607843137)]        }
" @2 Q, L+ ]0 d* q* Z4 x[color=rgba(0, 0, 0, 0.749019607843137)]        return TreeLeafSize(root->left) + TreeLeafSize(root->right);0 R) O4 W2 e/ R& A) H+ \
[color=rgba(0, 0, 0, 0.749019607843137)]}
6 X) q3 `+ b. g  I2 \4 J[color=rgba(0, 0, 0, 0.749019607843137)]1
4 T4 _2 D! A1 z" n" F[color=rgba(0, 0, 0, 0.749019607843137)]2  r: q* m8 A: ~/ Y$ _5 Y1 w) T
[color=rgba(0, 0, 0, 0.749019607843137)]3
" _& y. p* p1 I; W* }3 |[color=rgba(0, 0, 0, 0.749019607843137)]4
1 s" s5 {$ ?2 M/ L, H7 {+ t[color=rgba(0, 0, 0, 0.749019607843137)]52 n$ X. r! O% h  t1 b+ {3 X
[color=rgba(0, 0, 0, 0.749019607843137)]6
& t; v: i/ o( E: T/ ?[color=rgba(0, 0, 0, 0.749019607843137)]73 [1 a% j4 A! W7 _. Q& `
[color=rgba(0, 0, 0, 0.749019607843137)]8' c6 X6 h+ v& t/ ?2 y: q
[color=rgba(0, 0, 0, 0.749019607843137)]9
5 G8 K4 a, _( E0 ~4 {, V[color=rgba(0, 0, 0, 0.749019607843137)]10, n& p9 Y( x/ q
[color=rgba(0, 0, 0, 0.749019607843137)]11
( `5 K9 O' h) Z- y7 Q[color=rgba(0, 0, 0, 0.749019607843137)]12/ u7 L0 s6 S1 {$ f% g3 L9 I
[color=rgba(0, 0, 0, 0.749019607843137)]13
# O1 Q3 R: P5 F0 ~[color=rgba(0, 0, 0, 0.749019607843137)]14
+ F/ A( G2 |, R[color=rgba(0, 0, 0, 0.749019607843137)]2.4计算二叉树的高度
2 E& {' `8 t/ L5 M[color=rgba(0, 0, 0, 0.749019607843137)]int TreeHeight(BTNode* root)
2 K9 x& Y/ r+ O; B: G* D& W# L  h[color=rgba(0, 0, 0, 0.749019607843137)]{+ z  f! k8 X; A# S
[color=rgba(0, 0, 0, 0.749019607843137)]        //空树高度为0+ H/ |( @8 m2 W' n5 f/ ^( a
[color=rgba(0, 0, 0, 0.749019607843137)]        if (root == NULL)
* W) E  i4 Z# ~  p# P; n  w/ k" m[color=rgba(0, 0, 0, 0.749019607843137)]        {
* X* {: F- u( V5 D* h6 v# I3 }[color=rgba(0, 0, 0, 0.749019607843137)]                return 0;! D# `3 S+ x  a5 x/ c6 z5 p
[color=rgba(0, 0, 0, 0.749019607843137)]        }
+ w, s( o% B/ s' e+ X2 ^[color=rgba(0, 0, 0, 0.749019607843137)]        //树的高度是较高的那棵子树0 f, X& @- R$ a+ d/ F+ ~! k
[color=rgba(0, 0, 0, 0.749019607843137)]        int lh = TreeHeight(root->left);//左子树的高度! [/ K' f; c# V! r# }
[color=rgba(0, 0, 0, 0.749019607843137)]        int rh = TreeHeight(root->right);//右子树的高度
# v. q' y* m, J4 @[color=rgba(0, 0, 0, 0.749019607843137)]
' Y9 N8 X0 c, p  Q0 g+ z
0 Q6 o* l5 h% d/ l7 N9 {* J& R% `[color=rgba(0, 0, 0, 0.749019607843137)]        return lh > rh ? lh + 1 : rh + 1;  ?. `* X* n" m4 q, w
[color=rgba(0, 0, 0, 0.749019607843137)]}
" @  p, `; C: e5 U2 h( i[color=rgba(0, 0, 0, 0.749019607843137)]15 m3 \" ^: b7 o+ x! ?! p' \- @( L
[color=rgba(0, 0, 0, 0.749019607843137)]2
& G% M2 r, D. w/ d: A# f[color=rgba(0, 0, 0, 0.749019607843137)]3
" x# ~6 k$ q6 u4 y7 ^; o9 G5 V7 b[color=rgba(0, 0, 0, 0.749019607843137)]4
; r& N6 K$ f- P" J5 V" T$ O, f[color=rgba(0, 0, 0, 0.749019607843137)]5
- T$ }. u0 `' c* ~[color=rgba(0, 0, 0, 0.749019607843137)]67 K' j7 U2 }% o$ f3 {, E
[color=rgba(0, 0, 0, 0.749019607843137)]7  d6 g5 z% Y) y, F2 K! \- f
[color=rgba(0, 0, 0, 0.749019607843137)]8
* \# F  y  I0 J( Q- q& Y6 P+ w[color=rgba(0, 0, 0, 0.749019607843137)]9
7 M" P4 y, M2 t5 ][color=rgba(0, 0, 0, 0.749019607843137)]10
" M" I/ p# N/ Z; M- s! r6 f[color=rgba(0, 0, 0, 0.749019607843137)]11
! K+ b) Q* j! M' G- x: S; N$ l2 E[color=rgba(0, 0, 0, 0.749019607843137)]12
- s( h( ~0 u6 Q[color=rgba(0, 0, 0, 0.749019607843137)]13
; U& v6 n; N& T; i4 Y" i$ C[color=rgba(0, 0, 0, 0.749019607843137)]2.5计算第K层结点的个数
! X  u% h! O( a" Q5 g[color=rgba(0, 0, 0, 0.749019607843137)]
9 I5 t; |; J" U8 Z/ B
: y9 [2 f7 s/ D2 O[color=rgba(0, 0, 0, 0.749019607843137)]0 A! c8 ?% A- Q0 b5 t# w

+ q& X4 g. I! x0 |[color=rgba(0, 0, 0, 0.749019607843137)]求第K层的结点个数，转换成求子树第K-1层的结点个数。举个栗子：如果我们要求这棵二叉树第3层的结点个数（为3），就转换成求左子树根结点2的第2层的结点个数+右子树4第二层的结点个数。。。
" U4 T8 Y5 P* g, w/ H' d' G2 x[color=rgba(0, 0, 0, 0.749019607843137)]& T( S* C( r, a; v) `: Q

! e8 g! @2 ]" |# M; y/ {: B[color=rgba(0, 0, 0, 0.749019607843137)]//计算第K层结点的个数
$ Y( g& r" p- l: |$ {  v2 u# ]) }[color=rgba(0, 0, 0, 0.749019607843137)]int TreeLevel(BTNode* root,int K)
$ H% s( S! b% e* Z+ w9 a3 H; Y4 ^) C3 Z3 F[color=rgba(0, 0, 0, 0.749019607843137)]{1 o/ g  ^" T. [
[color=rgba(0, 0, 0, 0.749019607843137)]        assert(K > 0);1 {' r% K' j/ s6 q. H- V; q2 x
[color=rgba(0, 0, 0, 0.749019607843137)]        if (root == NULL)$ i) V9 _8 Y. o
[color=rgba(0, 0, 0, 0.749019607843137)]        {
5 O$ m+ |. `* E* W[color=rgba(0, 0, 0, 0.749019607843137)]                return 0;9 G! K) a+ f! G/ y9 t
[color=rgba(0, 0, 0, 0.749019607843137)]        }
' Y7 }; C% f$ T, c[color=rgba(0, 0, 0, 0.749019607843137)]        //如果是第一层(递归出口)
5 q/ `3 G, j, L, l  {2 e: `( C[color=rgba(0, 0, 0, 0.749019607843137)]        if (K == 1)
! N) k* ?1 W  L* h6 r- _[color=rgba(0, 0, 0, 0.749019607843137)]        {; A( u5 x6 |4 {3 s' x! l
[color=rgba(0, 0, 0, 0.749019607843137)]                return 1;8 i9 m2 A; y2 @1 E, t
[color=rgba(0, 0, 0, 0.749019607843137)]        }
2 G1 B4 u; h) F4 }) P& E: @% E[color=rgba(0, 0, 0, 0.749019607843137)]        //转换成子树的第K-1层
' Q# G2 H5 T! g' u5 t[color=rgba(0, 0, 0, 0.749019607843137)]        return TreeLevel(root->left,K-1) + TreeLevel(root->right,K-1);/ h- b1 V, f! n
[color=rgba(0, 0, 0, 0.749019607843137)]}1 t* T3 i1 L/ }" ?4 P. b0 v
[color=rgba(0, 0, 0, 0.749019607843137)]1  f7 ^# I7 a) X* T# t, l, G7 }
[color=rgba(0, 0, 0, 0.749019607843137)]26 i% b  ^5 M( |* j& q# Q
[color=rgba(0, 0, 0, 0.749019607843137)]3
, c+ W* H: D# t( ]+ N* ^[color=rgba(0, 0, 0, 0.749019607843137)]4
7 w' B6 P; A+ Z  k" X% A; S[color=rgba(0, 0, 0, 0.749019607843137)]5
9 A7 U1 {- Q9 e( F/ A- _[color=rgba(0, 0, 0, 0.749019607843137)]6
* E: p" e; y) d6 F5 c" {$ v[color=rgba(0, 0, 0, 0.749019607843137)]7. C0 A2 f* ~& W- t
[color=rgba(0, 0, 0, 0.749019607843137)]8. ]% h. H# K1 d  X4 H, g
[color=rgba(0, 0, 0, 0.749019607843137)]9
) Y" b$ f1 S1 z/ v. Q+ N+ P7 L[color=rgba(0, 0, 0, 0.749019607843137)]10
. A- d! @0 Q4 `7 R: \* D/ x[color=rgba(0, 0, 0, 0.749019607843137)]11
% U8 k( e  g' U/ m' G9 F[color=rgba(0, 0, 0, 0.749019607843137)]12, B$ a, @& `" g8 w
[color=rgba(0, 0, 0, 0.749019607843137)]13
  s# F4 e& d( Q: X3 X+ a7 Q, d[color=rgba(0, 0, 0, 0.749019607843137)]14
: S& n" y4 J% p& Z# T% E, H2 C[color=rgba(0, 0, 0, 0.749019607843137)]15% K) `+ I: d. _$ \( u( n
[color=rgba(0, 0, 0, 0.749019607843137)]16
/ I- V8 Q6 ~+ n5 m: W' V[color=rgba(0, 0, 0, 0.749019607843137)]2.6二叉树查找
8 n: `$ O# z0 }[color=rgba(0, 0, 0, 0.749019607843137)]//二叉树查找; P! D: _+ C' Z/ t8 ~
[color=rgba(0, 0, 0, 0.749019607843137)]BTNode* TreeFind(BTNode* root, BTDataType data)& w& _; C5 a4 p
[color=rgba(0, 0, 0, 0.749019607843137)]{
) i6 v6 [4 y" q' A9 @8 l[color=rgba(0, 0, 0, 0.749019607843137)]        if (root == NULL)
4 q4 b: _- x3 F: O[color=rgba(0, 0, 0, 0.749019607843137)]        {) D* w: z; ^+ |
[color=rgba(0, 0, 0, 0.749019607843137)]                return NULL;9 @; L6 C. V/ C1 \
[color=rgba(0, 0, 0, 0.749019607843137)]        }  W5 k) Y4 `4 M% |4 `5 `
[color=rgba(0, 0, 0, 0.749019607843137)]        if (root->data == data)$ `8 s. |- q" M, P2 R
[color=rgba(0, 0, 0, 0.749019607843137)]        {
; Q, u1 L, k% m* d' {; C) e[color=rgba(0, 0, 0, 0.749019607843137)]                return root;
% D, k7 {+ R% v/ v) x[color=rgba(0, 0, 0, 0.749019607843137)]        }! T: R# A% r2 l: e
[color=rgba(0, 0, 0, 0.749019607843137)]        //先查找左子树: a+ x) D: B2 Z3 |7 [( l
[color=rgba(0, 0, 0, 0.749019607843137)]        BTNode* lret = TreeFind(root->left, data);( c" |8 ~7 p7 F1 u  k
[color=rgba(0, 0, 0, 0.749019607843137)]        if (lret)0 Q1 z* B8 B/ h
[color=rgba(0, 0, 0, 0.749019607843137)]                return lret;$ p2 s' ~# }1 l' n
[color=rgba(0, 0, 0, 0.749019607843137)]        //再查找右子树
% |7 c# }( |' |0 J[color=rgba(0, 0, 0, 0.749019607843137)]        BTNode* rret = TreeFind(root->right, data);& T2 u/ f  e: T4 s( E
[color=rgba(0, 0, 0, 0.749019607843137)]        if (rret)
3 m4 ]9 g- Z8 R2 Y[color=rgba(0, 0, 0, 0.749019607843137)]                return rret;8 B: M/ \  D  |, n4 u4 c- D( k
[color=rgba(0, 0, 0, 0.749019607843137)]        return NULL;1 Y6 Y& [' J3 Y2 B" y' S( \
[color=rgba(0, 0, 0, 0.749019607843137)]}, u( v4 g- S# p% L* z
[color=rgba(0, 0, 0, 0.749019607843137)]————————————————
- O  N7 h6 A/ q- P  S% Q# \1 u[color=rgba(0, 0, 0, 0.749019607843137)]版权声明：本文为CSDN博主「SouLinya」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。& O; k# t1 s4 P- S+ \
[color=rgba(0, 0, 0, 0.749019607843137)]原文链接：https://blog.csdn.net/weixin_63449996/article/details/126841212" H6 _" w+ ?7 h' \- [

" T7 b- T: G) j
! s9 H2 U' F7 y3 b[color=rgba(0, 0, 0, 0.75)]
) ~7 }3 [+ N( d' [
  F6 _  t6 K5 F
( e/ F1 N% l) J% f6 x0 g4 E6 w/ L" F




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