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