求树的节点个数求法，求助啊！！！

qiandongdong

求树的节点个数的求法啊或matlab代码，我是新手，真心编了好久没结果。请前辈们帮帮忙啊~

madio

就是一个遍历树的所有节点的算法，我帮你找到一个

1. 首先需要定义树的存储。如果是C实现，应该是链表实现，每个节点用四个属性标志：2 c. c7 k* x7 D/ V# n1 [; s
   
2.        tree_nodename：节点名字或序号$ u/ I! [; I' E& N+ [# d
   
3.        tree_nodevalue：节点对应的值
   ( m( u& Y) ^: l* r3 d9 l
4.        tree_nodefather：节点父亲，如果没有父亲，值为空
   - G9 @/ N. D7 ~, ~$ s8 i0 o
5.        tree_nodeson：节点的第一个儿子（最左边），如果没有儿子，值为空
   1 `) a1 R! u* ?
6.        tree_nodeneighbor：节点的右边兄弟，如果右边没有兄弟，值为空' L( ~, p\" ?& z
   
7.        树的搜索，因为不限制搜索顺序，这里使用深度优先。不用递归，可以用栈实现。0 W; d) V# U1 T+ N3 @
   
8. ! r: e1 U9 K& y- p\" R0 H
   
9.        刚学了点matlab，就使用matlab实现。Matlab中没有链表的概念，用数组实现。
   ' |\" ]9 j0 n) ?  f$ Y! I- _- `
10. 
    + }5 A5 v, |* b6 ]9 K0 F
11.        %matlab源程序. r. Q1 y4 n$ Z
    
12.        %输入：树的深度、树的广度、搜索的值
    ) {( i3 S& R5 c8 I! p( Z
13.        %返回：树中接近的值、节点名字，如果没有接近的值，节点名字为空+ g1 ~, r9 f0 X' o* S( `
    
14.        function[valueintree, nodeintree] = tree(tree_depth, tree_width, seek_value)
    / H& {\" Y' [/ m  G9 u5 Y2 q/ h
15.        %根据树的深度、节点的儿子数量计算树总的节点个数
    ! n$ s6 C; ?\" X, u4 P
16.        node_num = 0;0 t, B' g, J6 G4 Z5 e9 ^; h7 B5 o
    
17.        for n= 0 : (tree_depth-1)
    $ e& k) l\" w: R+ R& g( X
18.               node_num = node_num + tree_width ^ n;, c, Q6 h& \- a9 H( X7 }
    
19.        end4 x3 E5 Q+ M+ [- a) i) z
    
20. 9 I\" D8 Y( n% ]8 K8 j$ B% Y0 I& j
    
21.        %为树的存储空间赋值2 Y2 U: |6 {$ ^6 A1 `
    
22.        %node name，按照广度优先为节点排号
    4 _6 P: n: B' Q) a  u
23.        tree_nodename = (1 : node_num);
    2 k5 I! H\" F0 k9 }& O1 g! x7 p
24.        %node value  {  |! a6 P& p) O1 \# f, i( z
    
25.        tree_nodevalue = rand(1 : node_num);: c\" V8 u+ f. F, Y7 _1 O% c
    
26.        %node father and son
    ; k  c0 i. u2 X9 i
27.        tree_nodefather(1) = 0;
    , _' b5 ?\" o$ F3 q0 F! s3 Q* k' g
28.        tree_nodeson = zeros(1, node_num);
    5 Q\" s3 p1 w4 s7 j( w! t. A$ e
29.        n = 2;
    ' n. }) m9 P% ~\" e; z+ d\" V  [9 E
30.        k = 1;
    9 J$ ]9 h5 x/ q2 j- r2 U
31.        while n <= node_num8 V1 \6 L2 w4 z- w* K( E9 L# e, o
    
32.               for m = 1 : tree_width6 W7 T# [% L0 T7 d. X( l- ]% b% _
    
33.                      tree_nodefather(n) = k;/ c$ |8 n$ }( ^: R4 x1 i
    
34.                      if m==1
    ! q* ^$ U. E0 P4 ?+ X9 `6 b
35.                             tree_nodeson(k) = n;
    : z0 ?9 p0 L' m' f& T
36.                      end5 G: `& B. \# c* a
    
37.                      n = n + 1;0 u& [+ s! S. w
    
38.               end+ m: X! @, ]% s7 S5 _( l* q
    
39.               k = k + 1;
    1 L. e: b' L1 Y% c# t
40.        end
    / j* c: v\" p$ I; r9 g+ S- S6 H
41.        %node neighbor7 [) J% H# f$ `7 v; K2 p! n
    
42.        tree_nodeneighbor(1) = 0;
    * ]9 r0 ?7 ^6 h1 R( J
43.        n = 2;
    6 c* \+ Y9 u, [+ D& q\" Z+ |! w
44.        while n <= node_num
    5 S8 b/ T+ H/ w. u& g) o
45.               for m = 1 : tree_width% ]' ~2 K; Q7 K6 u1 L
    
46.                      if m ==tree_width1 u- N0 A9 ~5 ~- E  u( ^3 n
    
47.                             tree_nodeneighbor(n) = 0;% N. c3 }8 A0 y( X
    
48.                      else
    . Z) m* K+ V/ Z9 {: Z2 w! X
49.                             tree_nodeneighbor(n) = n + 1;: y+ U7 A; O, W% V% Z  @
    
50.                      end4 v$ A5 I5 l9 h9 c) O1 Y\" K$ o% m\" P
    
51.                      n = n + 1;5 M- M\" y9 G7 P\" V2 S
    
52.               end' q  a. ^+ R: `5 j& _
    
53.        end7 z) i; K9 c8 \3 c
    
54. 
      s8 ?/ F* [- |\" W: S9 N' g, K9 G
55.        %下面是有效程序段，用栈实现( _' n6 V7 \; z9 }! X. h
    
56.        stack = zeros(1, tree_depth);! R3 V8 E$ o' h* J/ E; _' E\" ^2 v, {
    
57.        nodeinstack = zeros(1, node_num);
    ' m; O# K# _1 G8 h* z+ N
58.        stack_ptr = 1;9 H! ^* s! x' C' C: g7 c% U# Z; m$ v
    
59.        stack(1) = 1;
    % K\" L2 B+ }. g7 h. ^
60.        nodeinstack(1) = 1;: I! ~* {- n. ^' J5 z& b9 b
    
61.        valueintree = seek_value;+ ~: n: _3 r$ z7 ^' u5 ~
    
62.        nodeintree = 0;+ t& |4 L& P. ?3 V7 y
    
63. ' O! I3 {, ?- \0 y
    
64.        while stack_ptr > 0
    \" z) o7 S1 C  p0 Y( Q
65.               n = stack(stack_ptr);( ?2 _+ Q0 f+ P0 |/ U8 o9 W
    
66.               if abs(tree_nodevalue(n) – seek_value) < 1e-3
    6 l5 K8 R9 P1 t
67.               %如果搜索到值，返回
    7 r2 }9 N/ J8 y, t
68.                      valueintree = tree_nodevalue(n);
    . h+ _$ O+ K' T
69.                      nodeintree = tree_nodename(n);5 R4 ]6 G' y; ]( H' N
    
70.                      break;
    4 o& `# {- I% E/ ^
71.               end4 w  o/ `3 i/ }: V% |! a: ~. E
    
72. 
    & i- W) X6 t3 k& |; w
73.               if tree_nodeson(n) ~= 0 & nodeinstack(n) == 1& F. n- @! p5 n$ c# @# c0 F
    
74.               %如果节点有儿子，并且第一次入栈，将儿子节点入栈
    8 T8 n7 ~8 w9 |4 R# t. z3 @! x
75.                      stack_ptr = stack_ptr + 1;3 j3 S- g* }( x  [; c
    
76.                      m = tree_nodeson(n);7 H7 t! ]4 ^3 v$ H% a
    
77.                      stack(stack_ptr) = m;9 @. Y/ t; b3 D/ M4 a& h
    
78.                      nodeinstack(m) = nodeinstack(m) + 1;0 h2 s+ a8 D; A9 @
    
79.               elseif tree_nodeneighbor(n) ~= 06 Y0 M! l: E. r! m, O9 @
    
80.               %否则，如果节点右边有兄弟，节点出栈，然后将右边兄弟入栈
    & |! |9 b  Q2 F. [0 F' f7 l
81.                      m = tree_nodeneighbor(n);$ S4 W- H3 ?- @6 Y1 f
    
82.                      stack(stack_ptr) = m;
    & |. z* Y) I4 V( E9 D# z0 J
83.                      nodeinstack(m) = nodeinstack(m) + 1;\" R\" Q5 c8 L0 N
    
84.               else
    ( W' A4 e( x7 u! t. r5 ]
85.               %再否则，出栈，然后将父亲节点的入栈次数加一
    * }$ h5 G$ I4 K9 _
86.                      stack_ptr = stack_ptr - 1;
    \" B5 E( e  x2 l7 T1 h6 M
87.                      m = stack(stack_ptr);7 N$ T- M5 `% h7 G; S
    
88.                      nodeinstack(m) = nodeinstack(m) + 1;  `5 i$ x6 M! P7 o+ A
    
89.               end
    ) x\" t8 X( z) g; C) s  Y# J
90.        end

复制代码