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