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