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