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