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