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