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