【数据结构】二叉树的遍历：前序，中序，后序的递归结构遍历
1 Z1 C8 q8 _* [ \: v9 U' l% w. d+ R* O& B
[color=rgba(0, 0, 0, 0.749019607843137)]文章目录5 m6 t6 `3 _: M4 f+ M' [! C
[color=rgba(0, 0, 0, 0.749019607843137)]前言* ~4 H5 m& C/ L6 n
[color=rgba(0, 0, 0, 0.749019607843137)]1.二叉树的遍历方式5 N; K8 C6 c& N# |: m
[color=rgba(0, 0, 0, 0.749019607843137)]2.二叉树的遍历及相关函数（代码实现）
$ j* a5 e' Y" R( L1 S[color=rgba(0, 0, 0, 0.749019607843137)]2.1前序/中序/后序的遍历
V7 p) K9 F$ c V$ x" f[color=rgba(0, 0, 0, 0.749019607843137)]2.2计算二叉树的大小, n5 k7 ^( i# U4 a7 e. O4 ]
[color=rgba(0, 0, 0, 0.749019607843137)]2.3计算二叉树叶子结点的个数; U' S+ }( [9 K( `7 ^: K
[color=rgba(0, 0, 0, 0.749019607843137)]2.4计算二叉树的高度0 W" o0 O% Q# \, b( j' D
[color=rgba(0, 0, 0, 0.749019607843137)]2.5计算第K层结点的个数
F* Y6 j, n) z2 t7 }[color=rgba(0, 0, 0, 0.749019607843137)]2.6二叉树查找
3 S4 L# J2 k$ H9 D! b1 e! P4 q[color=rgba(0, 0, 0, 0.749019607843137)]前言" N, Z- \ R" k9 [
[color=rgba(0, 0, 0, 0.749019607843137)]在学习二叉树的遍历之前，我们需要先创建一棵二叉树，然后才能学习其相关的基本操作，由于现在我们对二叉树结构的掌握还在初阶部分，为了降低大家的学习成本，我们先手动快速创建一棵简单的二叉树，快速进入二叉树的操作学习，这个方法在我们调试程序代码的时候，也非常适用。等二叉树结构了解的差不多时，我们再继续研究二叉树真正的创建方式。
; P& |& S* Y G. ^. M* D[color=rgba(0, 0, 0, 0.749019607843137)]
5 ?8 h* B* a+ }( i. |3 _, I9 B1 @
/ I' s L8 W. _" l* N7 R: V1 G[color=rgba(0, 0, 0, 0.749019607843137)]1.二叉树的遍历方式
. c$ _; ?2 y& A1 d[color=rgba(0, 0, 0, 0.749019607843137)]
7 v' `* S) E& z. ^2 R& U0 J& R: L+ E
[color=rgba(0, 0, 0, 0.749019607843137)]按照规则，二叉树的遍历有：前序/中序/后序的递归结构遍历访问顺序： L% p+ `, }( |& V: L
[color=rgba(0, 0, 0, 0.749019607843137)]
2 X% O( q1 O+ X( `$ M- v4 |# q: G3 c Q' ~% f! r/ r- F
[color=rgba(0, 0, 0, 0.749019607843137)]1. 前序遍历（先序，先根):根——左子树——右子树2 K% L. v8 k! d
[color=rgba(0, 0, 0, 0.749019607843137)]; I1 D9 ?. v \! Z; W+ x8 b
( C& N# S- L- _ F, O& f8 c[color=rgba(0, 0, 0, 0.749019607843137)]
5 l" d% m% p$ A+ ]# b8 v ~9 ?0 K% K
[color=rgba(0, 0, 0, 0.749019607843137)]2. 中序遍历（中根）：左子树——根——右子树
& q. b1 ]4 t. S) W- i& D[color=rgba(0, 0, 0, 0.749019607843137)]
4 R/ U$ o/ d+ C' u& F6 U; {$ C7 O' q" O# p0 J+ O6 {
[color=rgba(0, 0, 0, 0.749019607843137)]! [' N- q/ E+ ^
/ c* N" u7 B+ G6 \[color=rgba(0, 0, 0, 0.749019607843137)]3. 后序遍历（后根）：左子树——右子树——根- d+ y0 m- k N j5 ]
[color=rgba(0, 0, 0, 0.749019607843137)]' p# v$ P. q X4 z
9 A- B: I o+ {% V% S3 l6 l8 L5 ` B[color=rgba(0, 0, 0, 0.749019607843137)]
# e2 b) `) `7 C1 M, p8 ?+ ^$ s# g- y& N* T# z" A2 z+ k( I) v8 F
[color=rgba(0, 0, 0, 0.749019607843137)]2.二叉树的遍历及相关函数（代码实现）
0 W1 o- f% F7 r' {9 j9 m8 L# w[color=rgba(0, 0, 0, 0.749019607843137)]思路：分而治之- t2 s) a8 V# @: z: U4 M
[color=rgba(0, 0, 0, 0.749019607843137)]1.首先我们要用简单的方式先创建出一棵二叉树，并赋予数据；2 U5 Y7 x& y) K3 ] M* f
[color=rgba(0, 0, 0, 0.749019607843137)]2.采用递归的方式，分别实现前序/中序/后序遍历这棵二叉树；
4 ~( F9 d G; N% S% I[color=rgba(0, 0, 0, 0.749019607843137)]3.尝试计算这个二叉树的大小（利用递归）；) n7 S# C0 }& C: @; e/ C+ I, o
[color=rgba(0, 0, 0, 0.749019607843137)]4.尝试计算叶子结点的个数（利用递归）；+ i' C8 T! b" z% p, W9 |2 {) g
[color=rgba(0, 0, 0, 0.749019607843137)]5.尝试计算二叉树的高度（利用递归）；' M; b: y: ^2 t* X- E
[color=rgba(0, 0, 0, 0.749019607843137)]6.尝试写出计算第K层结点的个数的函数（利用递归）；
4 K+ y& v" t1 H[color=rgba(0, 0, 0, 0.749019607843137)]7.尝试写出二叉树查找的函数（利用递归）。
. W7 y, T0 w/ z$ H( I[color=rgba(0, 0, 0, 0.749019607843137)]; t; d2 t% t9 F
" R/ f4 Z6 ?! v, U; K% @[color=rgba(0, 0, 0, 0.749019607843137)]2.1前序/中序/后序的遍历
2 N7 R- i5 K2 F, y[color=rgba(0, 0, 0, 0.749019607843137)]#define _CRT_SECURE_NO_WARNINGS 1
! S C3 s( V2 @9 k$ |" W7 D; E[color=rgba(0, 0, 0, 0.749019607843137)]#include<stdio.h>7 S1 P" `# U# {1 s* V
[color=rgba(0, 0, 0, 0.749019607843137)]#include<assert.h>" j+ p' }: F& S3 `% \
[color=rgba(0, 0, 0, 0.749019607843137)]#include<stdlib.h>& A- @/ ^$ Y4 B8 _/ Z) d& u# t( T7 Y
[color=rgba(0, 0, 0, 0.749019607843137)]4 _% ?3 Z( g+ |1 B4 X/ @
# d$ s* s* O0 ^1 B* d
[color=rgba(0, 0, 0, 0.749019607843137)]typedef int BTDataType;5 ?) N0 p0 V5 ?8 ~3 t M* ]6 \2 u5 M
[color=rgba(0, 0, 0, 0.749019607843137)]! {/ a3 L2 y7 |: }2 }
; b" a) ~, x& t5 ^8 S- u[color=rgba(0, 0, 0, 0.749019607843137)]//定义二叉树结点的结构体# ]' O( F; c6 h" K
[color=rgba(0, 0, 0, 0.749019607843137)]typedef struct BinaryTreeNode
& T+ k( E* C* f5 V, t S" T[color=rgba(0, 0, 0, 0.749019607843137)]{: o; L; h0 K9 @9 I! L0 V8 N0 [
[color=rgba(0, 0, 0, 0.749019607843137)] BTDataType data;
7 J) U3 q3 E5 c" M[color=rgba(0, 0, 0, 0.749019607843137)] struct BinaryTreeNode* left;
4 Q3 \9 C& ]0 e' S[color=rgba(0, 0, 0, 0.749019607843137)] struct BinaryTreeNode* right;' q! ]" D* c! `/ k; }& O/ P9 u6 f
[color=rgba(0, 0, 0, 0.749019607843137)]}BTNode;% A$ J7 \( F; _3 }1 q: t; v: ^3 {7 W
[color=rgba(0, 0, 0, 0.749019607843137)]& J. D0 L5 J; u# {2 ^/ c
# H. g- X! d3 T1 N1 A[color=rgba(0, 0, 0, 0.749019607843137)]//前序遍历% k6 G7 ?& ]+ L2 W7 c4 d
[color=rgba(0, 0, 0, 0.749019607843137)]void PreOrder(BTNode* root)8 v7 C* a+ W1 C! l. b
[color=rgba(0, 0, 0, 0.749019607843137)]{% i" S" J. V. O; r4 a) D" r
[color=rgba(0, 0, 0, 0.749019607843137)] if (root == NULL)9 r8 S" Z* e: i/ L$ c+ S" S. }) r
[color=rgba(0, 0, 0, 0.749019607843137)] {
" V2 x9 d( K% @# I9 Y[color=rgba(0, 0, 0, 0.749019607843137)] printf("NULL ");- O+ f$ f7 M$ U
[color=rgba(0, 0, 0, 0.749019607843137)] return;7 Q! R# e$ x$ T3 g
[color=rgba(0, 0, 0, 0.749019607843137)] }9 t) D/ P) x9 f
[color=rgba(0, 0, 0, 0.749019607843137)] printf("%d ", root->data);9 Z0 ]8 Y1 P1 U: a/ r/ s2 `
[color=rgba(0, 0, 0, 0.749019607843137)] PreOrder(root->left);" ?2 P2 G8 ~3 ~7 [7 m
[color=rgba(0, 0, 0, 0.749019607843137)] PreOrder(root->right);) t2 j+ N: X. `3 `9 `
[color=rgba(0, 0, 0, 0.749019607843137)]}
+ W" j, {( J, C( ]' X2 y3 v4 L1 ^[color=rgba(0, 0, 0, 0.749019607843137)]//中序遍历
* H, C8 l% M+ w[color=rgba(0, 0, 0, 0.749019607843137)]void InOrder(BTNode* root)
7 V/ A `8 x4 ?) A" ]) T# {[color=rgba(0, 0, 0, 0.749019607843137)]{! ~ w3 k; U9 W" h3 J2 R1 x; l
[color=rgba(0, 0, 0, 0.749019607843137)] if (root == NULL)$ A$ P/ H6 {* h+ ^& [
[color=rgba(0, 0, 0, 0.749019607843137)] {# S4 w: ]* F, Z% m/ q1 p3 V5 Y
[color=rgba(0, 0, 0, 0.749019607843137)] printf("NULL ");5 P+ H# K% I1 T
[color=rgba(0, 0, 0, 0.749019607843137)] return;" f r% O F* B; y( }8 l
[color=rgba(0, 0, 0, 0.749019607843137)] }8 l" L, S$ D* Q5 B0 G. v0 o! B! M
[color=rgba(0, 0, 0, 0.749019607843137)] InOrder(root->left);& D7 s$ X! K# x6 g
[color=rgba(0, 0, 0, 0.749019607843137)] printf("%d ", root->data);4 P D# q) N( J/ {
[color=rgba(0, 0, 0, 0.749019607843137)] InOrder(root->right);
9 P) Y7 h8 b7 s, L[color=rgba(0, 0, 0, 0.749019607843137)]}* k$ b7 P: R/ p+ d: E
[color=rgba(0, 0, 0, 0.749019607843137)]//后序遍历
2 _9 [/ _; X; W) s9 }8 t8 N[color=rgba(0, 0, 0, 0.749019607843137)]void PostOrder(BTNode* root)' ]" j6 @/ g/ }
[color=rgba(0, 0, 0, 0.749019607843137)]{& z' R. E9 f: ^0 Q0 |9 o
[color=rgba(0, 0, 0, 0.749019607843137)] if (root == NULL)
! y0 s5 J: e8 v5 j9 B[color=rgba(0, 0, 0, 0.749019607843137)] {6 O8 R; D; H6 E
[color=rgba(0, 0, 0, 0.749019607843137)] printf("NULL "); h( L; e& l8 v
[color=rgba(0, 0, 0, 0.749019607843137)] return;
& G; C4 D9 D( x$ e[color=rgba(0, 0, 0, 0.749019607843137)] }& Q Y& \/ x& L8 v5 Q
[color=rgba(0, 0, 0, 0.749019607843137)] PostOrder(root->left);* v3 Y- K8 V9 C0 H5 R# I8 K
[color=rgba(0, 0, 0, 0.749019607843137)] PostOrder(root->right);
C; e3 n( y' T$ r2 G: q7 l[color=rgba(0, 0, 0, 0.749019607843137)] printf("%d ", root->data);
" ^) s; q r1 P* h2 P[color=rgba(0, 0, 0, 0.749019607843137)]}. f. Z9 v5 c: C: X
[color=rgba(0, 0, 0, 0.749019607843137)]//先创建一个简单的二叉树结构 o; y8 V0 s' `0 r( o
[color=rgba(0, 0, 0, 0.749019607843137)]BTNode* CreateTree()7 o3 p. X- _) W$ M/ T6 J* ^
[color=rgba(0, 0, 0, 0.749019607843137)]{5 B8 m! \/ S D% k* a: d L
[color=rgba(0, 0, 0, 0.749019607843137)] //先动态开辟6个结点的空间 A9 }4 w0 x! F, @- X% }
[color=rgba(0, 0, 0, 0.749019607843137)] BTNode* n1 = (BTNode*)malloc(sizeof(BTNode));5 l Q" X& o$ j9 l* L3 ~
[color=rgba(0, 0, 0, 0.749019607843137)] assert(n1);( X& i" X8 ?+ }% z% e* l/ j
[color=rgba(0, 0, 0, 0.749019607843137)] BTNode* n2 = (BTNode*)malloc(sizeof(BTNode));
8 s" _# E' b( Z. O7 d! r[color=rgba(0, 0, 0, 0.749019607843137)] assert(n2);# Z' ~) M" b$ J( v9 @; s& N
[color=rgba(0, 0, 0, 0.749019607843137)] BTNode* n3 = (BTNode*)malloc(sizeof(BTNode));; ?* _; F+ `1 r% o4 e
[color=rgba(0, 0, 0, 0.749019607843137)] assert(n3);9 Y) c8 `9 a: W% e1 Q( M9 V1 c, I
[color=rgba(0, 0, 0, 0.749019607843137)] BTNode* n4 = (BTNode*)malloc(sizeof(BTNode));
, T1 `6 g$ T, m2 {: [[color=rgba(0, 0, 0, 0.749019607843137)] assert(n4);# \6 I" ?* v4 E" d
[color=rgba(0, 0, 0, 0.749019607843137)] BTNode* n5 = (BTNode*)malloc(sizeof(BTNode));
9 E. \2 E2 @! k) j[color=rgba(0, 0, 0, 0.749019607843137)] assert(n5);# v; H6 N [; p
[color=rgba(0, 0, 0, 0.749019607843137)] BTNode* n6 = (BTNode*)malloc(sizeof(BTNode));
7 v$ ?( D* Z5 X( R# d[color=rgba(0, 0, 0, 0.749019607843137)] assert(n6);
( ^3 K, m, V2 V X/ l' M[color=rgba(0, 0, 0, 0.749019607843137)]
) r/ W! \1 G# n! j4 r5 ?. h% e- w4 @* d
[color=rgba(0, 0, 0, 0.749019607843137)] n1->data = 1;' A9 K3 ?4 U/ i; x9 Z; m* \) u* k$ \
[color=rgba(0, 0, 0, 0.749019607843137)] n2->data = 2;: D# ^5 E& }% P5 x1 f. E
[color=rgba(0, 0, 0, 0.749019607843137)] n3->data = 3;4 b- X* G2 J3 A$ s
[color=rgba(0, 0, 0, 0.749019607843137)] n4->data = 4;
1 h! K: C/ C; ^/ \! P' }" y[color=rgba(0, 0, 0, 0.749019607843137)] n5->data = 5;! R: D5 B/ a( u, P- x$ I
[color=rgba(0, 0, 0, 0.749019607843137)] n6->data = 6;
" |& @, X2 v( o, @9 E& ~, k[color=rgba(0, 0, 0, 0.749019607843137)]+ I0 U( w8 r' d; M! j
% ?: o$ ]. K; j% P! [) f
[color=rgba(0, 0, 0, 0.749019607843137)] n1->left = n2;
. _* p5 p# ~! L' Z) v[color=rgba(0, 0, 0, 0.749019607843137)] n1->right = n4;- {% I6 Y% p" j" t
[color=rgba(0, 0, 0, 0.749019607843137)] n2->left = n3;+ r& w0 g5 _4 ?* M& s, w9 |- }
[color=rgba(0, 0, 0, 0.749019607843137)] n2->right = NULL;
- B& q9 D1 ^3 ^( \/ \0 |1 U0 Y[color=rgba(0, 0, 0, 0.749019607843137)] n3->left = NULL;0 {$ e. s* Y5 F) D% M5 d+ o
[color=rgba(0, 0, 0, 0.749019607843137)] n3->right = NULL;
' d) n4 K; h; I[color=rgba(0, 0, 0, 0.749019607843137)] n4->left = n5;
4 @3 U9 Y7 n0 q! |, [0 A) C* I[color=rgba(0, 0, 0, 0.749019607843137)] n4->right = n6;
7 r+ s) P' N5 \8 |3 t[color=rgba(0, 0, 0, 0.749019607843137)] n5->left = NULL;9 Y( j5 z; z! T& F
[color=rgba(0, 0, 0, 0.749019607843137)] n5->right = NULL;
/ f( M+ l& g4 J0 n/ w$ U ^[color=rgba(0, 0, 0, 0.749019607843137)] n6->left = NULL;2 y# U6 E0 Z1 P9 l( _
[color=rgba(0, 0, 0, 0.749019607843137)] n6->right = NULL;
! @& z% l: D j) V[color=rgba(0, 0, 0, 0.749019607843137)]
+ h( m4 q( x# L/ X! s1 @2 V' l6 s; \- M) Q- `# l% Q" _
[color=rgba(0, 0, 0, 0.749019607843137)] return n1;
- }8 V4 \$ L' M# f/ p6 k* S[color=rgba(0, 0, 0, 0.749019607843137)]}: g5 d3 d, {- }9 w( h3 u6 T
[color=rgba(0, 0, 0, 0.749019607843137)]
/ U1 e9 s' ~9 ?
3 ~: U e) [9 s[color=rgba(0, 0, 0, 0.749019607843137)]int main()0 N' i- \ a- ~/ C
[color=rgba(0, 0, 0, 0.749019607843137)]{5 `& R2 ]9 Z# B3 l
[color=rgba(0, 0, 0, 0.749019607843137)] //先创建一个简单的二叉树结构8 M; n" w; M2 k! ?) s
[color=rgba(0, 0, 0, 0.749019607843137)] BTNode* root = CreateTree();
/ x$ h* P0 r* n4 L9 D0 e+ m) V[color=rgba(0, 0, 0, 0.749019607843137)]
. K& j/ O/ I5 n4 g8 e$ G; n7 P E. M) u& [/ p5 K h
[color=rgba(0, 0, 0, 0.749019607843137)] //二叉树前序遍历
S4 G" U( ^# w[color=rgba(0, 0, 0, 0.749019607843137)] printf("二叉树前序遍历:");7 X2 \$ R" Q R" K
[color=rgba(0, 0, 0, 0.749019607843137)] PreOrder(root);. G: b4 L* S; `7 D
[color=rgba(0, 0, 0, 0.749019607843137)] printf("\n");9 k/ |$ ]" K; F' Z
[color=rgba(0, 0, 0, 0.749019607843137)] //二叉树中序遍历" Y: O4 x; V6 Q. N
[color=rgba(0, 0, 0, 0.749019607843137)] printf("二叉树中序序遍历:");" h V1 q! N7 g3 n$ Z1 ~
[color=rgba(0, 0, 0, 0.749019607843137)] InOrder(root);
/ T: q/ T$ ~ q, g2 [: d w6 _[color=rgba(0, 0, 0, 0.749019607843137)] printf("\n");0 w, _) s* | I) Q2 n; Q
[color=rgba(0, 0, 0, 0.749019607843137)] //二叉树后序遍历
- w6 d6 g2 D/ m+ B6 L% ~[color=rgba(0, 0, 0, 0.749019607843137)] printf("二叉树后序遍历:");
+ u% J$ z" {6 T8 D2 V8 L[color=rgba(0, 0, 0, 0.749019607843137)] PostOrder(root);
& c+ M& h: }/ p' U[color=rgba(0, 0, 0, 0.749019607843137)] printf("\n");
$ V+ X0 @) v; ^% x" }. z& g5 X[color=rgba(0, 0, 0, 0.749019607843137)]% }* [: X6 v3 b% ]: K/ J3 t& h
& a/ S$ B' c/ B, X! M: b/ g6 j[color=rgba(0, 0, 0, 0.749019607843137)] return 0;
9 @6 d; ]' n6 E- X" y[color=rgba(0, 0, 0, 0.749019607843137)]}
. o* s+ F# h) d" R; T[color=rgba(0, 0, 0, 0.749019607843137)]1
S$ z1 X0 x$ J1 l3 f' L- Z4 I[color=rgba(0, 0, 0, 0.749019607843137)]2
$ f/ w& X0 f5 L. {8 X2 R3 }[color=rgba(0, 0, 0, 0.749019607843137)]3& m7 d- D7 x E# }! _
[color=rgba(0, 0, 0, 0.749019607843137)]4
- W9 y1 W/ ?( \6 B[color=rgba(0, 0, 0, 0.749019607843137)]51 K7 d5 a- ]* _8 I" g5 z% P) i
[color=rgba(0, 0, 0, 0.749019607843137)]64 l; E4 V6 ~: [4 V& H& |. D3 j9 Z+ q
[color=rgba(0, 0, 0, 0.749019607843137)]7" l/ x* N a9 x3 n& C
[color=rgba(0, 0, 0, 0.749019607843137)]80 ~. J' c7 j4 j' \, F! [+ u; [2 u
[color=rgba(0, 0, 0, 0.749019607843137)]9
: N3 e1 G# }) E; H5 [% q8 ]. K[color=rgba(0, 0, 0, 0.749019607843137)]10
. |- }. _4 l1 M; ]! e' o! j[color=rgba(0, 0, 0, 0.749019607843137)]11
: Y/ q" }* [% q o$ p[color=rgba(0, 0, 0, 0.749019607843137)]12
' C% [9 f+ f% y- v$ J( n) L[color=rgba(0, 0, 0, 0.749019607843137)]13
5 {: s" K* J* k, c5 |[color=rgba(0, 0, 0, 0.749019607843137)]14' \! J) @/ [" l. ^/ L
[color=rgba(0, 0, 0, 0.749019607843137)]15
' [9 ^# B1 @$ z9 r$ T5 A[color=rgba(0, 0, 0, 0.749019607843137)]16
) H5 u3 S$ O& v3 B+ y/ y1 F" @) F[color=rgba(0, 0, 0, 0.749019607843137)]17/ R, x4 ~0 K/ q* B$ u' s( c
[color=rgba(0, 0, 0, 0.749019607843137)]18
( @7 \0 G- X/ [[color=rgba(0, 0, 0, 0.749019607843137)]197 k, e- t. x0 m
[color=rgba(0, 0, 0, 0.749019607843137)]203 A' v5 l7 B( a1 |1 P3 e
[color=rgba(0, 0, 0, 0.749019607843137)]21! d* F+ o( U- o" l
[color=rgba(0, 0, 0, 0.749019607843137)]22
) X4 c4 A. B2 R+ S& B j5 S- t- i[color=rgba(0, 0, 0, 0.749019607843137)]238 N; l: W3 b; {
[color=rgba(0, 0, 0, 0.749019607843137)]24" ?) X; n" b# W- Q* }
[color=rgba(0, 0, 0, 0.749019607843137)]25
$ ^& _3 ?8 |4 p# f9 d( p& Z[color=rgba(0, 0, 0, 0.749019607843137)]26
* C( d, T3 Q8 u. Q- Q4 R[color=rgba(0, 0, 0, 0.749019607843137)]274 n d+ f+ p) Q8 g" k5 a( J% x
[color=rgba(0, 0, 0, 0.749019607843137)]28+ P. ]$ Q* A* G$ q5 d }* ^* v
[color=rgba(0, 0, 0, 0.749019607843137)]29, G. x9 H2 l9 m: `* V
[color=rgba(0, 0, 0, 0.749019607843137)]30& F; B( {% D4 T2 E' ?
[color=rgba(0, 0, 0, 0.749019607843137)]31
. G5 T& S, F, D% T0 B2 ][color=rgba(0, 0, 0, 0.749019607843137)]32 ^. u1 ?$ ^. @; k( O
[color=rgba(0, 0, 0, 0.749019607843137)]33' X5 ~) x3 J. J& P
[color=rgba(0, 0, 0, 0.749019607843137)]346 B* @, ~* w8 A8 v1 n! {
[color=rgba(0, 0, 0, 0.749019607843137)]35" f2 ?6 C' P8 }3 Z Q( u s( x
[color=rgba(0, 0, 0, 0.749019607843137)]36- c3 C# w" g: U: X
[color=rgba(0, 0, 0, 0.749019607843137)]37' R$ R' D/ c. H& ]
[color=rgba(0, 0, 0, 0.749019607843137)]38
" g# L: X- d$ w3 G A8 J[color=rgba(0, 0, 0, 0.749019607843137)]39# q$ a9 `8 T8 B
[color=rgba(0, 0, 0, 0.749019607843137)]40
) A! v& g( b n7 _1 `; m[color=rgba(0, 0, 0, 0.749019607843137)]41
U9 M: b+ ]5 l9 P; v! m[color=rgba(0, 0, 0, 0.749019607843137)]421 C# S: E* K0 u( D# E0 W/ {7 }" ^' G
[color=rgba(0, 0, 0, 0.749019607843137)]43
7 {: \9 A5 `0 |8 q; r0 M[color=rgba(0, 0, 0, 0.749019607843137)]44
' g$ _: a& k5 F' E/ T4 S3 ?; T: h[color=rgba(0, 0, 0, 0.749019607843137)]45+ G0 o7 L ^) Y; X, D* {
[color=rgba(0, 0, 0, 0.749019607843137)]46' d: W3 I \3 _5 E' ^$ T
[color=rgba(0, 0, 0, 0.749019607843137)]47. P. o5 d {# r$ \$ b7 t: |
[color=rgba(0, 0, 0, 0.749019607843137)]48
8 w' n" U4 ]4 M: l l! E/ U( m[color=rgba(0, 0, 0, 0.749019607843137)]49
4 o% k9 O! X, O; T5 T- h[color=rgba(0, 0, 0, 0.749019607843137)]504 G1 R( w) z2 Q$ q3 {4 j5 p8 M; ]
[color=rgba(0, 0, 0, 0.749019607843137)]51/ e! z7 B4 R4 e% h
[color=rgba(0, 0, 0, 0.749019607843137)]52; w! S4 e% ~$ t% |- L
[color=rgba(0, 0, 0, 0.749019607843137)]531 Z- A! R0 W( X0 ~8 o
[color=rgba(0, 0, 0, 0.749019607843137)]54
4 n+ u, U7 O8 f- M[color=rgba(0, 0, 0, 0.749019607843137)]553 d" } u9 ^! }* g; _" u% K
[color=rgba(0, 0, 0, 0.749019607843137)]56
& J" X1 Y6 M( N% s- K- J: g; c[color=rgba(0, 0, 0, 0.749019607843137)]57
- S& F9 p& s' t7 K5 @: I* ~ P1 @[color=rgba(0, 0, 0, 0.749019607843137)]58; e2 A0 H w6 a7 h7 F
[color=rgba(0, 0, 0, 0.749019607843137)]59
- s9 |. M1 T( j[color=rgba(0, 0, 0, 0.749019607843137)]60: ~8 |& `" g2 ]2 N' P
[color=rgba(0, 0, 0, 0.749019607843137)]61
! i' s- m( b8 f- v[color=rgba(0, 0, 0, 0.749019607843137)]62
- F8 K: \7 n6 C1 U8 ][color=rgba(0, 0, 0, 0.749019607843137)]63$ y7 Y$ L! j5 ^0 L8 B" D: {/ s
[color=rgba(0, 0, 0, 0.749019607843137)]64
. O0 `( v9 k8 k* s* g[color=rgba(0, 0, 0, 0.749019607843137)]65
1 g- J' k. M# j4 D+ j" N[color=rgba(0, 0, 0, 0.749019607843137)]66
- t% x: L* J9 U) L[color=rgba(0, 0, 0, 0.749019607843137)]67/ s# Z( f0 g$ K
[color=rgba(0, 0, 0, 0.749019607843137)]68
7 i e# j4 K6 q# x$ y- i2 ]* c[color=rgba(0, 0, 0, 0.749019607843137)]69
" E4 M* }- E2 G[color=rgba(0, 0, 0, 0.749019607843137)]70! |. a- k# T2 Y) E4 t3 u
[color=rgba(0, 0, 0, 0.749019607843137)]71
" A9 t1 P6 ~! _3 P[color=rgba(0, 0, 0, 0.749019607843137)]72
5 [' w- }# \. M# R[color=rgba(0, 0, 0, 0.749019607843137)]73
$ l n8 f( Q& `! i. i[color=rgba(0, 0, 0, 0.749019607843137)]74) V+ \, `$ D. ?+ G
[color=rgba(0, 0, 0, 0.749019607843137)]75
+ k$ [3 b; d2 B6 r( U[color=rgba(0, 0, 0, 0.749019607843137)]76: {) C) X. V- K& U
[color=rgba(0, 0, 0, 0.749019607843137)]77
5 w6 Y( f2 W7 S- L, e[color=rgba(0, 0, 0, 0.749019607843137)]78
0 [' n& `& v2 \! M* O' J8 H[color=rgba(0, 0, 0, 0.749019607843137)]79. E+ ]# Y2 Y8 C+ g, R/ ?
[color=rgba(0, 0, 0, 0.749019607843137)]80) g( z6 V0 b' I+ m2 `
[color=rgba(0, 0, 0, 0.749019607843137)]81/ d( q; ]# z1 N% l7 w
[color=rgba(0, 0, 0, 0.749019607843137)]82
$ l$ u' v1 U% h[color=rgba(0, 0, 0, 0.749019607843137)]83
# p, o- f1 n$ _; n[color=rgba(0, 0, 0, 0.749019607843137)]84; ], ?7 V/ `2 H H5 z
[color=rgba(0, 0, 0, 0.749019607843137)]85
* t& z: g/ y( y. i. Q0 A' K[color=rgba(0, 0, 0, 0.749019607843137)]86
6 j4 [9 M0 H; s[color=rgba(0, 0, 0, 0.749019607843137)]878 |- b, H2 u2 D/ f8 U5 R. b
[color=rgba(0, 0, 0, 0.749019607843137)]88
5 S# p+ L. j* h ^9 I& s[color=rgba(0, 0, 0, 0.749019607843137)]898 a: n B/ X; }9 Q0 g$ K/ l
[color=rgba(0, 0, 0, 0.749019607843137)]90
* H& h0 {/ F8 Q D1 M[color=rgba(0, 0, 0, 0.749019607843137)]91. D, @3 `: I$ U U
[color=rgba(0, 0, 0, 0.749019607843137)]92
, C0 c) g; g/ m& r# c$ F[color=rgba(0, 0, 0, 0.749019607843137)]93
6 A/ ?6 Q1 [' @[color=rgba(0, 0, 0, 0.749019607843137)]94
4 l# C; _) {* T: W[color=rgba(0, 0, 0, 0.749019607843137)]95
' w4 e1 z& t7 P7 d& z[color=rgba(0, 0, 0, 0.749019607843137)]96( _4 }" |- F C. N: K
[color=rgba(0, 0, 0, 0.749019607843137)]97
! m* n5 @+ |' X! |[color=rgba(0, 0, 0, 0.749019607843137)]98& q W! Z1 x @0 L* D& N7 H6 ^
[color=rgba(0, 0, 0, 0.749019607843137)]99! e( s3 V8 H' W: z$ w
[color=rgba(0, 0, 0, 0.749019607843137)]100% m* j0 r+ e% n w( d
[color=rgba(0, 0, 0, 0.749019607843137)]101
" {4 c7 Q& }% ][color=rgba(0, 0, 0, 0.749019607843137)]102, r: v3 B2 e+ O# g8 }
[color=rgba(0, 0, 0, 0.749019607843137)]1031 K4 }' L/ ?: L+ ]
[color=rgba(0, 0, 0, 0.749019607843137)]104
: C) u! z& W9 G1 m$ W% ~; E/ h/ m[color=rgba(0, 0, 0, 0.749019607843137)]105/ q5 k* n, i' m3 R3 M* W
[color=rgba(0, 0, 0, 0.749019607843137)]1065 O* P9 {' ?3 P4 _( c+ |6 G, W% B
[color=rgba(0, 0, 0, 0.749019607843137)]107/ J1 ~% v. C) R1 }/ l" Y
[color=rgba(0, 0, 0, 0.749019607843137)]108
; `3 `& M/ c9 T: v. N[color=rgba(0, 0, 0, 0.749019607843137)]109
6 x+ k+ L8 U% W( A3 a8 n7 E# p[color=rgba(0, 0, 0, 0.749019607843137)]110$ B% e1 f; m. @$ X$ T% f; ~/ G
[color=rgba(0, 0, 0, 0.749019607843137)]1117 S. z4 C, I7 G4 K4 }
[color=rgba(0, 0, 0, 0.749019607843137)]测试结果：
3 u' d' Y% H( e/ r; [9 K[color=rgba(0, 0, 0, 0.749019607843137)]
6 V/ j; j$ P% _) r- ?6 ?) W+ J" s6 x; [
[color=rgba(0, 0, 0, 0.749019607843137)]
4 H+ E, e% L! v' W) R# T# e" V l
' ~0 Z4 j) z- d y% u9 s% B; l[color=rgba(0, 0, 0, 0.749019607843137)]2.2计算二叉树的大小* w, m1 Z. Q7 _( c
[color=rgba(0, 0, 0, 0.749019607843137)]时间复杂度为O(N)# t0 c, j3 D9 q5 }9 l% p
[color=rgba(0, 0, 0, 0.749019607843137)] b* j" g* q% @3 X/ ?
, o' S: s0 s2 j* [5 y$ r
[color=rgba(0, 0, 0, 0.749019607843137)]//二叉树的大小; B# V% ^5 B5 v! k, |
[color=rgba(0, 0, 0, 0.749019607843137)]//法一：全局变量
. U: R+ l. K/ |" H4 R4 J[color=rgba(0, 0, 0, 0.749019607843137)]//int count = 0;
V( e, N- {+ r1 h( Z8 m, }[color=rgba(0, 0, 0, 0.749019607843137)]//void TreeSize(BTNode* root)
8 F$ C8 s/ [; c& t6 i[color=rgba(0, 0, 0, 0.749019607843137)]//{' \% Y+ Y4 m$ \' {- f
[color=rgba(0, 0, 0, 0.749019607843137)]// if (root == NULL)
9 y7 M+ x0 u; [" C/ n3 O[color=rgba(0, 0, 0, 0.749019607843137)]// { b$ z/ i/ X' M6 |9 ]. i
[color=rgba(0, 0, 0, 0.749019607843137)]// return;: C0 r8 L6 q, n# ^, ]& W9 m1 N
[color=rgba(0, 0, 0, 0.749019607843137)]// }) F% U" C% R' M4 S& o. y
[color=rgba(0, 0, 0, 0.749019607843137)]// count++;: l9 D n4 F+ @! k
[color=rgba(0, 0, 0, 0.749019607843137)]// TreeSize(root->left);6 {6 b. `; Z& d+ z7 q2 r
[color=rgba(0, 0, 0, 0.749019607843137)]// TreeSize(root->right);1 J' v$ d& `* Z$ i1 L9 n7 G
[color=rgba(0, 0, 0, 0.749019607843137)]//# m' w( A2 g, s& T
[color=rgba(0, 0, 0, 0.749019607843137)]// return;//函数栈帧层层返回，最后回到根节点1，结束了1的右子树函数，什么都不返回，因为count是全局变量
: ^9 M, h: m8 s* [7 u# h J[color=rgba(0, 0, 0, 0.749019607843137)]//}
9 b4 p7 H2 G+ h: q% b4 R[color=rgba(0, 0, 0, 0.749019607843137)]//法二：子问题思路：分而治之! R0 {* |4 B8 G
[color=rgba(0, 0, 0, 0.749019607843137)]int TreeSize(BTNode* root)$ z" D. ~- c/ @; j0 Q/ b; a2 x+ a
[color=rgba(0, 0, 0, 0.749019607843137)]{9 ~% Y& a# n: V. P
[color=rgba(0, 0, 0, 0.749019607843137)] return root == NULL ? 0 : TreeSize(root->left) + TreeSize(root->right) + 1;
$ N1 c4 w5 r7 d$ Z. j[color=rgba(0, 0, 0, 0.749019607843137)]}
+ S- q4 D% ]4 p% U% O[color=rgba(0, 0, 0, 0.749019607843137)]16 S. D& G7 i/ _( B, d- K0 B- |- w
[color=rgba(0, 0, 0, 0.749019607843137)]24 ]6 p; b+ N& J! x
[color=rgba(0, 0, 0, 0.749019607843137)]38 H* A4 p/ _5 [" T/ D& ^9 n. m
[color=rgba(0, 0, 0, 0.749019607843137)]4# y8 p) U5 d; ` j% ~
[color=rgba(0, 0, 0, 0.749019607843137)]5
+ L- V, Z: x. `[color=rgba(0, 0, 0, 0.749019607843137)]6
/ w. r7 y- h7 s& ^- ?' o[color=rgba(0, 0, 0, 0.749019607843137)]7
) k9 e. L: i! v- A0 q- [6 {& Q[color=rgba(0, 0, 0, 0.749019607843137)]8, Q" S0 k. D4 y: i4 y4 m: j
[color=rgba(0, 0, 0, 0.749019607843137)]9! g8 Y4 g i9 {) R: W/ Z
[color=rgba(0, 0, 0, 0.749019607843137)]101 J5 a$ Z1 v) z0 o
[color=rgba(0, 0, 0, 0.749019607843137)]11
5 T1 r1 n# A$ h: C- j[color=rgba(0, 0, 0, 0.749019607843137)]12" s$ \& @% i0 ~5 u* z6 M
[color=rgba(0, 0, 0, 0.749019607843137)]13
. |4 l/ F1 b! V% W: h3 y& S- e% i0 \/ c[color=rgba(0, 0, 0, 0.749019607843137)]14
2 e3 _- b s9 R% A. F4 w" _[color=rgba(0, 0, 0, 0.749019607843137)]15
" g F( E z0 \" D! k4 V$ F[color=rgba(0, 0, 0, 0.749019607843137)]16
& c7 u* `4 B; C4 t: R[color=rgba(0, 0, 0, 0.749019607843137)]17% g$ {. G4 b8 u, M) Q2 d4 W
[color=rgba(0, 0, 0, 0.749019607843137)]18
0 V% L7 Q. W2 `! @& ]. e[color=rgba(0, 0, 0, 0.749019607843137)]19 T9 e2 g& {/ Z: N2 A9 O: E& r
[color=rgba(0, 0, 0, 0.749019607843137)]20+ X6 a% T9 K& P
[color=rgba(0, 0, 0, 0.749019607843137)]2.3计算二叉树叶子结点的个数5 N6 m- l/ K( ^. B' ^) n! h9 ]! C
[color=rgba(0, 0, 0, 0.749019607843137)]//计算二叉树叶子结点的个数
) X7 r" ^6 q+ j; ]8 W[color=rgba(0, 0, 0, 0.749019607843137)]int TreeLeafSize(BTNode* root)- y+ V7 Q) K0 F/ W; m( M
[color=rgba(0, 0, 0, 0.749019607843137)]{' C1 }/ x; I. ^, c! T
[color=rgba(0, 0, 0, 0.749019607843137)] if (root == NULL)//首先得考虑空树的情况,0个叶子结点
3 E- c5 z* h) c2 G' |( L7 N[color=rgba(0, 0, 0, 0.749019607843137)] {; X2 B$ c- b2 v
[color=rgba(0, 0, 0, 0.749019607843137)] return 0;; a& E- g+ D/ T3 `) f) r
[color=rgba(0, 0, 0, 0.749019607843137)] }
2 _" ?! u+ g, G& w n3 M[color=rgba(0, 0, 0, 0.749019607843137)] //叶子结点的特征就是左右子树为空) E: R/ e" H# D, V2 t" i
[color=rgba(0, 0, 0, 0.749019607843137)] if (root->left == NULL && root->right == NULL)
+ M: X; R( N- p: O" [0 H[color=rgba(0, 0, 0, 0.749019607843137)] {* z; y* s; L: \' D" w
[color=rgba(0, 0, 0, 0.749019607843137)] return 1;
7 [. B$ a& ~8 z, P% ?; v/ C7 f$ d1 h[color=rgba(0, 0, 0, 0.749019607843137)] }0 x1 k2 u ~( C
[color=rgba(0, 0, 0, 0.749019607843137)] return TreeLeafSize(root->left) + TreeLeafSize(root->right);+ ]1 z! [9 P& T R& s( e
[color=rgba(0, 0, 0, 0.749019607843137)]}
5 C" P* G6 u6 L; ^6 c+ X+ E[color=rgba(0, 0, 0, 0.749019607843137)]1" W: T- q9 `0 x/ }# h
[color=rgba(0, 0, 0, 0.749019607843137)]2
- x% z1 i7 G* a3 z[color=rgba(0, 0, 0, 0.749019607843137)]3) I4 U! [% ?& a4 K% z I
[color=rgba(0, 0, 0, 0.749019607843137)]4$ M2 d" V7 ~& C
[color=rgba(0, 0, 0, 0.749019607843137)]58 [( H- M/ ^; b! K, {2 L
[color=rgba(0, 0, 0, 0.749019607843137)]6
6 q. x8 s; d f! _2 Z2 d[color=rgba(0, 0, 0, 0.749019607843137)]7
5 l* E! f* W4 M, s8 c4 {[color=rgba(0, 0, 0, 0.749019607843137)]8
" H3 H# V4 q, E+ ?* A[color=rgba(0, 0, 0, 0.749019607843137)]9" a, R3 _1 j2 T$ O% {% e, Y$ `
[color=rgba(0, 0, 0, 0.749019607843137)]106 R5 n2 e" j) g! T# U
[color=rgba(0, 0, 0, 0.749019607843137)]11/ E) j% t8 }2 L% M/ B% g5 ?6 ]
[color=rgba(0, 0, 0, 0.749019607843137)]128 c% i, k# Y M0 s: A0 k0 o
[color=rgba(0, 0, 0, 0.749019607843137)]13* {/ y% k! s4 g, ?( a
[color=rgba(0, 0, 0, 0.749019607843137)]14, Z' _+ K0 S" D# L2 c, |/ X
[color=rgba(0, 0, 0, 0.749019607843137)]2.4计算二叉树的高度
& }9 l; i) G/ r) S; t[color=rgba(0, 0, 0, 0.749019607843137)]int TreeHeight(BTNode* root)
: `- r/ h5 o7 J/ N& Y[color=rgba(0, 0, 0, 0.749019607843137)]{3 z: _! x5 r* Y2 C( B! |3 ~7 S
[color=rgba(0, 0, 0, 0.749019607843137)] //空树高度为0
( \, r" u& q( _4 ][color=rgba(0, 0, 0, 0.749019607843137)] if (root == NULL)
6 F* @4 u' W( }5 G7 l" N[color=rgba(0, 0, 0, 0.749019607843137)] {
2 e6 }, V* Q9 v[color=rgba(0, 0, 0, 0.749019607843137)] return 0;! K. W3 T! |* i0 l% y0 _$ w
[color=rgba(0, 0, 0, 0.749019607843137)] }
- o& ]8 n8 l" M3 t* V* g3 r7 q[color=rgba(0, 0, 0, 0.749019607843137)] //树的高度是较高的那棵子树
; F- K2 j W6 B/ L) ^[color=rgba(0, 0, 0, 0.749019607843137)] int lh = TreeHeight(root->left);//左子树的高度
& Y* C8 D/ A5 Z2 s( ^7 p4 O[color=rgba(0, 0, 0, 0.749019607843137)] int rh = TreeHeight(root->right);//右子树的高度
1 j7 V7 B9 f2 b9 o# ^6 B( B' i5 h5 N[color=rgba(0, 0, 0, 0.749019607843137)]6 v! h4 z- E/ X: X# r$ X
+ R) H8 I6 t; v* ^! t! A
[color=rgba(0, 0, 0, 0.749019607843137)] return lh > rh ? lh + 1 : rh + 1;
" D7 y$ { R$ r9 |! \( P7 i) C[color=rgba(0, 0, 0, 0.749019607843137)]}1 \# X. x8 L- X. L8 p4 H8 }' o" z# v
[color=rgba(0, 0, 0, 0.749019607843137)]1
9 t7 P- M2 b2 o1 O% E[color=rgba(0, 0, 0, 0.749019607843137)]2& w* _" W) |1 D( K9 M3 X* V
[color=rgba(0, 0, 0, 0.749019607843137)]3
# W! f$ ^/ ^: u) H {0 h' j2 @) |[color=rgba(0, 0, 0, 0.749019607843137)]4) \ w# b2 T( L0 Y; R6 l
[color=rgba(0, 0, 0, 0.749019607843137)]5
+ Q5 D% K0 e3 i" \2 y$ R" g8 t7 L% S[color=rgba(0, 0, 0, 0.749019607843137)]6 ^7 ?, u, O/ a5 H+ }! m! i. k m
[color=rgba(0, 0, 0, 0.749019607843137)]7; ]( r8 M' I8 @: D& E/ [3 Z% x
[color=rgba(0, 0, 0, 0.749019607843137)]8
5 ~0 k! x4 n# d* |7 m[color=rgba(0, 0, 0, 0.749019607843137)]9+ p2 |7 _- G7 v2 \9 P# _2 ~
[color=rgba(0, 0, 0, 0.749019607843137)]10
' ]' e* U$ l4 q6 r* P[color=rgba(0, 0, 0, 0.749019607843137)]11
" |# r0 d+ h. O[color=rgba(0, 0, 0, 0.749019607843137)]125 c6 p* v s3 d
[color=rgba(0, 0, 0, 0.749019607843137)]13
: W- f( W; j1 V, p[color=rgba(0, 0, 0, 0.749019607843137)]2.5计算第K层结点的个数
" `% f4 T/ y: j# f[color=rgba(0, 0, 0, 0.749019607843137)] y0 o. `9 c B3 x$ b
- o8 f# K: P7 j V5 \! ^0 b[color=rgba(0, 0, 0, 0.749019607843137)]
/ V/ [! e0 z, L; v7 ~
. ?7 k- I' X$ P( G$ \[color=rgba(0, 0, 0, 0.749019607843137)]求第K层的结点个数，转换成求子树第K-1层的结点个数。举个栗子：如果我们要求这棵二叉树第3层的结点个数（为3），就转换成求左子树根结点2的第2层的结点个数+右子树4第二层的结点个数。。。! _. {, U9 f; M) `* _0 ^' `& U
[color=rgba(0, 0, 0, 0.749019607843137)]' A4 _/ V) ^2 \! |5 Y
* r$ i6 N, A& q) j, F0 u/ o[color=rgba(0, 0, 0, 0.749019607843137)]//计算第K层结点的个数
; G0 C# \2 b7 x( S[color=rgba(0, 0, 0, 0.749019607843137)]int TreeLevel(BTNode* root,int K)& B( ]7 h. C1 w
[color=rgba(0, 0, 0, 0.749019607843137)]{: f2 R- w$ L+ O% X1 Q% B! |# z5 l
[color=rgba(0, 0, 0, 0.749019607843137)] assert(K > 0);
_) W8 s1 [" H# p4 r[color=rgba(0, 0, 0, 0.749019607843137)] if (root == NULL)* n& T* U, x& |# p f2 ^ H; S
[color=rgba(0, 0, 0, 0.749019607843137)] {
' ?/ [ d/ x7 P[color=rgba(0, 0, 0, 0.749019607843137)] return 0;. e2 { Y. @9 s9 v+ G8 U' Q& d
[color=rgba(0, 0, 0, 0.749019607843137)] }1 V$ `( l1 U3 z+ z: A) Y: E
[color=rgba(0, 0, 0, 0.749019607843137)] //如果是第一层(递归出口)
" s+ o9 S. r0 S# T3 F[color=rgba(0, 0, 0, 0.749019607843137)] if (K == 1)
0 J, ]* L+ u$ i0 a( S[color=rgba(0, 0, 0, 0.749019607843137)] {6 S* h% O4 A" u0 n: G; I' l
[color=rgba(0, 0, 0, 0.749019607843137)] return 1;' x: n, `5 F9 a5 }1 N
[color=rgba(0, 0, 0, 0.749019607843137)] }# e; u7 K; e8 Z6 h0 C$ i0 E" J
[color=rgba(0, 0, 0, 0.749019607843137)] //转换成子树的第K-1层& ~: h' T+ g! A- R+ h, s$ W! ?! Y
[color=rgba(0, 0, 0, 0.749019607843137)] return TreeLevel(root->left,K-1) + TreeLevel(root->right,K-1);+ q; ~! q* I3 U
[color=rgba(0, 0, 0, 0.749019607843137)]}( \$ s: e) r# z+ y; d6 A
[color=rgba(0, 0, 0, 0.749019607843137)]1" [. W! s1 u! w$ v& h2 p
[color=rgba(0, 0, 0, 0.749019607843137)]2
3 ~. g" ^) L0 Y) Y[color=rgba(0, 0, 0, 0.749019607843137)]3 w+ i5 b8 W" t) N; f& X# P
[color=rgba(0, 0, 0, 0.749019607843137)]4, d8 N- b( g: G' |
[color=rgba(0, 0, 0, 0.749019607843137)]5
: o# H/ d& R4 W[color=rgba(0, 0, 0, 0.749019607843137)]6! t% S( [& R) ]8 ]3 ~4 a
[color=rgba(0, 0, 0, 0.749019607843137)]7: }! \9 F- c; T
[color=rgba(0, 0, 0, 0.749019607843137)]86 [& H2 ?, p1 W/ d& s$ G5 j! d7 _
[color=rgba(0, 0, 0, 0.749019607843137)]9' g) S2 k, L; B( c5 y' B% F
[color=rgba(0, 0, 0, 0.749019607843137)]10
$ Q; F" \' ]( O- T[color=rgba(0, 0, 0, 0.749019607843137)]11. `& q1 R) z3 w) {5 _
[color=rgba(0, 0, 0, 0.749019607843137)]12- O1 w! r/ ]) _- o
[color=rgba(0, 0, 0, 0.749019607843137)]13
- R9 O9 j: Z& O; ^' k[color=rgba(0, 0, 0, 0.749019607843137)]14" I+ c1 u( v& i/ `, `9 G
[color=rgba(0, 0, 0, 0.749019607843137)]158 j' R0 @1 R# u/ v
[color=rgba(0, 0, 0, 0.749019607843137)]16
) Q0 a1 t; u+ K/ A9 i" f[color=rgba(0, 0, 0, 0.749019607843137)]2.6二叉树查找
0 }5 \$ V' d' Y" j! g[color=rgba(0, 0, 0, 0.749019607843137)]//二叉树查找5 _9 n. ?9 z/ Z0 L2 d
[color=rgba(0, 0, 0, 0.749019607843137)]BTNode* TreeFind(BTNode* root, BTDataType data)
2 u' v6 N8 G: |4 C7 q0 i" _) i0 A& s[color=rgba(0, 0, 0, 0.749019607843137)]{/ t. Q: d* E: s* n, a. O
[color=rgba(0, 0, 0, 0.749019607843137)] if (root == NULL)
1 a$ x2 \) Y0 t+ h[color=rgba(0, 0, 0, 0.749019607843137)] {
; n+ g( r5 c' u+ i. n[color=rgba(0, 0, 0, 0.749019607843137)] return NULL;
5 H) Y4 u0 d$ U/ L- b; s2 \9 F[color=rgba(0, 0, 0, 0.749019607843137)] }
- N( P g: U/ c! U+ m- C$ e[color=rgba(0, 0, 0, 0.749019607843137)] if (root->data == data)
% m) A% Q9 b7 [[color=rgba(0, 0, 0, 0.749019607843137)] {
5 A3 s' j0 n2 S' K x[color=rgba(0, 0, 0, 0.749019607843137)] return root;
1 W2 I* d& i: h- ~0 \[color=rgba(0, 0, 0, 0.749019607843137)] }- D, t3 b g# z
[color=rgba(0, 0, 0, 0.749019607843137)] //先查找左子树
' F4 u( c5 |/ Z& f, n: F) v[color=rgba(0, 0, 0, 0.749019607843137)] BTNode* lret = TreeFind(root->left, data);
& t9 L6 ^! N* s% l# e7 N[color=rgba(0, 0, 0, 0.749019607843137)] if (lret)5 |2 f, f8 H Y* `. J
[color=rgba(0, 0, 0, 0.749019607843137)] return lret;8 a# {: L I2 G( K. e! L9 X
[color=rgba(0, 0, 0, 0.749019607843137)] //再查找右子树+ |/ D4 e) A, c% k+ g
[color=rgba(0, 0, 0, 0.749019607843137)] BTNode* rret = TreeFind(root->right, data);
! F9 A5 m: ?- F5 I. l% U2 K[color=rgba(0, 0, 0, 0.749019607843137)] if (rret)$ k/ ?# `9 G0 G0 q
[color=rgba(0, 0, 0, 0.749019607843137)] return rret;
) Y8 G8 e- p4 I" \' y9 w" y[color=rgba(0, 0, 0, 0.749019607843137)] return NULL;+ k2 X) }1 a4 t4 P$ S* o8 N2 P
[color=rgba(0, 0, 0, 0.749019607843137)]}4 l' r! ?5 W% B' m/ c
[color=rgba(0, 0, 0, 0.749019607843137)]————————————————& ^" ]4 B' C) h% h* k" `/ K
[color=rgba(0, 0, 0, 0.749019607843137)]版权声明：本文为CSDN博主「SouLinya」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
$ `# e/ e: _) f- B Q6 O2 l[color=rgba(0, 0, 0, 0.749019607843137)]原文链接：https://blog.csdn.net/weixin_63449996/article/details/1268412120 Z3 l4 t4 X- Z! L
9 i- l1 q0 g2 ?- O1 H$ Q( H$ W- {3 f7 d
[color=rgba(0, 0, 0, 0.75)]
. c1 f2 p. e# k: w9 e
6 ^' z4 r) g$ J; ~' n) o4 c
- g8 H" d& A- F- \' X2 ] s8 L* L8 j5 Q5 B# C7 A4 C2 [- _
|
IP卡
狗仔卡
发表于 2022-9-15 11:55
转播
淘帖
分享
收藏
支持
反对
微信
提升卡
置顶卡
沉默卡
喧嚣卡
变色卡
抢沙发
显身卡
