【数据结构】二叉树的遍历：前序，中序，后序的递归结构遍历
/ j! U, E9 M. t0 K: p, E; x4 G8 b9 f l5 e- E, Z% e/ R
[color=rgba(0, 0, 0, 0.749019607843137)]文章目录
, _( L: d1 E% p( b[color=rgba(0, 0, 0, 0.749019607843137)]前言2 V8 R3 h0 s5 V& a# S; a' t
[color=rgba(0, 0, 0, 0.749019607843137)]1.二叉树的遍历方式
/ |0 p; Q( H( \' t* e' d[color=rgba(0, 0, 0, 0.749019607843137)]2.二叉树的遍历及相关函数（代码实现）
) i" L$ a- h9 H: H* ^; D[color=rgba(0, 0, 0, 0.749019607843137)]2.1前序/中序/后序的遍历) {& D% [2 v5 P$ R9 l
[color=rgba(0, 0, 0, 0.749019607843137)]2.2计算二叉树的大小0 {4 D* C) }% ~2 _) v" \
[color=rgba(0, 0, 0, 0.749019607843137)]2.3计算二叉树叶子结点的个数
& ~4 B8 z8 _; i. f4 n& S[color=rgba(0, 0, 0, 0.749019607843137)]2.4计算二叉树的高度
8 E V& b; T$ a/ E) L[color=rgba(0, 0, 0, 0.749019607843137)]2.5计算第K层结点的个数; b1 f: B- V2 }, U! p" I$ `+ P% F
[color=rgba(0, 0, 0, 0.749019607843137)]2.6二叉树查找
( {# r- D M7 l2 G[color=rgba(0, 0, 0, 0.749019607843137)]前言
- j7 k ]9 g k4 ]( H( t' t[color=rgba(0, 0, 0, 0.749019607843137)]在学习二叉树的遍历之前，我们需要先创建一棵二叉树，然后才能学习其相关的基本操作，由于现在我们对二叉树结构的掌握还在初阶部分，为了降低大家的学习成本，我们先手动快速创建一棵简单的二叉树，快速进入二叉树的操作学习，这个方法在我们调试程序代码的时候，也非常适用。等二叉树结构了解的差不多时，我们再继续研究二叉树真正的创建方式。
2 i% p l4 q( J: w$ ~[color=rgba(0, 0, 0, 0.749019607843137)]) ]6 s l! f. m6 z5 G/ }& T; F. N
2 q- |! F; I% R5 D$ M' {[color=rgba(0, 0, 0, 0.749019607843137)]1.二叉树的遍历方式
7 |# @" G; Q( @ p[color=rgba(0, 0, 0, 0.749019607843137)]% e+ r+ L8 {# @ _$ K
4 m5 h5 t. {( F5 {
[color=rgba(0, 0, 0, 0.749019607843137)]按照规则，二叉树的遍历有：前序/中序/后序的递归结构遍历访问顺序：! S) w1 d2 k# l
[color=rgba(0, 0, 0, 0.749019607843137)]3 q+ T; S3 B) E6 d7 J% M* o
# k% N8 \; C7 D3 ~/ u. Q
[color=rgba(0, 0, 0, 0.749019607843137)]1. 前序遍历（先序，先根):根——左子树——右子树' [3 `1 T. c2 G [3 M
[color=rgba(0, 0, 0, 0.749019607843137)]
" H8 L, q7 E, w" n4 T+ d- d/ L
8 ~: z7 A( {) L4 t8 S _5 K[color=rgba(0, 0, 0, 0.749019607843137)]
) W! h, Q4 `0 |- Z* ^8 N- \2 r$ D6 [
[color=rgba(0, 0, 0, 0.749019607843137)]2. 中序遍历（中根）：左子树——根——右子树( Q* B! y' A0 d1 ?7 `
[color=rgba(0, 0, 0, 0.749019607843137)]
! A( n) e% S! ~* w. y3 `) x Q# d3 H5 j; Y
[color=rgba(0, 0, 0, 0.749019607843137)]4 @1 p, S8 `- Y) M& M7 a
3 b0 [' \4 U0 Z4 P! k) {9 t1 b
[color=rgba(0, 0, 0, 0.749019607843137)]3. 后序遍历（后根）：左子树——右子树——根
~- l; l$ X- f* ?, v7 q# ^* ^[color=rgba(0, 0, 0, 0.749019607843137)]: X8 N+ W* C: R) H3 w4 J3 B
2 K$ R" y8 s6 m$ G) D3 c' i
[color=rgba(0, 0, 0, 0.749019607843137)]
; d/ {$ A0 X3 ^/ [( g* B7 e* |" h ?; _7 X9 }7 u0 Z S) U
[color=rgba(0, 0, 0, 0.749019607843137)]2.二叉树的遍历及相关函数（代码实现）7 {: q9 v+ @6 l# S
[color=rgba(0, 0, 0, 0.749019607843137)]思路：分而治之* g+ N* F9 F$ Y9 I0 I8 P9 B
[color=rgba(0, 0, 0, 0.749019607843137)]1.首先我们要用简单的方式先创建出一棵二叉树，并赋予数据；$ P9 r) }8 s9 o3 a' _1 I" }) d, q
[color=rgba(0, 0, 0, 0.749019607843137)]2.采用递归的方式，分别实现前序/中序/后序遍历这棵二叉树；
" s7 a$ ~) z- c[color=rgba(0, 0, 0, 0.749019607843137)]3.尝试计算这个二叉树的大小（利用递归）；
# D4 j/ r* M @7 l7 ][color=rgba(0, 0, 0, 0.749019607843137)]4.尝试计算叶子结点的个数（利用递归）；, [. Q* b; {5 s; L& m( A* K
[color=rgba(0, 0, 0, 0.749019607843137)]5.尝试计算二叉树的高度（利用递归）；
* F$ n5 ]4 g- ]7 x& D2 ^) i3 h& P[color=rgba(0, 0, 0, 0.749019607843137)]6.尝试写出计算第K层结点的个数的函数（利用递归）；
# P- G2 Z; E- U( a5 v' U% P[color=rgba(0, 0, 0, 0.749019607843137)]7.尝试写出二叉树查找的函数（利用递归）。' i/ a# {7 v% x! ]) ?
[color=rgba(0, 0, 0, 0.749019607843137)]
) s8 p8 Z Z r. W! Y9 T- j5 @* Z4 s8 @
[color=rgba(0, 0, 0, 0.749019607843137)]2.1前序/中序/后序的遍历" U" f+ O! [4 h+ ^9 E- q
[color=rgba(0, 0, 0, 0.749019607843137)]#define _CRT_SECURE_NO_WARNINGS 14 t3 s9 ^' R+ d0 v
[color=rgba(0, 0, 0, 0.749019607843137)]#include<stdio.h>$ u/ s/ R6 W" b7 D' `0 j
[color=rgba(0, 0, 0, 0.749019607843137)]#include<assert.h>
8 X; H1 @4 [. Z% }[color=rgba(0, 0, 0, 0.749019607843137)]#include<stdlib.h>1 W9 e: C8 E/ S2 V
[color=rgba(0, 0, 0, 0.749019607843137)]
- S. n: W0 j% O
: }. R4 V4 G3 B. F! c p' S[color=rgba(0, 0, 0, 0.749019607843137)]typedef int BTDataType;
, l* T$ o" h; t4 @[color=rgba(0, 0, 0, 0.749019607843137)]' x& i }; |' Z# ]* H# F
1 S& W$ y7 {' ~3 Q9 f" G
[color=rgba(0, 0, 0, 0.749019607843137)]//定义二叉树结点的结构体- o1 I* Q$ D9 c/ L4 ?6 e6 @4 Z
[color=rgba(0, 0, 0, 0.749019607843137)]typedef struct BinaryTreeNode T. I' ~/ I# \! C" K- r
[color=rgba(0, 0, 0, 0.749019607843137)]{2 o w; S) X o) t* w# T0 v
[color=rgba(0, 0, 0, 0.749019607843137)] BTDataType data;
/ G3 R, b9 _7 P( V ` d% h[color=rgba(0, 0, 0, 0.749019607843137)] struct BinaryTreeNode* left;9 L3 [* d: C& n
[color=rgba(0, 0, 0, 0.749019607843137)] struct BinaryTreeNode* right;* J0 }* N- f; W# i/ Q/ }% [
[color=rgba(0, 0, 0, 0.749019607843137)]}BTNode;0 M) ?5 P: N, P2 M; ^. J3 U) {
[color=rgba(0, 0, 0, 0.749019607843137)]+ b! h+ z5 M0 z8 [" _
: m0 b& { H; D& T( q* c
[color=rgba(0, 0, 0, 0.749019607843137)]//前序遍历
5 b( T6 q: p# w5 u: k1 i[color=rgba(0, 0, 0, 0.749019607843137)]void PreOrder(BTNode* root)6 K( L4 w/ @( \5 ]% C# O
[color=rgba(0, 0, 0, 0.749019607843137)]{
& v3 N8 K4 k9 E[color=rgba(0, 0, 0, 0.749019607843137)] if (root == NULL)! |6 V' O$ z5 q0 ~; r9 `" @# O Z
[color=rgba(0, 0, 0, 0.749019607843137)] {2 }6 \+ o+ \6 }
[color=rgba(0, 0, 0, 0.749019607843137)] printf("NULL ");
: s4 t: d6 P" F& {# B/ A[color=rgba(0, 0, 0, 0.749019607843137)] return;
7 Z8 ^4 z6 i4 H/ z, [: m. o[color=rgba(0, 0, 0, 0.749019607843137)] }
2 Z3 w# x3 D" `( |: u[color=rgba(0, 0, 0, 0.749019607843137)] printf("%d ", root->data);
: S* r5 k9 t) } l2 A[color=rgba(0, 0, 0, 0.749019607843137)] PreOrder(root->left);
7 Y2 j u2 [% _- u+ R( q. z% d[color=rgba(0, 0, 0, 0.749019607843137)] PreOrder(root->right);: x, W8 j- [# [& d" i
[color=rgba(0, 0, 0, 0.749019607843137)]}' r& @5 j( K7 E& f; H9 \$ U
[color=rgba(0, 0, 0, 0.749019607843137)]//中序遍历5 L6 O' `4 x5 d9 |. u
[color=rgba(0, 0, 0, 0.749019607843137)]void InOrder(BTNode* root)- w! k8 u5 M3 k. g
[color=rgba(0, 0, 0, 0.749019607843137)]{
" [! x/ R2 w* C: y" Q5 `# q8 ?[color=rgba(0, 0, 0, 0.749019607843137)] if (root == NULL)
, O+ O4 B! G+ K[color=rgba(0, 0, 0, 0.749019607843137)] {
! O' g% L5 [. b5 U- C+ }[color=rgba(0, 0, 0, 0.749019607843137)] printf("NULL ");
6 O& _' ^5 G+ [7 i[color=rgba(0, 0, 0, 0.749019607843137)] return;1 O: b/ G% ]& U8 c( W7 j# ?5 }
[color=rgba(0, 0, 0, 0.749019607843137)] }
: x5 V" T2 U9 }2 Z- h[color=rgba(0, 0, 0, 0.749019607843137)] InOrder(root->left);
' k6 v4 P9 z: _6 W& y/ L[color=rgba(0, 0, 0, 0.749019607843137)] printf("%d ", root->data);, |0 q) N: e8 n2 R, l' _7 N
[color=rgba(0, 0, 0, 0.749019607843137)] InOrder(root->right);" w" H) A. I& x& h6 W
[color=rgba(0, 0, 0, 0.749019607843137)]}
; y" `7 F3 r8 T. W$ R9 P' o- v[color=rgba(0, 0, 0, 0.749019607843137)]//后序遍历
6 j: j$ {) \ A6 |/ w3 F[color=rgba(0, 0, 0, 0.749019607843137)]void PostOrder(BTNode* root) j% a/ z: N4 @
[color=rgba(0, 0, 0, 0.749019607843137)]{
6 R( ?; p+ g5 p9 t4 x[color=rgba(0, 0, 0, 0.749019607843137)] if (root == NULL)
( ~8 W! l1 g- W[color=rgba(0, 0, 0, 0.749019607843137)] {% h& c% c7 o5 @1 _
[color=rgba(0, 0, 0, 0.749019607843137)] printf("NULL ");
/ P8 t n/ F- |( L$ G+ Z1 s[color=rgba(0, 0, 0, 0.749019607843137)] return;' J$ k+ ]* G0 U. J
[color=rgba(0, 0, 0, 0.749019607843137)] }' b n' S& ^& b2 R5 {5 g: V, `
[color=rgba(0, 0, 0, 0.749019607843137)] PostOrder(root->left);
: L6 d3 M% u% a[color=rgba(0, 0, 0, 0.749019607843137)] PostOrder(root->right);
2 `5 p+ t, x- _[color=rgba(0, 0, 0, 0.749019607843137)] printf("%d ", root->data);
" c8 ]5 x5 Y/ a9 Y0 q[color=rgba(0, 0, 0, 0.749019607843137)]}. C3 Y6 ^6 ?. |! R' `" Z, Y
[color=rgba(0, 0, 0, 0.749019607843137)]//先创建一个简单的二叉树结构' H8 p$ t9 e# L! H! b8 y
[color=rgba(0, 0, 0, 0.749019607843137)]BTNode* CreateTree()6 d* c' f, G; _" f& d4 X& q
[color=rgba(0, 0, 0, 0.749019607843137)]{0 T( E4 _% i4 A) u
[color=rgba(0, 0, 0, 0.749019607843137)] //先动态开辟6个结点的空间+ Y5 a& W' W ? }
[color=rgba(0, 0, 0, 0.749019607843137)] BTNode* n1 = (BTNode*)malloc(sizeof(BTNode));% g- K0 u( n. h' B3 n
[color=rgba(0, 0, 0, 0.749019607843137)] assert(n1);
6 j2 O& z, c. _[color=rgba(0, 0, 0, 0.749019607843137)] BTNode* n2 = (BTNode*)malloc(sizeof(BTNode));8 A7 Y; {9 W, h2 N# H* x
[color=rgba(0, 0, 0, 0.749019607843137)] assert(n2);, A* n% K. ~( x5 {0 W6 i) g$ @- l% ?1 [
[color=rgba(0, 0, 0, 0.749019607843137)] BTNode* n3 = (BTNode*)malloc(sizeof(BTNode));2 `/ k; a1 Q u' Q
[color=rgba(0, 0, 0, 0.749019607843137)] assert(n3);
! V- |& w. r; y( ~/ Z[color=rgba(0, 0, 0, 0.749019607843137)] BTNode* n4 = (BTNode*)malloc(sizeof(BTNode));4 ~. {$ @2 J$ T, Y! T8 k
[color=rgba(0, 0, 0, 0.749019607843137)] assert(n4);
9 L& J0 C2 _; a3 F) z7 ~[color=rgba(0, 0, 0, 0.749019607843137)] BTNode* n5 = (BTNode*)malloc(sizeof(BTNode));
0 b; x9 T7 _- J1 _/ R[color=rgba(0, 0, 0, 0.749019607843137)] assert(n5);# y. ~+ N0 M5 k6 v4 N- o, m5 Z* _; t
[color=rgba(0, 0, 0, 0.749019607843137)] BTNode* n6 = (BTNode*)malloc(sizeof(BTNode));0 \: v7 d7 p4 N2 j8 l
[color=rgba(0, 0, 0, 0.749019607843137)] assert(n6);! A4 c$ C- V6 c8 G Y; w# J6 F6 F
[color=rgba(0, 0, 0, 0.749019607843137)], m) _$ c" {3 k
0 n* ]' q/ N8 @4 p[color=rgba(0, 0, 0, 0.749019607843137)] n1->data = 1;
) [. e* `7 y) O8 Y& \[color=rgba(0, 0, 0, 0.749019607843137)] n2->data = 2;( a; v6 @: f& i5 e N
[color=rgba(0, 0, 0, 0.749019607843137)] n3->data = 3;
% y$ U- @2 w) [) {) G8 A[color=rgba(0, 0, 0, 0.749019607843137)] n4->data = 4;
. n V P! |( x/ U. W8 W3 P* n6 m[color=rgba(0, 0, 0, 0.749019607843137)] n5->data = 5;
# g- w9 @; Z8 D! |/ i Z[color=rgba(0, 0, 0, 0.749019607843137)] n6->data = 6;
& n& j5 n( H; n6 z+ B9 T/ y[color=rgba(0, 0, 0, 0.749019607843137)]
' a2 J& X, A* M- k" |, E
- D a" i R q0 K( I9 G4 ~[color=rgba(0, 0, 0, 0.749019607843137)] n1->left = n2;* \( R; n! W8 Q M9 l
[color=rgba(0, 0, 0, 0.749019607843137)] n1->right = n4;
: p+ z: g6 V9 T" E0 H! T[color=rgba(0, 0, 0, 0.749019607843137)] n2->left = n3;
+ x7 J6 s' {% _7 ^- t) n* {* \[color=rgba(0, 0, 0, 0.749019607843137)] n2->right = NULL;6 a% T! l+ [3 Y1 q3 ]
[color=rgba(0, 0, 0, 0.749019607843137)] n3->left = NULL;3 k" o" [: p7 V5 Y2 _3 | y
[color=rgba(0, 0, 0, 0.749019607843137)] n3->right = NULL;
8 Y, O6 ?6 Z) Y' p3 w[color=rgba(0, 0, 0, 0.749019607843137)] n4->left = n5;
6 K! S# b. Z* w+ K* I[color=rgba(0, 0, 0, 0.749019607843137)] n4->right = n6;
- \7 Y2 m# [2 o2 T+ c4 n[color=rgba(0, 0, 0, 0.749019607843137)] n5->left = NULL;- c2 f$ s1 D# v/ A6 P
[color=rgba(0, 0, 0, 0.749019607843137)] n5->right = NULL;
$ e: \+ ` R, Q" ~3 c/ F$ x[color=rgba(0, 0, 0, 0.749019607843137)] n6->left = NULL;( z) b6 [# ?& y) V) u7 _1 e% o
[color=rgba(0, 0, 0, 0.749019607843137)] n6->right = NULL;1 f6 m* e4 a- C1 [
[color=rgba(0, 0, 0, 0.749019607843137)]0 Y F2 Y* h$ f; U, I" H+ w4 u
# X7 P, e0 i5 u& B7 N
[color=rgba(0, 0, 0, 0.749019607843137)] return n1;& v) f! v1 @/ ]* a' @
[color=rgba(0, 0, 0, 0.749019607843137)]}
5 h, p! G( v% [/ x- F9 A5 `[color=rgba(0, 0, 0, 0.749019607843137)]
7 ?' v" _$ e- p3 I( x$ d! x! A( h5 h% j5 h, }' x% `
[color=rgba(0, 0, 0, 0.749019607843137)]int main()7 t$ H- E; e4 Q% r: m
[color=rgba(0, 0, 0, 0.749019607843137)]{" W6 c. {' b" l |+ t) V4 i. L$ @
[color=rgba(0, 0, 0, 0.749019607843137)] //先创建一个简单的二叉树结构
9 q7 }& r, `# k8 g3 r1 o" a2 e1 x[color=rgba(0, 0, 0, 0.749019607843137)] BTNode* root = CreateTree();5 r! m; Q7 R7 Q
[color=rgba(0, 0, 0, 0.749019607843137)]% C6 |+ N. q/ |+ m3 \4 U# ]
3 b/ l. G, _3 d' F8 h
[color=rgba(0, 0, 0, 0.749019607843137)] //二叉树前序遍历/ m5 a- o5 I% T8 }* s7 {5 ~2 |2 y+ s
[color=rgba(0, 0, 0, 0.749019607843137)] printf("二叉树前序遍历:");
7 {& B% c8 k- m: |[color=rgba(0, 0, 0, 0.749019607843137)] PreOrder(root);
! ^0 z3 E m1 {% ^& u) f! [[color=rgba(0, 0, 0, 0.749019607843137)] printf("\n");
" S: Q {& D4 m, c6 V[color=rgba(0, 0, 0, 0.749019607843137)] //二叉树中序遍历) X$ o( z7 t' i" n
[color=rgba(0, 0, 0, 0.749019607843137)] printf("二叉树中序序遍历:");
$ `& M0 z* o/ |+ H7 j[color=rgba(0, 0, 0, 0.749019607843137)] InOrder(root);- n! | Y. o: g" X
[color=rgba(0, 0, 0, 0.749019607843137)] printf("\n");% l1 `. m6 m0 a2 n, c5 D3 k
[color=rgba(0, 0, 0, 0.749019607843137)] //二叉树后序遍历
8 V9 |: x. X! L' R) u[color=rgba(0, 0, 0, 0.749019607843137)] printf("二叉树后序遍历:");
: ^, X: g: m$ C! b, V[color=rgba(0, 0, 0, 0.749019607843137)] PostOrder(root);
. w5 L% x, @2 w+ h4 t- E( o4 F7 {[color=rgba(0, 0, 0, 0.749019607843137)] printf("\n");; ~6 Y9 Y3 G/ P7 ]
[color=rgba(0, 0, 0, 0.749019607843137)]( I( ^. a; O; j! Y. |; V1 ^& H' A% W b) D+ B
: d D! N( D! _8 _9 R[color=rgba(0, 0, 0, 0.749019607843137)] return 0;# }/ i: |& x2 a+ @3 }) Z
[color=rgba(0, 0, 0, 0.749019607843137)]}
3 a% ^- D: i1 M" o D, M1 \+ E[color=rgba(0, 0, 0, 0.749019607843137)]1
2 _ M6 C3 [ J[color=rgba(0, 0, 0, 0.749019607843137)]2
- R# P/ E* e/ H; B1 W[color=rgba(0, 0, 0, 0.749019607843137)]3
4 n) z b6 o, ]% d8 E8 f r: ]8 w. ]& R[color=rgba(0, 0, 0, 0.749019607843137)]4
; c6 e) l( p9 F4 Q: U- M[color=rgba(0, 0, 0, 0.749019607843137)]5( m: l- h8 Q2 b' \, `. k9 {
[color=rgba(0, 0, 0, 0.749019607843137)]62 [, K: ^+ ^+ G1 y/ T$ C
[color=rgba(0, 0, 0, 0.749019607843137)]7
, {* B, }! D8 }- \ [- Z3 G) H& c[color=rgba(0, 0, 0, 0.749019607843137)]8
! O' O, y [8 W# F7 B[color=rgba(0, 0, 0, 0.749019607843137)]9/ Z$ Z6 ?! h+ I
[color=rgba(0, 0, 0, 0.749019607843137)]10
5 x h9 A' U8 F# e( E[color=rgba(0, 0, 0, 0.749019607843137)]11
! F% z" U, @- L[color=rgba(0, 0, 0, 0.749019607843137)]12
, U6 N: C r/ g[color=rgba(0, 0, 0, 0.749019607843137)]13
+ j4 {' J; Y4 ]7 e; W[color=rgba(0, 0, 0, 0.749019607843137)]14* _, c- \ A3 K& X3 g! m
[color=rgba(0, 0, 0, 0.749019607843137)]15! ]3 g% `% J- V+ F/ K# [- n- F, ?
[color=rgba(0, 0, 0, 0.749019607843137)]164 |, b) I0 s# P4 U+ ~. j8 y# H, M
[color=rgba(0, 0, 0, 0.749019607843137)]178 ^0 O- B$ g8 P* ]
[color=rgba(0, 0, 0, 0.749019607843137)]18
# r# M9 d5 G+ v- C8 j[color=rgba(0, 0, 0, 0.749019607843137)]19/ w& r8 `( _; }; E6 W3 t- w0 o
[color=rgba(0, 0, 0, 0.749019607843137)]20 G w. C9 k% C/ N
[color=rgba(0, 0, 0, 0.749019607843137)]21
: s! t1 d( A. x& B3 S2 n[color=rgba(0, 0, 0, 0.749019607843137)]226 ?4 {* d% S6 M6 L- \
[color=rgba(0, 0, 0, 0.749019607843137)]239 ?: F0 k M- L9 F. b& B& t
[color=rgba(0, 0, 0, 0.749019607843137)]24' ~# y* {( q# }+ ~1 ~* L3 | A( r
[color=rgba(0, 0, 0, 0.749019607843137)]259 O* I7 m+ p5 E2 \
[color=rgba(0, 0, 0, 0.749019607843137)]26, A! D/ P5 D: p0 d. G
[color=rgba(0, 0, 0, 0.749019607843137)]27! a% J1 _! H7 q, h8 ?5 N# Y& J/ R Y
[color=rgba(0, 0, 0, 0.749019607843137)]28
7 p7 A* C/ ?6 l: F[color=rgba(0, 0, 0, 0.749019607843137)]298 l/ G) g8 {( l/ p. \8 x
[color=rgba(0, 0, 0, 0.749019607843137)]30 k& X: {% P; c! ?+ ?
[color=rgba(0, 0, 0, 0.749019607843137)]31
# k b7 F; P) A7 f! ^( E[color=rgba(0, 0, 0, 0.749019607843137)]32" P' n U( ^ r) ~
[color=rgba(0, 0, 0, 0.749019607843137)]33
. z8 _& D+ }5 m% E[color=rgba(0, 0, 0, 0.749019607843137)]34
- L( E1 F& S. T8 s1 m[color=rgba(0, 0, 0, 0.749019607843137)]35
% R0 G5 S. ^, h7 g) S" C[color=rgba(0, 0, 0, 0.749019607843137)]36% f7 d8 i) a" E) |# x0 M
[color=rgba(0, 0, 0, 0.749019607843137)]37; M0 Q; s% p7 Y/ Q0 d8 l0 c3 v& S+ O
[color=rgba(0, 0, 0, 0.749019607843137)]389 g1 w/ s5 u2 z5 x l' w8 }$ r7 f
[color=rgba(0, 0, 0, 0.749019607843137)]39
B; F$ j2 q5 Z[color=rgba(0, 0, 0, 0.749019607843137)]40
" k1 Q! V% p9 `) M9 J' i[color=rgba(0, 0, 0, 0.749019607843137)]412 E0 s; ^/ W4 K. d( f- C
[color=rgba(0, 0, 0, 0.749019607843137)]42
! A: z6 T- a) ?- X# T4 F, ~[color=rgba(0, 0, 0, 0.749019607843137)]43- O( y4 t1 F8 ^1 q8 Y; L' M
[color=rgba(0, 0, 0, 0.749019607843137)]443 L2 k/ ?7 K+ O& y! M5 F9 X$ h
[color=rgba(0, 0, 0, 0.749019607843137)]45
4 f7 M# o7 q; ~0 `[color=rgba(0, 0, 0, 0.749019607843137)]46
0 Q( u$ z1 {9 `9 X9 Z[color=rgba(0, 0, 0, 0.749019607843137)]47
9 |& ?, s6 B" Z. h% W[color=rgba(0, 0, 0, 0.749019607843137)]487 _4 y! B! j0 D
[color=rgba(0, 0, 0, 0.749019607843137)]49/ F2 r# u5 t" D- _
[color=rgba(0, 0, 0, 0.749019607843137)]50
4 J) A6 Z7 U3 T" }$ S[color=rgba(0, 0, 0, 0.749019607843137)]512 O5 K- j! A$ \+ y; k! W6 H) \
[color=rgba(0, 0, 0, 0.749019607843137)]52
9 a7 M0 n8 K! I- a[color=rgba(0, 0, 0, 0.749019607843137)]539 D a6 L. l9 y
[color=rgba(0, 0, 0, 0.749019607843137)]54
; P4 u6 P' r& ]: j& Z# u2 d, w' V[color=rgba(0, 0, 0, 0.749019607843137)]55
- G! e8 h. r/ V, P! S8 h[color=rgba(0, 0, 0, 0.749019607843137)]56
# I ~6 @! q3 a& r1 V: D; V[color=rgba(0, 0, 0, 0.749019607843137)]57
1 Y6 J* k s1 y8 H3 s: m[color=rgba(0, 0, 0, 0.749019607843137)]58
* [1 b& H) W4 T5 ~. e5 a( C0 V[color=rgba(0, 0, 0, 0.749019607843137)]59; M% v# ^8 m8 c; U1 c s, p
[color=rgba(0, 0, 0, 0.749019607843137)]60
; O+ h3 d/ M, Z0 X6 r- N[color=rgba(0, 0, 0, 0.749019607843137)]61
$ t/ `* ]- s* v) u& f1 ~[color=rgba(0, 0, 0, 0.749019607843137)]621 e; Z e3 V% j: r: V h
[color=rgba(0, 0, 0, 0.749019607843137)]63( \) Z% p9 W- H# q5 ]
[color=rgba(0, 0, 0, 0.749019607843137)]64
' h6 J% K: y. i& B- l* ]9 o4 ][color=rgba(0, 0, 0, 0.749019607843137)]65* C6 J) M* D! U: C
[color=rgba(0, 0, 0, 0.749019607843137)]66
5 z) k" s; l' q# w. Q# ][color=rgba(0, 0, 0, 0.749019607843137)]67/ v; y- D0 m' ?3 W& V
[color=rgba(0, 0, 0, 0.749019607843137)]68
! H& m# N; n# v3 e4 J4 f0 j- {- c( o[color=rgba(0, 0, 0, 0.749019607843137)]69
& o" N& C9 g, c) S: z4 @2 S; Z0 F[color=rgba(0, 0, 0, 0.749019607843137)]70
, R( ]! }. }, `, R% c: `9 o& R: f[color=rgba(0, 0, 0, 0.749019607843137)]710 S2 f4 x- `7 J* b7 i/ L
[color=rgba(0, 0, 0, 0.749019607843137)]72: t) R' ^, x. Z! G( V# J% j- k
[color=rgba(0, 0, 0, 0.749019607843137)]732 w D$ G5 ?2 e+ v
[color=rgba(0, 0, 0, 0.749019607843137)]74
, l5 ~5 j. \% a9 H[color=rgba(0, 0, 0, 0.749019607843137)]75
# z5 t$ f: @5 |; C! w[color=rgba(0, 0, 0, 0.749019607843137)]763 D u8 S3 S6 W, X7 \0 e& D
[color=rgba(0, 0, 0, 0.749019607843137)]776 q- @/ ~+ K. }4 q5 W( X
[color=rgba(0, 0, 0, 0.749019607843137)]784 f7 W* a7 F g" }
[color=rgba(0, 0, 0, 0.749019607843137)]79/ e3 E4 a+ r6 p
[color=rgba(0, 0, 0, 0.749019607843137)]80# q" T4 o! o8 H2 ~! S9 d
[color=rgba(0, 0, 0, 0.749019607843137)]81
& p& g# z/ V: L9 k4 N' K) i[color=rgba(0, 0, 0, 0.749019607843137)]82
- A' r: s3 U* r$ S[color=rgba(0, 0, 0, 0.749019607843137)]83) \ p1 t4 @5 g- T; X7 L
[color=rgba(0, 0, 0, 0.749019607843137)]84% n# |1 V8 x5 G
[color=rgba(0, 0, 0, 0.749019607843137)]85" _# H7 z! G; O# M. P7 }: K5 v
[color=rgba(0, 0, 0, 0.749019607843137)]86
3 b6 W% x, Y1 [: ?" V[color=rgba(0, 0, 0, 0.749019607843137)]87( Y/ F4 P3 t8 Y# M
[color=rgba(0, 0, 0, 0.749019607843137)]88
# ~( ~) s! c- R, ^( O) h* \[color=rgba(0, 0, 0, 0.749019607843137)]89
0 R" P7 b: i( T& M% a[color=rgba(0, 0, 0, 0.749019607843137)]90
: K u! F+ Y6 ]0 Y4 w[color=rgba(0, 0, 0, 0.749019607843137)]91
( u1 [0 m8 |' t- e5 ?[color=rgba(0, 0, 0, 0.749019607843137)]92 M$ K3 r7 G' D2 I; M1 c1 u
[color=rgba(0, 0, 0, 0.749019607843137)]93: k+ P- B6 O& e; Z
[color=rgba(0, 0, 0, 0.749019607843137)]94, C6 X" c5 f* b8 _% B
[color=rgba(0, 0, 0, 0.749019607843137)]95
, x+ }# q/ ^) F+ ^8 x[color=rgba(0, 0, 0, 0.749019607843137)]96# F* u; \( J0 |0 ~: F9 X1 h
[color=rgba(0, 0, 0, 0.749019607843137)]979 G/ F( q( Z6 M5 A, y; l
[color=rgba(0, 0, 0, 0.749019607843137)]987 g& P6 T4 p; o! C6 W
[color=rgba(0, 0, 0, 0.749019607843137)]99$ d- X" u9 Y- j e
[color=rgba(0, 0, 0, 0.749019607843137)]100
+ R I5 B) \" t/ n2 z3 v[color=rgba(0, 0, 0, 0.749019607843137)]101- @, K# Q( [% V \& W9 l! B
[color=rgba(0, 0, 0, 0.749019607843137)]102
& `4 Q* x. v# X9 O, s( p0 ?+ z& p: T[color=rgba(0, 0, 0, 0.749019607843137)]103
3 _4 M+ ]. w/ D) ^4 w7 d) y5 h; z[color=rgba(0, 0, 0, 0.749019607843137)]1049 e( j% |6 O( O' s5 X3 Y7 v: ^
[color=rgba(0, 0, 0, 0.749019607843137)]105
* u6 h2 I9 U% _& C0 T9 A6 D[color=rgba(0, 0, 0, 0.749019607843137)]1061 D D* ]% o2 x3 F# ~1 n! v! E
[color=rgba(0, 0, 0, 0.749019607843137)]1070 `. C) U& \: p9 E
[color=rgba(0, 0, 0, 0.749019607843137)]108
/ Y& J- k, ^% ]/ r5 N. k[color=rgba(0, 0, 0, 0.749019607843137)]109
! w# j3 [. x ]- ][color=rgba(0, 0, 0, 0.749019607843137)]110
% h+ f" Q* ^6 a2 V4 h[color=rgba(0, 0, 0, 0.749019607843137)]1114 D' k) _2 O2 v) n; i8 o
[color=rgba(0, 0, 0, 0.749019607843137)]测试结果：
0 M; C. Q( @' R+ r[color=rgba(0, 0, 0, 0.749019607843137)]
# m2 ]- J$ F* c' T. B& i# |' o v1 [2 [; R5 N; L. v
[color=rgba(0, 0, 0, 0.749019607843137)]' e) K5 q0 v) i
1 K1 r" p% |# T1 D
[color=rgba(0, 0, 0, 0.749019607843137)]2.2计算二叉树的大小
3 n* i4 c2 b/ k. [: t/ R[color=rgba(0, 0, 0, 0.749019607843137)]时间复杂度为O(N)
5 t# M q5 q. y6 F[color=rgba(0, 0, 0, 0.749019607843137)]& n7 Z$ M# J3 U0 E; f$ h( ?
% U) t3 x3 m) _; j E& K$ G4 O7 N* n4 s
[color=rgba(0, 0, 0, 0.749019607843137)]//二叉树的大小* `+ ?# U/ M6 Q, b
[color=rgba(0, 0, 0, 0.749019607843137)]//法一：全局变量
$ ?+ V. y( N, ~. M[color=rgba(0, 0, 0, 0.749019607843137)]//int count = 0;; o W$ ]3 q( S& g* Y3 V
[color=rgba(0, 0, 0, 0.749019607843137)]//void TreeSize(BTNode* root)" F" }, ?6 F4 {2 O# x) v6 W$ K
[color=rgba(0, 0, 0, 0.749019607843137)]//{* V$ x- L. h1 g) A
[color=rgba(0, 0, 0, 0.749019607843137)]// if (root == NULL)
# o6 [/ g& B; u0 j[color=rgba(0, 0, 0, 0.749019607843137)]// {, h! D1 C8 L I% p& O# d
[color=rgba(0, 0, 0, 0.749019607843137)]// return;+ }' J6 z% p0 \
[color=rgba(0, 0, 0, 0.749019607843137)]// }! l9 ~* [/ b. J; F1 x) L" d! v
[color=rgba(0, 0, 0, 0.749019607843137)]// count++;& G8 K9 R! }& ]/ y" R# T
[color=rgba(0, 0, 0, 0.749019607843137)]// TreeSize(root->left);& L/ {1 P- e! [
[color=rgba(0, 0, 0, 0.749019607843137)]// TreeSize(root->right);
" ^% r( o# j9 A5 S: z. _. W[color=rgba(0, 0, 0, 0.749019607843137)]// C$ K, A) }0 [2 n
[color=rgba(0, 0, 0, 0.749019607843137)]// return;//函数栈帧层层返回，最后回到根节点1，结束了1的右子树函数，什么都不返回，因为count是全局变量3 a, z5 O5 J5 v6 g
[color=rgba(0, 0, 0, 0.749019607843137)]//}
* r3 P' _' }! W6 r' Z p* y; V/ a[color=rgba(0, 0, 0, 0.749019607843137)]//法二：子问题思路：分而治之+ k6 {! D8 g2 a! a" X
[color=rgba(0, 0, 0, 0.749019607843137)]int TreeSize(BTNode* root)6 K& H7 O8 E( `7 B2 U. W: k
[color=rgba(0, 0, 0, 0.749019607843137)]{$ Q* \3 Z0 }& x5 Z
[color=rgba(0, 0, 0, 0.749019607843137)] return root == NULL ? 0 : TreeSize(root->left) + TreeSize(root->right) + 1;
" _) C5 e% S, K[color=rgba(0, 0, 0, 0.749019607843137)]}; I; z- Q2 {. t7 Y" ?* `8 u% m
[color=rgba(0, 0, 0, 0.749019607843137)]1
* E4 L M% p+ |# X3 D( W/ b[color=rgba(0, 0, 0, 0.749019607843137)]2: @2 t( h9 y1 S: f) `% |' I
[color=rgba(0, 0, 0, 0.749019607843137)]3. Y( w- _4 H* F% H
[color=rgba(0, 0, 0, 0.749019607843137)]4
) Z3 D1 U" V3 u* X9 d# ~( G$ b; s[color=rgba(0, 0, 0, 0.749019607843137)]5
1 m# W' X6 _" `% H0 J+ x. G9 C[color=rgba(0, 0, 0, 0.749019607843137)]6
6 ^& W0 o" i% w% v[color=rgba(0, 0, 0, 0.749019607843137)]7" x5 w! k$ r- m) e' B
[color=rgba(0, 0, 0, 0.749019607843137)]86 \6 M: A7 C8 m$ ]# o
[color=rgba(0, 0, 0, 0.749019607843137)]9) Z$ R/ o- V$ u$ t, t6 ? N( j
[color=rgba(0, 0, 0, 0.749019607843137)]10
; y' b$ x, K6 j$ d( |' O: [[color=rgba(0, 0, 0, 0.749019607843137)]116 O) ~( T/ h2 V9 `
[color=rgba(0, 0, 0, 0.749019607843137)]12
0 [8 ^& D( \- ^7 n" B, J[color=rgba(0, 0, 0, 0.749019607843137)]13
5 Y4 ~8 m1 e5 } {( J3 Y' U7 ^# @( X[color=rgba(0, 0, 0, 0.749019607843137)]14
% q l# n0 J. ?1 g3 i* G[color=rgba(0, 0, 0, 0.749019607843137)]15
& W8 b& s! t2 v/ P[color=rgba(0, 0, 0, 0.749019607843137)]16
8 O G* g- R9 N0 v[color=rgba(0, 0, 0, 0.749019607843137)]17
% Y- q9 O9 V0 J A[color=rgba(0, 0, 0, 0.749019607843137)]18
$ J1 U: `! p# h+ Q3 @[color=rgba(0, 0, 0, 0.749019607843137)]19
" |! H: o- O9 N$ W+ _6 N[color=rgba(0, 0, 0, 0.749019607843137)]20( o$ Z) d4 }9 B0 z E( o9 S) a
[color=rgba(0, 0, 0, 0.749019607843137)]2.3计算二叉树叶子结点的个数/ I3 }4 L% t# |- H4 ~$ y$ L' l
[color=rgba(0, 0, 0, 0.749019607843137)]//计算二叉树叶子结点的个数. ~2 T1 }" V6 F0 {
[color=rgba(0, 0, 0, 0.749019607843137)]int TreeLeafSize(BTNode* root)! M' m- f) H1 K! |6 f7 @/ l9 _7 x
[color=rgba(0, 0, 0, 0.749019607843137)]{
! L1 O4 N" e! I9 h7 u! N: o[color=rgba(0, 0, 0, 0.749019607843137)] if (root == NULL)//首先得考虑空树的情况,0个叶子结点
& o4 J ?1 A+ f0 O2 ^, k[color=rgba(0, 0, 0, 0.749019607843137)] {
4 M' x0 [6 M3 ~6 ^4 {! P6 v[color=rgba(0, 0, 0, 0.749019607843137)] return 0;' c# T0 G8 A- J) x
[color=rgba(0, 0, 0, 0.749019607843137)] }
6 p, P& u0 d3 A( ^; C( d8 P6 C7 U[color=rgba(0, 0, 0, 0.749019607843137)] //叶子结点的特征就是左右子树为空
, Q' P8 }2 W, L. ][color=rgba(0, 0, 0, 0.749019607843137)] if (root->left == NULL && root->right == NULL)
" W" |. Y1 w6 Y/ [. Q[color=rgba(0, 0, 0, 0.749019607843137)] {
1 {$ U5 j- ?% H& w$ u[color=rgba(0, 0, 0, 0.749019607843137)] return 1;) O8 Z; R8 d& I4 y+ T9 O4 o: ]% x
[color=rgba(0, 0, 0, 0.749019607843137)] }1 c) f- ?4 F" m8 f$ s
[color=rgba(0, 0, 0, 0.749019607843137)] return TreeLeafSize(root->left) + TreeLeafSize(root->right);8 N0 S, F5 t5 _6 J+ B1 s% M
[color=rgba(0, 0, 0, 0.749019607843137)]}* D' ~4 p' P/ ^5 i4 \5 a$ c7 f6 V
[color=rgba(0, 0, 0, 0.749019607843137)]1) e0 u+ e! q+ {( X
[color=rgba(0, 0, 0, 0.749019607843137)]26 E% o0 U% n' u7 ?
[color=rgba(0, 0, 0, 0.749019607843137)]39 ^8 P3 ^' I# L6 c2 B8 k
[color=rgba(0, 0, 0, 0.749019607843137)]4
$ Z4 \7 T/ B$ ~( l1 m7 G[color=rgba(0, 0, 0, 0.749019607843137)]5
1 d5 y3 j# N; w/ B) t- Q- t1 W3 v# ^[color=rgba(0, 0, 0, 0.749019607843137)]6, o* E$ N0 t7 e( [8 \5 Q: E# ~
[color=rgba(0, 0, 0, 0.749019607843137)]71 e$ Q2 h9 S! k1 y# J1 w, E1 B" }& B
[color=rgba(0, 0, 0, 0.749019607843137)]8
/ o1 }1 O4 I; j# ?. ?# h[color=rgba(0, 0, 0, 0.749019607843137)]92 ~2 w- f" f/ M3 z: e
[color=rgba(0, 0, 0, 0.749019607843137)]10! _3 O3 ?/ a( b1 J V% ^( k
[color=rgba(0, 0, 0, 0.749019607843137)]113 |1 \' r# x1 i6 p; s' `% P
[color=rgba(0, 0, 0, 0.749019607843137)]12
7 g ^9 |5 Z3 |/ P, E[color=rgba(0, 0, 0, 0.749019607843137)]13( V# N* R7 `3 w6 \' R5 _
[color=rgba(0, 0, 0, 0.749019607843137)]147 a! m, g0 c8 y5 a' E; b1 V
[color=rgba(0, 0, 0, 0.749019607843137)]2.4计算二叉树的高度% e$ [% X* z( d5 P7 Q
[color=rgba(0, 0, 0, 0.749019607843137)]int TreeHeight(BTNode* root)
- V: E9 C* Z* t" ]$ w[color=rgba(0, 0, 0, 0.749019607843137)]{! X( P$ n0 b" s& Y7 j" k- U
[color=rgba(0, 0, 0, 0.749019607843137)] //空树高度为0% o$ `1 }: f: \, a5 k' n$ @7 G
[color=rgba(0, 0, 0, 0.749019607843137)] if (root == NULL)
) A( ~( V: z! c- J1 {8 g[color=rgba(0, 0, 0, 0.749019607843137)] {
! D9 z. N h1 x0 S) ?' p[color=rgba(0, 0, 0, 0.749019607843137)] return 0;
! r$ ]; t! v; U2 m[color=rgba(0, 0, 0, 0.749019607843137)] }2 Y) @$ W% Z' R% P5 M5 h! V: L# b
[color=rgba(0, 0, 0, 0.749019607843137)] //树的高度是较高的那棵子树1 m& u2 M4 Q) D6 b. Z& U
[color=rgba(0, 0, 0, 0.749019607843137)] int lh = TreeHeight(root->left);//左子树的高度: p; [$ @/ F ]3 W$ N
[color=rgba(0, 0, 0, 0.749019607843137)] int rh = TreeHeight(root->right);//右子树的高度 \( k7 m% E7 f; |2 f) u+ S
[color=rgba(0, 0, 0, 0.749019607843137)]
; E- b8 v- r; r6 I/ t$ V. b3 t1 s1 Z( G) ^" Q
[color=rgba(0, 0, 0, 0.749019607843137)] return lh > rh ? lh + 1 : rh + 1;# i; ^+ ]# C2 n/ M
[color=rgba(0, 0, 0, 0.749019607843137)]}) A# V* B/ J. M/ K
[color=rgba(0, 0, 0, 0.749019607843137)]19 b' S$ ]5 b( _" ]
[color=rgba(0, 0, 0, 0.749019607843137)]2% }2 N4 J8 }- A Z9 @" x
[color=rgba(0, 0, 0, 0.749019607843137)]3
$ S; z4 ~& t0 m6 S[color=rgba(0, 0, 0, 0.749019607843137)]4
n2 U1 S% c& `$ F3 Q[color=rgba(0, 0, 0, 0.749019607843137)]55 ^0 A/ J6 j1 L+ r! ]0 y% _
[color=rgba(0, 0, 0, 0.749019607843137)]6
) N4 S$ H8 Z) ~3 m8 ?1 I. U8 `[color=rgba(0, 0, 0, 0.749019607843137)]7, n" S5 j' O2 X. p
[color=rgba(0, 0, 0, 0.749019607843137)]8( X8 W9 d1 D8 n- S# V7 H$ `( O9 t& E
[color=rgba(0, 0, 0, 0.749019607843137)]9
, w! B+ Q: w: M' T% b2 T) a5 B[color=rgba(0, 0, 0, 0.749019607843137)]10$ I" U+ z |+ L6 Y/ P# F& T9 b
[color=rgba(0, 0, 0, 0.749019607843137)]11: S: [/ i0 W8 W! @8 ~% t
[color=rgba(0, 0, 0, 0.749019607843137)]120 p( R* I* }( v# n! ^
[color=rgba(0, 0, 0, 0.749019607843137)]13
( s* }3 `0 [0 A9 E[color=rgba(0, 0, 0, 0.749019607843137)]2.5计算第K层结点的个数
5 v5 ?- |( I" e6 g4 H* F- F( P[color=rgba(0, 0, 0, 0.749019607843137)]
1 N$ K S, l% m5 X- `% n
% r0 \9 b7 w6 n( M[color=rgba(0, 0, 0, 0.749019607843137)]# @& \; g8 u% o6 I4 y
* |) D5 W9 {: Y7 Z0 ~[color=rgba(0, 0, 0, 0.749019607843137)]求第K层的结点个数，转换成求子树第K-1层的结点个数。举个栗子：如果我们要求这棵二叉树第3层的结点个数（为3），就转换成求左子树根结点2的第2层的结点个数+右子树4第二层的结点个数。。。: W2 m! ]# R$ g$ R1 P& c4 e6 J
[color=rgba(0, 0, 0, 0.749019607843137)]/ Q# E$ h+ g- R; M; O. ]( _
5 z8 `) {8 f4 J) Q8 ~' G. T/ x
[color=rgba(0, 0, 0, 0.749019607843137)]//计算第K层结点的个数
' O0 u, W0 _( R# I8 y[color=rgba(0, 0, 0, 0.749019607843137)]int TreeLevel(BTNode* root,int K)
' f+ z- M3 E4 I0 k( Q4 a3 H[color=rgba(0, 0, 0, 0.749019607843137)]{
5 I/ R9 ?( Q# G' Y" _3 `. k[color=rgba(0, 0, 0, 0.749019607843137)] assert(K > 0);& C/ W3 d9 E, K
[color=rgba(0, 0, 0, 0.749019607843137)] if (root == NULL)
( J2 M/ F$ x, ^& o) |[color=rgba(0, 0, 0, 0.749019607843137)] {
5 {2 S+ Y: i0 Y$ N. K[color=rgba(0, 0, 0, 0.749019607843137)] return 0;6 C# ^* {" w+ a9 T" q; k$ L$ e
[color=rgba(0, 0, 0, 0.749019607843137)] }
% _: C! C9 l8 C3 C[color=rgba(0, 0, 0, 0.749019607843137)] //如果是第一层(递归出口)' r$ b1 C. M) [6 @. U
[color=rgba(0, 0, 0, 0.749019607843137)] if (K == 1); W/ M) P4 k7 |
[color=rgba(0, 0, 0, 0.749019607843137)] {
+ g( q, ]1 H) K$ O( X[color=rgba(0, 0, 0, 0.749019607843137)] return 1;4 |+ x, z" V7 @* E: [( Y
[color=rgba(0, 0, 0, 0.749019607843137)] }
5 i) L% x- F0 B4 \; g[color=rgba(0, 0, 0, 0.749019607843137)] //转换成子树的第K-1层
' _5 C8 d3 h( F+ h[color=rgba(0, 0, 0, 0.749019607843137)] return TreeLevel(root->left,K-1) + TreeLevel(root->right,K-1);7 k3 [. Z: Z7 r p) q1 y9 I
[color=rgba(0, 0, 0, 0.749019607843137)]}: x# L: H5 Q$ V B+ B5 t$ C; n
[color=rgba(0, 0, 0, 0.749019607843137)]18 B, R- s$ X* ?4 x, p/ z3 K. K
[color=rgba(0, 0, 0, 0.749019607843137)]2' ~1 E9 d. a6 N( w" v3 h" r
[color=rgba(0, 0, 0, 0.749019607843137)]3' @) I& p8 v a7 f/ ~
[color=rgba(0, 0, 0, 0.749019607843137)]4) g/ k4 r, j, |
[color=rgba(0, 0, 0, 0.749019607843137)]5' O* w' B" B3 P7 B% Z$ a
[color=rgba(0, 0, 0, 0.749019607843137)]6
" R# z8 c+ c7 w5 S f[color=rgba(0, 0, 0, 0.749019607843137)]7) y( E& @ B/ L" \$ K5 h
[color=rgba(0, 0, 0, 0.749019607843137)]88 g% V$ b! K" {- n7 f: z
[color=rgba(0, 0, 0, 0.749019607843137)]91 x2 p$ V) h: _ o+ \6 E
[color=rgba(0, 0, 0, 0.749019607843137)]10
2 V+ k- U8 ~ v[color=rgba(0, 0, 0, 0.749019607843137)]11
5 ~( r" T& ^3 C3 u; L n8 G9 \[color=rgba(0, 0, 0, 0.749019607843137)]12
, {% ` n$ t4 x, X! d' t[color=rgba(0, 0, 0, 0.749019607843137)]13
% G; g h J; Q0 N" D6 @; d9 _[color=rgba(0, 0, 0, 0.749019607843137)]14
) W8 L" @ G; h. P/ q* T& p8 W[color=rgba(0, 0, 0, 0.749019607843137)]15' J$ c) ^2 {$ V: |0 q9 P& B
[color=rgba(0, 0, 0, 0.749019607843137)]16
' ~; a s$ e, L- ^[color=rgba(0, 0, 0, 0.749019607843137)]2.6二叉树查找$ B3 w2 l1 n! `4 W4 f
[color=rgba(0, 0, 0, 0.749019607843137)]//二叉树查找* m# J+ G+ v# D( b
[color=rgba(0, 0, 0, 0.749019607843137)]BTNode* TreeFind(BTNode* root, BTDataType data)4 b) Y9 ]6 C1 H8 c; d
[color=rgba(0, 0, 0, 0.749019607843137)]{
/ n* X, z/ J& j3 F n Q[color=rgba(0, 0, 0, 0.749019607843137)] if (root == NULL)1 V) v( V7 w% i/ P! s3 h
[color=rgba(0, 0, 0, 0.749019607843137)] {: z9 ?/ ^( q" ~: F) ^, \
[color=rgba(0, 0, 0, 0.749019607843137)] return NULL;, G0 y7 A) f1 N, h) }1 V
[color=rgba(0, 0, 0, 0.749019607843137)] }$ S3 \0 C) w A, J: \
[color=rgba(0, 0, 0, 0.749019607843137)] if (root->data == data)
2 A3 z5 P# J+ V[color=rgba(0, 0, 0, 0.749019607843137)] {! W8 j' L9 `' P% @
[color=rgba(0, 0, 0, 0.749019607843137)] return root;
" e; K% A$ _& x& _9 c+ n+ U. t8 R[color=rgba(0, 0, 0, 0.749019607843137)] }* a& \& O1 }. z3 Q, o# q
[color=rgba(0, 0, 0, 0.749019607843137)] //先查找左子树( t P" g( I g
[color=rgba(0, 0, 0, 0.749019607843137)] BTNode* lret = TreeFind(root->left, data);4 V( U( j- Z+ X, r; e, O
[color=rgba(0, 0, 0, 0.749019607843137)] if (lret)) A/ L9 k# v1 Q3 h4 D
[color=rgba(0, 0, 0, 0.749019607843137)] return lret;: P! m$ a+ e/ o0 t
[color=rgba(0, 0, 0, 0.749019607843137)] //再查找右子树
$ B' v5 Q# J6 P. H[color=rgba(0, 0, 0, 0.749019607843137)] BTNode* rret = TreeFind(root->right, data);
; K3 T3 u9 J2 g0 Z: p[color=rgba(0, 0, 0, 0.749019607843137)] if (rret)
% ]% ?3 l+ [9 w j+ R G[color=rgba(0, 0, 0, 0.749019607843137)] return rret;4 D2 ]% L+ R$ `, V7 F: x- j. b
[color=rgba(0, 0, 0, 0.749019607843137)] return NULL;" k( M3 p0 y. m2 y
[color=rgba(0, 0, 0, 0.749019607843137)]}
1 u+ S. O0 }5 Y8 D[color=rgba(0, 0, 0, 0.749019607843137)]————————————————' s- \/ ~0 {$ k0 e! ^& l
[color=rgba(0, 0, 0, 0.749019607843137)]版权声明：本文为CSDN博主「SouLinya」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。! |0 I% H. m5 r, S/ a" W9 l
[color=rgba(0, 0, 0, 0.749019607843137)]原文链接：https://blog.csdn.net/weixin_63449996/article/details/1268412127 V/ e3 t) `' N) }& e
& p: Z+ _% |4 n P
: r6 B, T6 H5 @( W/ ][color=rgba(0, 0, 0, 0.75)]
7 S& M/ N3 C4 ^& }0 }+ j0 G9 L* k6 Q
. l$ @2 l! h% Q5 F7 o% I
9 D! ]2 Y1 n; _1 b! Y1 M, u' ^ |
IP卡
狗仔卡
发表于 2022-9-15 11:55
转播
淘帖
分享
收藏
支持
反对
微信
提升卡
置顶卡
沉默卡
喧嚣卡
变色卡
抢沙发
显身卡
