【数据结构】二叉树的遍历：前序，中序，后序的递归结构遍历
" a' d+ b H9 J4 ?7 J7 Q
, r$ |0 g; Q+ v) q$ J# \[color=rgba(0, 0, 0, 0.749019607843137)]文章目录+ E7 q. _" h/ l8 d. s, h
[color=rgba(0, 0, 0, 0.749019607843137)]前言
7 B1 B( ~7 h; j1 F[color=rgba(0, 0, 0, 0.749019607843137)]1.二叉树的遍历方式, s( V- {8 l( p: D) A
[color=rgba(0, 0, 0, 0.749019607843137)]2.二叉树的遍历及相关函数（代码实现）7 @2 X L. G- T& w. {
[color=rgba(0, 0, 0, 0.749019607843137)]2.1前序/中序/后序的遍历& v0 ^$ B* s+ `/ m; m! u/ w0 C
[color=rgba(0, 0, 0, 0.749019607843137)]2.2计算二叉树的大小
! u; p& a2 ]+ V4 D7 j[color=rgba(0, 0, 0, 0.749019607843137)]2.3计算二叉树叶子结点的个数
+ x8 G% v/ R& H7 r$ l" }[color=rgba(0, 0, 0, 0.749019607843137)]2.4计算二叉树的高度
( k1 J) f( `! y c5 C$ B[color=rgba(0, 0, 0, 0.749019607843137)]2.5计算第K层结点的个数; Q n' Y: V: J. W& x
[color=rgba(0, 0, 0, 0.749019607843137)]2.6二叉树查找
) n( b4 F/ B3 P+ [1 p# Z[color=rgba(0, 0, 0, 0.749019607843137)]前言& \; @, R. M, D0 D, H! Q P7 H# y1 q
[color=rgba(0, 0, 0, 0.749019607843137)]在学习二叉树的遍历之前，我们需要先创建一棵二叉树，然后才能学习其相关的基本操作，由于现在我们对二叉树结构的掌握还在初阶部分，为了降低大家的学习成本，我们先手动快速创建一棵简单的二叉树，快速进入二叉树的操作学习，这个方法在我们调试程序代码的时候，也非常适用。等二叉树结构了解的差不多时，我们再继续研究二叉树真正的创建方式。1 W0 Z; d0 k8 G9 f @) _! y; Z
[color=rgba(0, 0, 0, 0.749019607843137)]
. K! r# ?! W( u& G8 U' T& g2 J; n% F4 E4 T, |
[color=rgba(0, 0, 0, 0.749019607843137)]1.二叉树的遍历方式0 r. O$ W, e3 T" M1 n+ u
[color=rgba(0, 0, 0, 0.749019607843137)]
8 L7 T" k: H" V+ Z! V7 X$ K7 ]2 n8 S& q( g- @' b# n# ^- l) \ Y
[color=rgba(0, 0, 0, 0.749019607843137)]按照规则，二叉树的遍历有：前序/中序/后序的递归结构遍历访问顺序：
: I/ U. X" U# e7 a[color=rgba(0, 0, 0, 0.749019607843137)]
9 e( i/ G1 v7 p" m; y! z/ A/ l2 {5 U" y8 y
[color=rgba(0, 0, 0, 0.749019607843137)]1. 前序遍历（先序，先根):根——左子树——右子树5 p. P5 Q! s; A( S5 Q! d
[color=rgba(0, 0, 0, 0.749019607843137)]
3 U; ?" m! q: b+ { _& J
! a, D6 z% V2 C; B[color=rgba(0, 0, 0, 0.749019607843137)]. |2 K3 B! P8 P# p
! I/ \5 k4 N* W7 q/ v; d[color=rgba(0, 0, 0, 0.749019607843137)]2. 中序遍历（中根）：左子树——根——右子树
4 d( m5 \9 l* L3 w$ j9 `[color=rgba(0, 0, 0, 0.749019607843137)]) ?; Q# Y% j. P; M1 u B# b5 z
3 v; s3 [9 J! b5 u) C/ z1 L& E3 ^! c[color=rgba(0, 0, 0, 0.749019607843137)]
% o$ v# O# j. y4 O6 v
7 ^1 b N C, L/ u, Q8 S9 w[color=rgba(0, 0, 0, 0.749019607843137)]3. 后序遍历（后根）：左子树——右子树——根1 J; V$ G1 M S4 `9 w% S `- z
[color=rgba(0, 0, 0, 0.749019607843137)]
3 ~& d1 ^. a* ^; C
" j0 ]9 B2 j; y! t% W! j[color=rgba(0, 0, 0, 0.749019607843137)]
8 T3 s! Z( u& [& Z% c; _/ Y V& S6 {3 Y" e" [
[color=rgba(0, 0, 0, 0.749019607843137)]2.二叉树的遍历及相关函数（代码实现）; {/ F8 ]! G% L
[color=rgba(0, 0, 0, 0.749019607843137)]思路：分而治之
; F& o* [1 U+ H0 W[color=rgba(0, 0, 0, 0.749019607843137)]1.首先我们要用简单的方式先创建出一棵二叉树，并赋予数据；& a7 b& g1 E9 I6 B' L
[color=rgba(0, 0, 0, 0.749019607843137)]2.采用递归的方式，分别实现前序/中序/后序遍历这棵二叉树；
8 X7 x8 l: N6 B! p[color=rgba(0, 0, 0, 0.749019607843137)]3.尝试计算这个二叉树的大小（利用递归）；/ d2 t7 W0 ?5 B% X0 g
[color=rgba(0, 0, 0, 0.749019607843137)]4.尝试计算叶子结点的个数（利用递归）；
/ @1 ^7 V4 W$ ]% ][color=rgba(0, 0, 0, 0.749019607843137)]5.尝试计算二叉树的高度（利用递归）；
5 u' b2 ^* S* v$ T1 B4 j[color=rgba(0, 0, 0, 0.749019607843137)]6.尝试写出计算第K层结点的个数的函数（利用递归）；2 g2 q1 S G) f
[color=rgba(0, 0, 0, 0.749019607843137)]7.尝试写出二叉树查找的函数（利用递归）。
8 v4 M d( V, \* `+ A[color=rgba(0, 0, 0, 0.749019607843137)]
& _' ~6 z* ^8 d, X# q8 r3 g- z/ n# o1 i' E v3 `% `
[color=rgba(0, 0, 0, 0.749019607843137)]2.1前序/中序/后序的遍历
& D W) c: a' x[color=rgba(0, 0, 0, 0.749019607843137)]#define _CRT_SECURE_NO_WARNINGS 1
7 V9 N$ {3 u: ?4 q: l* u! c[color=rgba(0, 0, 0, 0.749019607843137)]#include<stdio.h>" e8 T- `7 V# L" j' |4 h5 y
[color=rgba(0, 0, 0, 0.749019607843137)]#include<assert.h>
, X, k& H1 o+ G% q; D" D! o[color=rgba(0, 0, 0, 0.749019607843137)]#include<stdlib.h>
' A* g; |. D: w# @: J7 K[color=rgba(0, 0, 0, 0.749019607843137)]1 D' q8 U: k' W- m4 j
- e" a; K) b Y& H6 H8 n/ W[color=rgba(0, 0, 0, 0.749019607843137)]typedef int BTDataType;+ J( ^6 ?1 B6 l7 X
[color=rgba(0, 0, 0, 0.749019607843137)]9 ]: r" _4 S2 E$ p" R
3 d1 N1 z$ f- [# Q6 s
[color=rgba(0, 0, 0, 0.749019607843137)]//定义二叉树结点的结构体1 [, b% I. a a# b! Y3 ^! |
[color=rgba(0, 0, 0, 0.749019607843137)]typedef struct BinaryTreeNode
: _0 \% L: L+ {. t7 X& l[color=rgba(0, 0, 0, 0.749019607843137)]{* S/ ^1 e( y9 E+ s
[color=rgba(0, 0, 0, 0.749019607843137)] BTDataType data;
" _; |; m+ A6 H& _7 D[color=rgba(0, 0, 0, 0.749019607843137)] struct BinaryTreeNode* left;7 U& L) m8 y0 ?5 @) @; N
[color=rgba(0, 0, 0, 0.749019607843137)] struct BinaryTreeNode* right;
; a) J, [+ K k[color=rgba(0, 0, 0, 0.749019607843137)]}BTNode;
! l- _( r8 u; }7 z) |; g$ u2 T: n[color=rgba(0, 0, 0, 0.749019607843137)]
7 I" F$ y/ ^+ U: e: z. Y7 x6 K8 y6 b2 Z3 {- E* v
[color=rgba(0, 0, 0, 0.749019607843137)]//前序遍历
: [+ ~( l, B. q% m: b0 Z V[color=rgba(0, 0, 0, 0.749019607843137)]void PreOrder(BTNode* root)
3 Z: @' p2 S& Z; d/ |+ D[color=rgba(0, 0, 0, 0.749019607843137)]{, ]- D. ^. d% T% a9 x7 S) g. P a
[color=rgba(0, 0, 0, 0.749019607843137)] if (root == NULL)
3 P9 p% Y3 i C7 E& a, n5 y[color=rgba(0, 0, 0, 0.749019607843137)] {
' U- x$ X4 T6 m; @% x[color=rgba(0, 0, 0, 0.749019607843137)] printf("NULL ");2 f4 d6 J9 m) Y( |/ f( s+ F
[color=rgba(0, 0, 0, 0.749019607843137)] return;. F1 m' d. F0 z% u( Q4 t
[color=rgba(0, 0, 0, 0.749019607843137)] }& n Y. E' {; {, h
[color=rgba(0, 0, 0, 0.749019607843137)] printf("%d ", root->data);& S3 ]5 F F, T$ K7 e6 |3 u7 v
[color=rgba(0, 0, 0, 0.749019607843137)] PreOrder(root->left);
4 n" w% _5 f8 D& e% t S7 H[color=rgba(0, 0, 0, 0.749019607843137)] PreOrder(root->right);
2 x# D1 j- e# j2 }5 I/ o[color=rgba(0, 0, 0, 0.749019607843137)]}; f$ V2 Z, k% j4 m
[color=rgba(0, 0, 0, 0.749019607843137)]//中序遍历
+ H) L! n6 |- ]# V; t' `[color=rgba(0, 0, 0, 0.749019607843137)]void InOrder(BTNode* root)1 q$ u, w h# K9 m% K0 p7 `4 ^4 n+ z# }( p
[color=rgba(0, 0, 0, 0.749019607843137)]{, P' L" s1 Z2 h5 H0 ]" m
[color=rgba(0, 0, 0, 0.749019607843137)] if (root == NULL)- v e. A9 J4 w7 ]3 Q, }5 N G
[color=rgba(0, 0, 0, 0.749019607843137)] {
6 Q! o5 h; `+ e+ |[color=rgba(0, 0, 0, 0.749019607843137)] printf("NULL ");* W5 p: B( _1 J$ D) r# d
[color=rgba(0, 0, 0, 0.749019607843137)] return;
" e d2 R6 j1 P" ^[color=rgba(0, 0, 0, 0.749019607843137)] }5 V: w7 U7 y% B0 Q" |6 D( [
[color=rgba(0, 0, 0, 0.749019607843137)] InOrder(root->left);
; e9 n4 f% m% E[color=rgba(0, 0, 0, 0.749019607843137)] printf("%d ", root->data);- ~" o! \+ \9 n4 d4 {7 L' i
[color=rgba(0, 0, 0, 0.749019607843137)] InOrder(root->right);
5 H9 G& w. A. O$ v* b0 y: V" O( |[color=rgba(0, 0, 0, 0.749019607843137)]}
5 m: Z! V. K0 V/ o[color=rgba(0, 0, 0, 0.749019607843137)]//后序遍历
4 h# S9 b H5 c% `[color=rgba(0, 0, 0, 0.749019607843137)]void PostOrder(BTNode* root)# E O7 }% l$ D
[color=rgba(0, 0, 0, 0.749019607843137)]{. F a, e) ~1 C: z" T9 ~. q; z9 f! N
[color=rgba(0, 0, 0, 0.749019607843137)] if (root == NULL)! Y o. O" J# m2 |; X5 f- @
[color=rgba(0, 0, 0, 0.749019607843137)] {" H! \$ B3 F( Y: M1 J# n: I! A
[color=rgba(0, 0, 0, 0.749019607843137)] printf("NULL ");; |6 s, k% {. a; a. M( ]6 L/ \
[color=rgba(0, 0, 0, 0.749019607843137)] return;* w( M) s$ d& Z L, E& x5 d/ G
[color=rgba(0, 0, 0, 0.749019607843137)] }
; Q3 {# B5 E; x t6 R- V[color=rgba(0, 0, 0, 0.749019607843137)] PostOrder(root->left);
4 d/ i8 L+ K! W[color=rgba(0, 0, 0, 0.749019607843137)] PostOrder(root->right);
7 Q6 |) v7 M. o: [. m7 o; N6 m4 [[color=rgba(0, 0, 0, 0.749019607843137)] printf("%d ", root->data);
. d$ I; Q- | z" Q b[color=rgba(0, 0, 0, 0.749019607843137)]}
! {5 Z1 _: o7 L[color=rgba(0, 0, 0, 0.749019607843137)]//先创建一个简单的二叉树结构
2 P6 K. r& a; N0 n& f[color=rgba(0, 0, 0, 0.749019607843137)]BTNode* CreateTree(), X5 l0 a q2 A
[color=rgba(0, 0, 0, 0.749019607843137)]{$ S1 D& {. T1 M
[color=rgba(0, 0, 0, 0.749019607843137)] //先动态开辟6个结点的空间
) [% s8 \. b. H" c' Y8 a7 p& }[color=rgba(0, 0, 0, 0.749019607843137)] BTNode* n1 = (BTNode*)malloc(sizeof(BTNode));& T+ w- K9 X0 b
[color=rgba(0, 0, 0, 0.749019607843137)] assert(n1);
% v) S6 Z0 r! }9 |[color=rgba(0, 0, 0, 0.749019607843137)] BTNode* n2 = (BTNode*)malloc(sizeof(BTNode));# S& u" c& K3 v2 h c4 X% |- k
[color=rgba(0, 0, 0, 0.749019607843137)] assert(n2);
9 ]' o- M2 V4 T" ^% `[color=rgba(0, 0, 0, 0.749019607843137)] BTNode* n3 = (BTNode*)malloc(sizeof(BTNode));9 O* p4 o- W# r! ]$ a8 X q- m
[color=rgba(0, 0, 0, 0.749019607843137)] assert(n3);5 L! D0 J, W3 }9 e4 g3 w7 L! Q/ a
[color=rgba(0, 0, 0, 0.749019607843137)] BTNode* n4 = (BTNode*)malloc(sizeof(BTNode));5 X3 ^& S% g' c& {9 J2 `
[color=rgba(0, 0, 0, 0.749019607843137)] assert(n4);! y' e- v+ L# Z: \7 u6 z$ e: R
[color=rgba(0, 0, 0, 0.749019607843137)] BTNode* n5 = (BTNode*)malloc(sizeof(BTNode));5 Q* c4 r2 ^) U9 i
[color=rgba(0, 0, 0, 0.749019607843137)] assert(n5);
1 D8 C6 Z8 k! J0 ]' N[color=rgba(0, 0, 0, 0.749019607843137)] BTNode* n6 = (BTNode*)malloc(sizeof(BTNode));
+ i/ |) D* P, J# r3 P7 c* j/ K0 g[color=rgba(0, 0, 0, 0.749019607843137)] assert(n6);& P- V8 H) _/ B* u$ T# Y! b, ~" {, q( l
[color=rgba(0, 0, 0, 0.749019607843137)]
. H5 d% e9 V: @. v
g2 j, ]+ |, V) c5 @) \$ o8 E* e[color=rgba(0, 0, 0, 0.749019607843137)] n1->data = 1;- H# T$ R1 E+ X8 s5 C
[color=rgba(0, 0, 0, 0.749019607843137)] n2->data = 2;9 h8 _/ Q3 i. T* v7 k
[color=rgba(0, 0, 0, 0.749019607843137)] n3->data = 3;9 V3 d: G% x1 g/ d8 G6 N3 J
[color=rgba(0, 0, 0, 0.749019607843137)] n4->data = 4;
B$ ]9 b' w3 p) z j[color=rgba(0, 0, 0, 0.749019607843137)] n5->data = 5;
$ f, }2 a- f( X* I: ]/ Q[color=rgba(0, 0, 0, 0.749019607843137)] n6->data = 6;
# I+ _+ N% \: c' i* }3 A+ q* d/ b[color=rgba(0, 0, 0, 0.749019607843137)]
4 w! r% T" d! d" A# Y# A8 S
% a: p: I' Q [* z3 _[color=rgba(0, 0, 0, 0.749019607843137)] n1->left = n2;
8 ~; x/ n( E: q[color=rgba(0, 0, 0, 0.749019607843137)] n1->right = n4;# C) F& x( r$ ^' F8 @7 G
[color=rgba(0, 0, 0, 0.749019607843137)] n2->left = n3;
3 n- N% |# B3 U8 D* ] I. k( p[color=rgba(0, 0, 0, 0.749019607843137)] n2->right = NULL;( i6 p# |: u5 i2 B* w
[color=rgba(0, 0, 0, 0.749019607843137)] n3->left = NULL;
9 O2 S n6 x$ `[color=rgba(0, 0, 0, 0.749019607843137)] n3->right = NULL;7 e/ e3 C5 i% f4 T: y
[color=rgba(0, 0, 0, 0.749019607843137)] n4->left = n5;
' q$ ?! L1 N: N2 j[color=rgba(0, 0, 0, 0.749019607843137)] n4->right = n6;* Q- e, l4 F$ g2 F/ E
[color=rgba(0, 0, 0, 0.749019607843137)] n5->left = NULL;) f- H4 t& }5 L3 j
[color=rgba(0, 0, 0, 0.749019607843137)] n5->right = NULL;9 s& O$ z/ X; i1 ^. t% e
[color=rgba(0, 0, 0, 0.749019607843137)] n6->left = NULL;
! y7 Z- V! h4 P- ][color=rgba(0, 0, 0, 0.749019607843137)] n6->right = NULL;& W0 [+ z) i- y3 n2 z* d
[color=rgba(0, 0, 0, 0.749019607843137)]
. v0 x4 o$ ~; }) B8 a
- d, d/ Z+ H) ]$ o0 k; p[color=rgba(0, 0, 0, 0.749019607843137)] return n1;+ t7 F/ U0 j1 }9 O
[color=rgba(0, 0, 0, 0.749019607843137)]}1 _7 ?7 ~3 v! V! g6 [
[color=rgba(0, 0, 0, 0.749019607843137)]2 f/ n* D" c# ], n6 H @; ~- M
8 \5 N1 D$ a% X7 D0 I& m# m[color=rgba(0, 0, 0, 0.749019607843137)]int main()
& S- h' l$ `7 n& L3 n[color=rgba(0, 0, 0, 0.749019607843137)]{
* }! S5 F) [5 \ Z( N8 N[color=rgba(0, 0, 0, 0.749019607843137)] //先创建一个简单的二叉树结构" r; c; @) ^* R( X4 B0 [
[color=rgba(0, 0, 0, 0.749019607843137)] BTNode* root = CreateTree();/ H: I9 A; x% ]$ |! q
[color=rgba(0, 0, 0, 0.749019607843137)]
x8 k* \& x/ e9 [4 y: g: z& q% F( b# \+ n) z2 N5 k
[color=rgba(0, 0, 0, 0.749019607843137)] //二叉树前序遍历( n3 ?( o* Q6 g& C* Z! i
[color=rgba(0, 0, 0, 0.749019607843137)] printf("二叉树前序遍历:");$ z- T: m4 y% N0 j, w/ n& W
[color=rgba(0, 0, 0, 0.749019607843137)] PreOrder(root);
! V; R( J; P3 e1 q1 R[color=rgba(0, 0, 0, 0.749019607843137)] printf("\n");
/ T) j, b! N% B8 `) x) J W5 o[color=rgba(0, 0, 0, 0.749019607843137)] //二叉树中序遍历
, ]; o5 Z/ L( L[color=rgba(0, 0, 0, 0.749019607843137)] printf("二叉树中序序遍历:");
3 a) L2 H9 e1 f/ z2 U[color=rgba(0, 0, 0, 0.749019607843137)] InOrder(root);$ @. ~9 @* @) g2 y' d8 w
[color=rgba(0, 0, 0, 0.749019607843137)] printf("\n");+ R) }% @9 b: l# d- |% r
[color=rgba(0, 0, 0, 0.749019607843137)] //二叉树后序遍历7 Y) Z- F/ c' T
[color=rgba(0, 0, 0, 0.749019607843137)] printf("二叉树后序遍历:");1 u. C( n! k7 X* \1 l2 p
[color=rgba(0, 0, 0, 0.749019607843137)] PostOrder(root);
5 \- C5 M# h+ H. f- C+ J[color=rgba(0, 0, 0, 0.749019607843137)] printf("\n");! e' E9 _3 I a# C$ y
[color=rgba(0, 0, 0, 0.749019607843137)]
/ t+ H6 S. J# P# L
8 b3 r* k. {8 @) k9 z[color=rgba(0, 0, 0, 0.749019607843137)] return 0;4 L% t% j% {5 R2 I( r9 O
[color=rgba(0, 0, 0, 0.749019607843137)]} f5 R' E+ y4 o) d+ ]( l$ {% j
[color=rgba(0, 0, 0, 0.749019607843137)]1' f1 D4 _# }% x/ A
[color=rgba(0, 0, 0, 0.749019607843137)]2: { K! H+ @2 ~0 M
[color=rgba(0, 0, 0, 0.749019607843137)]3
5 F: ^0 l) | s$ [- h. b[color=rgba(0, 0, 0, 0.749019607843137)]4
3 |+ ` d1 t9 I: {$ N! }5 |" ~' f[color=rgba(0, 0, 0, 0.749019607843137)]5
% W- q3 W6 N0 s# v: @[color=rgba(0, 0, 0, 0.749019607843137)]6$ m, ^& S, `+ w8 E# {1 s8 r
[color=rgba(0, 0, 0, 0.749019607843137)]7
; `' k3 X; n, ]8 Y[color=rgba(0, 0, 0, 0.749019607843137)]8- c- Q. ~; _% `5 Z0 Q( d
[color=rgba(0, 0, 0, 0.749019607843137)]9: c, a2 T1 Q4 X
[color=rgba(0, 0, 0, 0.749019607843137)]107 I+ `8 \; |9 T* i
[color=rgba(0, 0, 0, 0.749019607843137)]11" j; B! E% j) K9 U9 {! u
[color=rgba(0, 0, 0, 0.749019607843137)]12- j& F5 X! i" g$ C+ t! d8 k4 \
[color=rgba(0, 0, 0, 0.749019607843137)]133 T7 p% s! n! D9 w% V8 d
[color=rgba(0, 0, 0, 0.749019607843137)]14
8 V6 C+ `. r! y" o) C3 T; d, t# D! u[color=rgba(0, 0, 0, 0.749019607843137)]15
/ Y7 V* H/ B7 X, w[color=rgba(0, 0, 0, 0.749019607843137)]16& n( d) v U2 q$ r6 P
[color=rgba(0, 0, 0, 0.749019607843137)]17, P6 D' J- L8 P1 r0 H/ ~
[color=rgba(0, 0, 0, 0.749019607843137)]180 ~4 c0 C1 b% }% P6 E
[color=rgba(0, 0, 0, 0.749019607843137)]19
1 d0 v d; U" Y* b# y[color=rgba(0, 0, 0, 0.749019607843137)]206 j4 Y9 G) ~# h6 k! y$ k
[color=rgba(0, 0, 0, 0.749019607843137)]21! [( L/ _( U5 \8 ?) ~ P0 L
[color=rgba(0, 0, 0, 0.749019607843137)]229 _$ I- C" i/ C8 t0 n
[color=rgba(0, 0, 0, 0.749019607843137)]230 `% _! f l1 Z! n3 `
[color=rgba(0, 0, 0, 0.749019607843137)]24+ n% a7 a; x9 [
[color=rgba(0, 0, 0, 0.749019607843137)]251 [' q$ v+ F' X. b
[color=rgba(0, 0, 0, 0.749019607843137)]263 s* a0 N/ X% v4 S2 b+ G8 p1 T
[color=rgba(0, 0, 0, 0.749019607843137)]27
0 G i. U: ^4 q+ f[color=rgba(0, 0, 0, 0.749019607843137)]285 A/ p1 |" m. n
[color=rgba(0, 0, 0, 0.749019607843137)]29
+ R; u7 h8 y4 ]% W. [# H5 L[color=rgba(0, 0, 0, 0.749019607843137)]303 v0 z1 a8 q* j q- W
[color=rgba(0, 0, 0, 0.749019607843137)]31
, c& n G) R' k& r. h[color=rgba(0, 0, 0, 0.749019607843137)]329 [ M" N4 P Y. h* Y& \
[color=rgba(0, 0, 0, 0.749019607843137)]33' _6 T3 r( }& c5 ]/ E% z
[color=rgba(0, 0, 0, 0.749019607843137)]34
& j: ?& V5 q; S7 W6 I1 H3 }( a[color=rgba(0, 0, 0, 0.749019607843137)]355 O' h4 L; s( `; q
[color=rgba(0, 0, 0, 0.749019607843137)]360 T' \- Y m! Q) O4 |% v9 s- M% P N
[color=rgba(0, 0, 0, 0.749019607843137)]37
; n9 e; @9 {8 D' B4 j[color=rgba(0, 0, 0, 0.749019607843137)]38
7 Z4 X. }2 @2 D) ?+ w+ ?[color=rgba(0, 0, 0, 0.749019607843137)]39
* A4 R0 k7 J! P E5 z[color=rgba(0, 0, 0, 0.749019607843137)]40% w4 T% g( |; n, |2 n; x
[color=rgba(0, 0, 0, 0.749019607843137)]41
2 U) `0 D' u, v l! e- Y# M[color=rgba(0, 0, 0, 0.749019607843137)]42
0 p" X c5 L; F[color=rgba(0, 0, 0, 0.749019607843137)]435 T+ @. H; x1 @! ~9 Z
[color=rgba(0, 0, 0, 0.749019607843137)]44
9 l! ?/ n' A6 p/ {/ z! Z8 q: p' e[color=rgba(0, 0, 0, 0.749019607843137)]45
1 ]: O& I- o: r$ t) U* E[color=rgba(0, 0, 0, 0.749019607843137)]46
1 J- S3 Y! N# Y/ s9 ^[color=rgba(0, 0, 0, 0.749019607843137)]47
5 S1 l' U! Z& `- @ i, K[color=rgba(0, 0, 0, 0.749019607843137)]48& p0 E$ }0 j5 F( U
[color=rgba(0, 0, 0, 0.749019607843137)]49 V4 m& q. `7 ~2 A! o% k) I* k
[color=rgba(0, 0, 0, 0.749019607843137)]50
' c. s& r+ i0 l: A i4 I; X[color=rgba(0, 0, 0, 0.749019607843137)]51, w8 M- k- ~' i* A4 ]! q
[color=rgba(0, 0, 0, 0.749019607843137)]52# y, W2 P! d. {$ R) r z$ m8 P
[color=rgba(0, 0, 0, 0.749019607843137)]53! d2 G6 t" }: M6 `+ I4 l# e
[color=rgba(0, 0, 0, 0.749019607843137)]54$ k! D. I" O% x2 H
[color=rgba(0, 0, 0, 0.749019607843137)]55$ h( W. g& E* l* C
[color=rgba(0, 0, 0, 0.749019607843137)]560 A, B3 F8 ]5 x# B Y
[color=rgba(0, 0, 0, 0.749019607843137)]57+ H$ K8 J( F3 l5 s: ]4 K
[color=rgba(0, 0, 0, 0.749019607843137)]58
) c+ V) J! W) ^# L) |4 [3 V[color=rgba(0, 0, 0, 0.749019607843137)]59
2 v$ a8 x' K0 v1 ~. X T[color=rgba(0, 0, 0, 0.749019607843137)]60: X* u4 V1 m" \, K, |: q
[color=rgba(0, 0, 0, 0.749019607843137)]61, u* {. n$ S. p- f# R) O' a
[color=rgba(0, 0, 0, 0.749019607843137)]62
2 d* W6 P2 {9 i* ?5 g, ?[color=rgba(0, 0, 0, 0.749019607843137)]63
& g O% s4 z$ e- N[color=rgba(0, 0, 0, 0.749019607843137)]64+ C( A$ X, g5 M @, A. U
[color=rgba(0, 0, 0, 0.749019607843137)]657 S1 ~8 {! e% d! X) ]- D
[color=rgba(0, 0, 0, 0.749019607843137)]66
" S( K# p& h7 f, {9 J7 e% \- K[color=rgba(0, 0, 0, 0.749019607843137)]67( p2 ?, g% _: l% {
[color=rgba(0, 0, 0, 0.749019607843137)]68+ q+ _& v6 A- A* K# a7 W5 r7 ~3 l
[color=rgba(0, 0, 0, 0.749019607843137)]69
# |6 P% ]# X' |: x[color=rgba(0, 0, 0, 0.749019607843137)]70
# X- \0 \ v% _0 G9 {/ A0 ][color=rgba(0, 0, 0, 0.749019607843137)]713 ], W5 `! Z5 A4 z3 f
[color=rgba(0, 0, 0, 0.749019607843137)]722 s% u2 |* ~# `
[color=rgba(0, 0, 0, 0.749019607843137)]73. B: f' f& |4 n- x- V( k" _
[color=rgba(0, 0, 0, 0.749019607843137)]74/ L$ s+ h" e. ^$ \' H! Z3 G! I' [
[color=rgba(0, 0, 0, 0.749019607843137)]75
0 r9 X8 ~1 [) H: z0 n[color=rgba(0, 0, 0, 0.749019607843137)]76, D: c+ f3 T' f, W
[color=rgba(0, 0, 0, 0.749019607843137)]774 {& x2 K$ S& G9 r- g8 S0 p
[color=rgba(0, 0, 0, 0.749019607843137)]78. V! l W" z" E8 I/ r; G! |
[color=rgba(0, 0, 0, 0.749019607843137)]79& @) D7 y$ }8 j. F. _) q
[color=rgba(0, 0, 0, 0.749019607843137)]80( o/ a4 M8 v9 C% {
[color=rgba(0, 0, 0, 0.749019607843137)]812 F6 f8 N5 o/ H3 W. D5 t: @
[color=rgba(0, 0, 0, 0.749019607843137)]82
( K0 J- t) B( @3 h, [$ _: p[color=rgba(0, 0, 0, 0.749019607843137)]83 I' u4 ?2 x% e
[color=rgba(0, 0, 0, 0.749019607843137)]84
% X9 ?- E2 c5 x[color=rgba(0, 0, 0, 0.749019607843137)]85
, R* L' k/ c9 B6 ?[color=rgba(0, 0, 0, 0.749019607843137)]86
& y6 s) q& n- n9 j1 D; f[color=rgba(0, 0, 0, 0.749019607843137)]87
3 N& u3 ?0 Y; U[color=rgba(0, 0, 0, 0.749019607843137)]88
7 Y7 |( [* C+ ~: |! A% A[color=rgba(0, 0, 0, 0.749019607843137)]893 r* J" D+ [2 y1 n8 J
[color=rgba(0, 0, 0, 0.749019607843137)]90
$ A+ D! k; |: p7 {* n[color=rgba(0, 0, 0, 0.749019607843137)]91
3 b6 N0 v1 C: d( E- T9 X3 q[color=rgba(0, 0, 0, 0.749019607843137)]929 Q! F/ C% H/ A
[color=rgba(0, 0, 0, 0.749019607843137)]93( D. Q2 |8 y% ~) |6 ~2 X& w3 U
[color=rgba(0, 0, 0, 0.749019607843137)]94
u2 }0 `1 l; q[color=rgba(0, 0, 0, 0.749019607843137)]95
% Y7 B& |8 Z' _. X5 i! k t4 t3 O4 M[color=rgba(0, 0, 0, 0.749019607843137)]96
8 j. b3 _& O, K6 c2 t[color=rgba(0, 0, 0, 0.749019607843137)]97. l1 F9 W. I& J' K- l
[color=rgba(0, 0, 0, 0.749019607843137)]98
% U0 V+ [0 e6 R! J6 l[color=rgba(0, 0, 0, 0.749019607843137)]99
! s" Z# y" ]$ w5 G6 Z% `& p[color=rgba(0, 0, 0, 0.749019607843137)]1002 F6 [! |6 h8 J; |3 C
[color=rgba(0, 0, 0, 0.749019607843137)]101 n9 z! v+ O5 ~- @7 F
[color=rgba(0, 0, 0, 0.749019607843137)]102
}/ `6 s y1 O) {5 O[color=rgba(0, 0, 0, 0.749019607843137)]103
8 w$ g0 i2 g, K( z0 ~, R. V0 o[color=rgba(0, 0, 0, 0.749019607843137)]104
7 Y1 d) @8 ]/ U, L9 t$ F* m[color=rgba(0, 0, 0, 0.749019607843137)]105: l# Q7 i$ A; H; a" T s9 M! i, ^
[color=rgba(0, 0, 0, 0.749019607843137)]106
5 a' L5 Q5 m2 `+ v2 Q% y/ z0 w[color=rgba(0, 0, 0, 0.749019607843137)]107
2 O' L: S% {* m: n% T[color=rgba(0, 0, 0, 0.749019607843137)]108
$ o# L4 Y, ]! \* V5 {. C+ x[color=rgba(0, 0, 0, 0.749019607843137)]109
4 n. @" S6 g3 `( K8 J$ ` S9 W) n[color=rgba(0, 0, 0, 0.749019607843137)]110$ b2 ?6 H; L% ~( ^
[color=rgba(0, 0, 0, 0.749019607843137)]111
2 ^0 y8 G, c4 W* Q[color=rgba(0, 0, 0, 0.749019607843137)]测试结果：
' U8 u) W! ]' L/ J+ g. S/ p[color=rgba(0, 0, 0, 0.749019607843137)]
9 F7 {/ f' U! A# ^* L$ X O$ h9 p1 e$ L
[color=rgba(0, 0, 0, 0.749019607843137)]; {+ I; m" d' a. T6 `- v9 D
9 W) p* Z; z9 Q, [$ J+ ]3 Y. P+ M
[color=rgba(0, 0, 0, 0.749019607843137)]2.2计算二叉树的大小* y8 s, o3 l& |; T
[color=rgba(0, 0, 0, 0.749019607843137)]时间复杂度为O(N)
; B' ?- z! ?; P- }[color=rgba(0, 0, 0, 0.749019607843137)]9 |8 y4 ?; X5 W5 x
/ y! H2 C4 c2 B6 W5 b: N5 t2 r[color=rgba(0, 0, 0, 0.749019607843137)]//二叉树的大小
6 Z) \7 \/ U Z G A- j/ e8 K[color=rgba(0, 0, 0, 0.749019607843137)]//法一：全局变量$ M! D6 J7 B7 i: y' l) p
[color=rgba(0, 0, 0, 0.749019607843137)]//int count = 0;& I% |4 x7 J$ p( |4 J
[color=rgba(0, 0, 0, 0.749019607843137)]//void TreeSize(BTNode* root)
8 k3 j# l; W+ j2 A6 b7 P$ F7 T- y[color=rgba(0, 0, 0, 0.749019607843137)]//{+ _ v1 Y4 q' y4 R |; z2 f
[color=rgba(0, 0, 0, 0.749019607843137)]// if (root == NULL)
$ u' `4 R# l! V- Z[color=rgba(0, 0, 0, 0.749019607843137)]// {
5 w3 ?' {: F$ \, `7 a- k[color=rgba(0, 0, 0, 0.749019607843137)]// return;8 g; A+ q: a" M4 X
[color=rgba(0, 0, 0, 0.749019607843137)]// }! }; c: z! h0 {1 M
[color=rgba(0, 0, 0, 0.749019607843137)]// count++;
8 m8 A8 v( q% e, R; r[color=rgba(0, 0, 0, 0.749019607843137)]// TreeSize(root->left);
1 j+ O2 [8 \, J) l* X" \[color=rgba(0, 0, 0, 0.749019607843137)]// TreeSize(root->right);4 W: A- s2 P& c0 \. z5 C0 K* p
[color=rgba(0, 0, 0, 0.749019607843137)]//6 Z! |( K- H N3 d
[color=rgba(0, 0, 0, 0.749019607843137)]// return;//函数栈帧层层返回，最后回到根节点1，结束了1的右子树函数，什么都不返回，因为count是全局变量
8 z! Z& ^9 E7 j o: E3 K5 m3 E! Z[color=rgba(0, 0, 0, 0.749019607843137)]//}
* v3 T, x; D; H* \% F[color=rgba(0, 0, 0, 0.749019607843137)]//法二：子问题思路：分而治之( P* p- N4 p: A' G; S
[color=rgba(0, 0, 0, 0.749019607843137)]int TreeSize(BTNode* root)! P7 o5 \/ Q0 {9 F: j! i- P
[color=rgba(0, 0, 0, 0.749019607843137)]{
' I$ ~; h! G. P$ L5 j[color=rgba(0, 0, 0, 0.749019607843137)] return root == NULL ? 0 : TreeSize(root->left) + TreeSize(root->right) + 1;
8 B3 o# k% ^3 ]( Y8 l[color=rgba(0, 0, 0, 0.749019607843137)]}
# E& O s3 x, O1 y T; M9 |[color=rgba(0, 0, 0, 0.749019607843137)]1
8 Q( k7 o# m5 {. l6 R F/ f# F[color=rgba(0, 0, 0, 0.749019607843137)]2
- z* f" v8 G5 D[color=rgba(0, 0, 0, 0.749019607843137)]3
8 `% K3 w! ]) j8 h[color=rgba(0, 0, 0, 0.749019607843137)]4
9 H* I. D$ O3 N0 C% ]. d" a[color=rgba(0, 0, 0, 0.749019607843137)]5
1 x! i4 ?9 W @. I9 _[color=rgba(0, 0, 0, 0.749019607843137)]6
1 W+ } }% K' v; Z% u. S! k[color=rgba(0, 0, 0, 0.749019607843137)]7
! u: Y* r( O8 u2 ~[color=rgba(0, 0, 0, 0.749019607843137)]8
0 L: u$ S7 L% l[color=rgba(0, 0, 0, 0.749019607843137)]9! B) X+ a" T5 l! k
[color=rgba(0, 0, 0, 0.749019607843137)]10
. N1 [1 D. S) j- u0 `9 L" a8 p[color=rgba(0, 0, 0, 0.749019607843137)]11
$ a, g! i. x( E% C[color=rgba(0, 0, 0, 0.749019607843137)]12+ | t6 z7 v- Z2 O/ o/ H( Z( \9 r/ I
[color=rgba(0, 0, 0, 0.749019607843137)]131 i# ] L4 @% F! O
[color=rgba(0, 0, 0, 0.749019607843137)]146 {6 w0 ?) U) G* J$ W1 [" {
[color=rgba(0, 0, 0, 0.749019607843137)]15' H3 a% E& H9 b! {7 ?2 {
[color=rgba(0, 0, 0, 0.749019607843137)]16& n w3 o/ G a2 B/ L) N& g4 j
[color=rgba(0, 0, 0, 0.749019607843137)]17
5 V+ \7 ~& W/ z[color=rgba(0, 0, 0, 0.749019607843137)]182 @/ f# V- v6 Y1 Z2 q
[color=rgba(0, 0, 0, 0.749019607843137)]19
3 o' Q6 j0 B, \7 G; t8 H[color=rgba(0, 0, 0, 0.749019607843137)]203 p& v9 i0 c7 {& u& N* l* g: l
[color=rgba(0, 0, 0, 0.749019607843137)]2.3计算二叉树叶子结点的个数
& I4 ]6 N* i3 W: e# |( v7 m! _[color=rgba(0, 0, 0, 0.749019607843137)]//计算二叉树叶子结点的个数/ T2 @: K1 R& b4 b2 @" t7 a
[color=rgba(0, 0, 0, 0.749019607843137)]int TreeLeafSize(BTNode* root)
6 l+ N$ n! C4 z6 |7 k8 G% }2 ^[color=rgba(0, 0, 0, 0.749019607843137)]{0 _$ l I Q0 y U) _4 ]6 e" ~$ h- u
[color=rgba(0, 0, 0, 0.749019607843137)] if (root == NULL)//首先得考虑空树的情况,0个叶子结点/ H9 u! k9 N. s
[color=rgba(0, 0, 0, 0.749019607843137)] {
! d0 E& w$ C# j! {: i& C[color=rgba(0, 0, 0, 0.749019607843137)] return 0;
$ k1 k. ]2 M1 [[color=rgba(0, 0, 0, 0.749019607843137)] }7 T+ c: I5 k% g- H w; b
[color=rgba(0, 0, 0, 0.749019607843137)] //叶子结点的特征就是左右子树为空
0 m+ f5 [+ i0 [! S[color=rgba(0, 0, 0, 0.749019607843137)] if (root->left == NULL && root->right == NULL)6 b3 h3 \. X5 V' |8 F. J+ G
[color=rgba(0, 0, 0, 0.749019607843137)] {
) j/ P; N, y8 O$ g: r[color=rgba(0, 0, 0, 0.749019607843137)] return 1;
, u% E7 M+ w1 t[color=rgba(0, 0, 0, 0.749019607843137)] }$ g# ~' W$ R' g1 A
[color=rgba(0, 0, 0, 0.749019607843137)] return TreeLeafSize(root->left) + TreeLeafSize(root->right);
) [3 t# [! M7 p; r. @[color=rgba(0, 0, 0, 0.749019607843137)]}
3 c9 N5 |1 r4 s5 o[color=rgba(0, 0, 0, 0.749019607843137)]1
6 o" X$ K; E) N: l[color=rgba(0, 0, 0, 0.749019607843137)]2
9 T: V6 J( u+ O- O7 g3 p$ D. |% E# ?[color=rgba(0, 0, 0, 0.749019607843137)]3% d* r0 n& A! H4 f! P" D
[color=rgba(0, 0, 0, 0.749019607843137)]4
7 J+ b" q! Q1 I/ M1 f& s1 T8 p# H[color=rgba(0, 0, 0, 0.749019607843137)]5& X. @8 J3 x" |% b! v @# b0 b: N
[color=rgba(0, 0, 0, 0.749019607843137)]6
* L6 j# S5 u7 B+ A4 W; w. `[color=rgba(0, 0, 0, 0.749019607843137)]7, a' o' t0 L' T# Q- z
[color=rgba(0, 0, 0, 0.749019607843137)]8* ^1 G; U8 q) y2 ]+ z
[color=rgba(0, 0, 0, 0.749019607843137)]9- m* o( V i A! E1 l
[color=rgba(0, 0, 0, 0.749019607843137)]10
% E3 B/ ^8 C" r& t% h[color=rgba(0, 0, 0, 0.749019607843137)]11
$ ]0 m% w' t/ I% ?* K+ \6 h[color=rgba(0, 0, 0, 0.749019607843137)]12( Z; z; K5 H8 D0 C# X& ]0 y
[color=rgba(0, 0, 0, 0.749019607843137)]13
! k+ y! g% h9 O* ~& w @' N7 b[color=rgba(0, 0, 0, 0.749019607843137)]14# c, @9 b4 \! p N4 L
[color=rgba(0, 0, 0, 0.749019607843137)]2.4计算二叉树的高度& r9 u: h4 F3 t, \
[color=rgba(0, 0, 0, 0.749019607843137)]int TreeHeight(BTNode* root)
, K' k" b% t# p6 ][color=rgba(0, 0, 0, 0.749019607843137)]{
) I( r) `4 b# h/ Q( W6 d& P[color=rgba(0, 0, 0, 0.749019607843137)] //空树高度为0( A, O, ]5 ?; y$ g' O4 _
[color=rgba(0, 0, 0, 0.749019607843137)] if (root == NULL)2 l l3 j. h8 M- O A
[color=rgba(0, 0, 0, 0.749019607843137)] {0 J; g Q# |* J! v
[color=rgba(0, 0, 0, 0.749019607843137)] return 0;/ V, w E- P& c0 [' o8 m' _
[color=rgba(0, 0, 0, 0.749019607843137)] }; _, U0 V9 X' t4 l
[color=rgba(0, 0, 0, 0.749019607843137)] //树的高度是较高的那棵子树# p' Y& I, D2 H3 g$ B7 B+ @
[color=rgba(0, 0, 0, 0.749019607843137)] int lh = TreeHeight(root->left);//左子树的高度
& K3 F! s: l& `; V C[color=rgba(0, 0, 0, 0.749019607843137)] int rh = TreeHeight(root->right);//右子树的高度
3 S6 e! a1 ?! n* K- \7 f+ G2 t[color=rgba(0, 0, 0, 0.749019607843137)]1 z6 C0 }) n4 Z) m# X/ w
* N# U- t! J, N* ?% z
[color=rgba(0, 0, 0, 0.749019607843137)] return lh > rh ? lh + 1 : rh + 1;
, r1 M0 [4 D, J5 H: j[color=rgba(0, 0, 0, 0.749019607843137)]}# c% ]' m# ~. p4 N) k" T3 c
[color=rgba(0, 0, 0, 0.749019607843137)]12 f d; h, Y, W* S+ M
[color=rgba(0, 0, 0, 0.749019607843137)]2
: e! E4 _ D; |$ G. ^- n$ ^[color=rgba(0, 0, 0, 0.749019607843137)]3/ M) G$ L1 k/ \( a, e+ Y( H
[color=rgba(0, 0, 0, 0.749019607843137)]4
$ Q" H( N: x+ a: n[color=rgba(0, 0, 0, 0.749019607843137)]5
9 G4 h' F! c6 w0 r* ]- v7 I9 t& K[color=rgba(0, 0, 0, 0.749019607843137)]6: C1 R0 R S( v
[color=rgba(0, 0, 0, 0.749019607843137)]7
! O( u! w" o, d z Q& Z[color=rgba(0, 0, 0, 0.749019607843137)]8
1 H# Z- O# } T: @! R% |[color=rgba(0, 0, 0, 0.749019607843137)]9
9 |* M/ n' f, K) Z [[color=rgba(0, 0, 0, 0.749019607843137)]10
1 w6 i3 D! U+ H: [" t* K[color=rgba(0, 0, 0, 0.749019607843137)]11
& N% z: @' J# J4 O' m7 ~[color=rgba(0, 0, 0, 0.749019607843137)]12- ~+ i' Q3 B0 a
[color=rgba(0, 0, 0, 0.749019607843137)]13; N+ I4 I7 d7 g% g6 j
[color=rgba(0, 0, 0, 0.749019607843137)]2.5计算第K层结点的个数! }& ?" c4 x7 b% H9 x# @$ H' ^4 d
[color=rgba(0, 0, 0, 0.749019607843137)]
3 q* B* ]& C, P2 A+ t
, l0 `0 v, [: L% y' X0 x[color=rgba(0, 0, 0, 0.749019607843137)]
. c9 W& {% `: k( ~. G9 C& Y7 W c0 I" G. h( K) }, e/ ^
[color=rgba(0, 0, 0, 0.749019607843137)]求第K层的结点个数，转换成求子树第K-1层的结点个数。举个栗子：如果我们要求这棵二叉树第3层的结点个数（为3），就转换成求左子树根结点2的第2层的结点个数+右子树4第二层的结点个数。。。
: m" E! e; m" ?6 `[color=rgba(0, 0, 0, 0.749019607843137)]# u9 F" I+ {2 ~& w6 K7 [( U2 Y
8 Y) d2 }. m: q8 D0 i3 f[color=rgba(0, 0, 0, 0.749019607843137)]//计算第K层结点的个数
4 [+ Y g2 }# Q[color=rgba(0, 0, 0, 0.749019607843137)]int TreeLevel(BTNode* root,int K)
) n( O, O5 k% g3 P$ _[color=rgba(0, 0, 0, 0.749019607843137)]{
! Q9 Z. s5 c) x# |[color=rgba(0, 0, 0, 0.749019607843137)] assert(K > 0);% L4 H/ y: ]1 N0 Y) Y
[color=rgba(0, 0, 0, 0.749019607843137)] if (root == NULL)
# S& J7 d5 ^' q f/ z4 r# ][color=rgba(0, 0, 0, 0.749019607843137)] {
6 I3 w/ O8 W+ k. G6 ]3 W( h1 i9 ~5 A$ [[color=rgba(0, 0, 0, 0.749019607843137)] return 0;8 z$ n9 H6 k2 v0 }: o
[color=rgba(0, 0, 0, 0.749019607843137)] }; X: z9 o3 _ V7 G' L* U
[color=rgba(0, 0, 0, 0.749019607843137)] //如果是第一层(递归出口)
, X0 Y1 h7 p5 \+ [. f/ L |[color=rgba(0, 0, 0, 0.749019607843137)] if (K == 1). ]2 l0 H: L/ q. V
[color=rgba(0, 0, 0, 0.749019607843137)] {' b- K) f" @* m& T
[color=rgba(0, 0, 0, 0.749019607843137)] return 1;
) c3 [) S1 _$ Y! Q4 n z[color=rgba(0, 0, 0, 0.749019607843137)] }
# W5 u- A. m1 W, u& ^6 ]; S! q6 V8 P[color=rgba(0, 0, 0, 0.749019607843137)] //转换成子树的第K-1层" G! |. c5 l2 V# D0 D/ L
[color=rgba(0, 0, 0, 0.749019607843137)] return TreeLevel(root->left,K-1) + TreeLevel(root->right,K-1);, i9 ?# H# }2 J7 ]
[color=rgba(0, 0, 0, 0.749019607843137)]}
; {( s _7 g* J- D4 G* s9 ^) L* u, l: ~[color=rgba(0, 0, 0, 0.749019607843137)]1! ]2 L+ R" z; @7 m9 P
[color=rgba(0, 0, 0, 0.749019607843137)]29 I1 q0 l* c# ?2 _6 j1 {, C& W4 p$ M
[color=rgba(0, 0, 0, 0.749019607843137)]3
; O. y: H/ \5 i& H! s[color=rgba(0, 0, 0, 0.749019607843137)]4) T H' F" r/ y& I; B0 S% Z
[color=rgba(0, 0, 0, 0.749019607843137)]5* r$ N) F3 ?/ ^! \0 q# u
[color=rgba(0, 0, 0, 0.749019607843137)]6
2 ^3 \' o6 j# a! M$ w1 ~8 Z; e5 \9 I[color=rgba(0, 0, 0, 0.749019607843137)]7
& H, X5 \& k8 @8 F( ^ K[color=rgba(0, 0, 0, 0.749019607843137)]8
9 Z- k0 X- C+ x6 S& q7 U[color=rgba(0, 0, 0, 0.749019607843137)]9$ s; s8 ~3 Q: F" G8 w
[color=rgba(0, 0, 0, 0.749019607843137)]10
- [7 H3 R( A5 y) t) l' S[color=rgba(0, 0, 0, 0.749019607843137)]11$ G; ^3 b( I4 J+ u x0 {
[color=rgba(0, 0, 0, 0.749019607843137)]12
$ u5 j1 W' {3 R; h$ u0 K# `[color=rgba(0, 0, 0, 0.749019607843137)]13
7 F- Y) l$ Z _- l[color=rgba(0, 0, 0, 0.749019607843137)]14
& j6 A( L: C& J) T[color=rgba(0, 0, 0, 0.749019607843137)]15" B l ]6 o c; V) k6 u/ s( X
[color=rgba(0, 0, 0, 0.749019607843137)]169 v) @3 ~$ B0 S! }+ \/ ~
[color=rgba(0, 0, 0, 0.749019607843137)]2.6二叉树查找; c- Z" p, ]7 Y6 S& o0 d3 _% b
[color=rgba(0, 0, 0, 0.749019607843137)]//二叉树查找% H7 K' U% C/ ^" k0 P* V
[color=rgba(0, 0, 0, 0.749019607843137)]BTNode* TreeFind(BTNode* root, BTDataType data)& y5 t' s8 v. c8 A- F
[color=rgba(0, 0, 0, 0.749019607843137)]{
! Z" `6 p9 {$ U/ j$ q, M; Q[color=rgba(0, 0, 0, 0.749019607843137)] if (root == NULL)
; E0 T/ `& M. N* g, V[color=rgba(0, 0, 0, 0.749019607843137)] {
8 ]4 j6 t& {' X[color=rgba(0, 0, 0, 0.749019607843137)] return NULL;: J! k* z# s4 `( B/ b7 L
[color=rgba(0, 0, 0, 0.749019607843137)] }
. m2 d& c5 @% u* w8 r# v; i/ l, t& S) @6 w[color=rgba(0, 0, 0, 0.749019607843137)] if (root->data == data)3 s+ U: o2 _8 ~% t# ]
[color=rgba(0, 0, 0, 0.749019607843137)] {
_ R7 L- `: C9 X5 w z[color=rgba(0, 0, 0, 0.749019607843137)] return root; |% v I/ @' P8 q& q7 _" E
[color=rgba(0, 0, 0, 0.749019607843137)] }
; G$ P8 {1 h5 `& [" Z' ?7 `# b$ g[color=rgba(0, 0, 0, 0.749019607843137)] //先查找左子树
: X5 `) i- `0 D! A5 v- L[color=rgba(0, 0, 0, 0.749019607843137)] BTNode* lret = TreeFind(root->left, data);
2 ~& h8 i8 v" ?( Z( Q[color=rgba(0, 0, 0, 0.749019607843137)] if (lret)' O- }5 i( M* P. {: R5 F; r
[color=rgba(0, 0, 0, 0.749019607843137)] return lret;+ `. u3 L) H4 h; Z, u$ a4 L' Q
[color=rgba(0, 0, 0, 0.749019607843137)] //再查找右子树2 [0 L. n3 ]9 ^' F' e# L
[color=rgba(0, 0, 0, 0.749019607843137)] BTNode* rret = TreeFind(root->right, data);2 L1 g. g+ {/ o/ N6 u
[color=rgba(0, 0, 0, 0.749019607843137)] if (rret) k( ^- i! Y5 `; T, s3 d
[color=rgba(0, 0, 0, 0.749019607843137)] return rret;* f$ k: f1 D" f" Q; B
[color=rgba(0, 0, 0, 0.749019607843137)] return NULL;
8 u6 z- y1 ^% h! ~9 U0 r H[color=rgba(0, 0, 0, 0.749019607843137)]}
: t3 S$ V$ S( m, F) J3 m[color=rgba(0, 0, 0, 0.749019607843137)]————————————————1 f& \6 ^& }; t- e5 V4 b! D% H
[color=rgba(0, 0, 0, 0.749019607843137)]版权声明：本文为CSDN博主「SouLinya」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。, s2 e% j: {6 M9 k/ l. M. w
[color=rgba(0, 0, 0, 0.749019607843137)]原文链接：https://blog.csdn.net/weixin_63449996/article/details/126841212
) X. Y, M7 b, o, v7 A
7 e5 B7 `2 Z9 f) l8 b$ V
0 N: K* G1 i3 D, Y; p[color=rgba(0, 0, 0, 0.75)]
4 v: v9 Z8 A! Z [, U, ]
: Q3 ?9 u# N& T! i a6 E
0 `' T; `# e6 t' n( X) L+ D
# {, S) m. S* D, l |
IP卡
狗仔卡
发表于 2022-9-15 11:55
转播
淘帖
分享
收藏
支持
反对
微信
提升卡
置顶卡
沉默卡
喧嚣卡
变色卡
抢沙发
显身卡
