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

qiandongdong

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

madio

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

1. 首先需要定义树的存储。如果是C实现，应该是链表实现，每个节点用四个属性标志：) w  g- B; F5 r  e\" U( n
   
2.        tree_nodename：节点名字或序号7 V\" J0 k2 a6 ]* n4 J
   
3.        tree_nodevalue：节点对应的值5 n\" ?; M$ J: ~
   
4.        tree_nodefather：节点父亲，如果没有父亲，值为空
   1 D  h6 k% Q5 i2 |, m
5.        tree_nodeson：节点的第一个儿子（最左边），如果没有儿子，值为空
   ; K1 P: d8 t( I$ S\" c3 s, M
6.        tree_nodeneighbor：节点的右边兄弟，如果右边没有兄弟，值为空9 y' Y/ c& ^8 N2 \
   
7.        树的搜索，因为不限制搜索顺序，这里使用深度优先。不用递归，可以用栈实现。
   $ i0 B) i8 s8 {
8. 
   5 f6 x5 y) Y' M
9.        刚学了点matlab，就使用matlab实现。Matlab中没有链表的概念，用数组实现。
   \" S2 n. y. O, s0 B, t  g
10. 
    ! @) p2 m* g$ ?( q% p: u
11.        %matlab源程序6 ^) u, Y% o3 @9 K7 Z7 Q
    
12.        %输入：树的深度、树的广度、搜索的值
    6 ]/ O/ B7 n$ S
13.        %返回：树中接近的值、节点名字，如果没有接近的值，节点名字为空: s0 o/ ?\" U9 s. e# N( ~$ u
    
14.        function[valueintree, nodeintree] = tree(tree_depth, tree_width, seek_value)
    # @' R5 p. O# J\" Z
15.        %根据树的深度、节点的儿子数量计算树总的节点个数/ {& z\" D/ E2 ^, \. b0 @
    
16.        node_num = 0;
    1 h- \, o( c- a% n* s' ?
17.        for n= 0 : (tree_depth-1)8 F  Y# B& \4 P; r& u& s
    
18.               node_num = node_num + tree_width ^ n;
    4 ^- O3 ]6 D  H) d$ J
19.        end1 ]) i7 O4 `( M) I1 C' x0 }' _5 S
    
20. # [: x0 T; Z' I/ U8 n
    
21.        %为树的存储空间赋值
    * y2 S$ g2 r& _1 q
22.        %node name，按照广度优先为节点排号
    + H9 R; C6 S' _# t- X, ?3 b- E
23.        tree_nodename = (1 : node_num);
    3 [( I8 Z+ I% ?: o/ p0 A1 Z
24.        %node value8 a7 e& K+ V/ v+ ]7 n. Y5 q
    
25.        tree_nodevalue = rand(1 : node_num);
    2 _# j# b) u9 c- B. M- M$ ~
26.        %node father and son
      l, ]! d* W: h, H
27.        tree_nodefather(1) = 0;
    6 v; J3 C& T4 }
28.        tree_nodeson = zeros(1, node_num);
    $ O8 J0 \9 X7 j! ?# |
29.        n = 2;
    . i8 q$ D* b* z; M9 T. ~& [
30.        k = 1;/ O& u: G\" Q9 `& L# }0 u
    
31.        while n <= node_num
    # t2 Z) L( C8 h* n1 \; `
32.               for m = 1 : tree_width
    * S* P3 k/ Q5 U% q
33.                      tree_nodefather(n) = k;
    4 W: M+ V8 k1 t# W; g$ ]0 o, y
34.                      if m==1
    ! f% Q7 X! {/ f* K9 D6 E6 ]
35.                             tree_nodeson(k) = n;/ Q8 k4 w9 L: H- H2 T* g
    
36.                      end
    , q9 {1 u8 E; H& R6 B; p
37.                      n = n + 1;
    5 ]* q: @, k/ I; g3 U6 ^- P9 F
38.               end
    2 P% M7 m  N5 d7 h# [2 r
39.               k = k + 1;
      M# b2 D# c& \. S
40.        end
    3 ~& u; r6 K: ]3 g$ p' }
41.        %node neighbor1 }; w2 h: M( s) h4 x0 L5 x
    
42.        tree_nodeneighbor(1) = 0;
    $ M  v3 |! i9 h
43.        n = 2;
    3 B: l- q6 @3 ?5 ~
44.        while n <= node_num5 B# J, r3 ?. C* G# I
    
45.               for m = 1 : tree_width
    - ]! }' I. c8 _: o4 I
46.                      if m ==tree_width; p& u- z3 U# ~% w! Z
    
47.                             tree_nodeneighbor(n) = 0;5 C# l* n9 |3 ~5 n* t. J0 V
    
48.                      else3 G& D# B  o! |
    
49.                             tree_nodeneighbor(n) = n + 1;) r5 V6 o% r\" A$ M/ R# L
    
50.                      end
    ; E# ?\" a8 E1 Z4 h8 S+ P' U
51.                      n = n + 1;
    0 t3 G0 E+ `5 n- ~2 {# a& E$ h
52.               end8 B1 X6 m3 ]0 c- Q) N6 P
    
53.        end
    / D4 o' v' j. c
54. 
    # J, _/ ^9 V0 G/ ]2 j
55.        %下面是有效程序段，用栈实现, o: y& Q0 ~6 E  m  }* z
    
56.        stack = zeros(1, tree_depth);
    + l1 q' ^7 U9 R5 w) [( J; U0 Q
57.        nodeinstack = zeros(1, node_num);
    4 |* G* Y4 @7 \, r, B
58.        stack_ptr = 1;. G7 C9 D. B) O; m+ ]
    
59.        stack(1) = 1;
    ! X; e' P6 c+ |/ W; I9 ^% w& r\" `
60.        nodeinstack(1) = 1;# U\" V% N$ |8 X4 b
    
61.        valueintree = seek_value;0 o& i4 y# {2 _: I) {# D6 n% v
    
62.        nodeintree = 0;! v9 [' c$ Z* q/ U7 `\" F
    
63. 
    \" ~! N* _6 G- m+ d( I4 c
64.        while stack_ptr > 02 c, K6 F( C, D
    
65.               n = stack(stack_ptr);
    + H4 V- \\" J( {6 r* n
66.               if abs(tree_nodevalue(n) – seek_value) < 1e-3
    / T: `8 D* _. d0 L7 G
67.               %如果搜索到值，返回
    $ v: G( n. i- ~; F  t, W7 V\" X7 ^
68.                      valueintree = tree_nodevalue(n);1 |! B7 X9 N0 T& O% \1 J1 {4 K
    
69.                      nodeintree = tree_nodename(n);* t/ A. s5 g- U
    
70.                      break;5 X, S: K  f( K- h$ G+ s# Y8 P2 A' O
    
71.               end
    4 ~2 b- J# ]7 i) K\" ^, s1 {( i) F& B0 K' h
72. 
    8 O; @& Y6 w7 R2 k. a3 Q
73.               if tree_nodeson(n) ~= 0 & nodeinstack(n) == 1
    7 S6 A) u$ K& S5 z2 B
74.               %如果节点有儿子，并且第一次入栈，将儿子节点入栈* i' M% j8 i! C7 I) b
    
75.                      stack_ptr = stack_ptr + 1;
    : [, l9 q! e$ l/ \' i0 ?
76.                      m = tree_nodeson(n);
    * ]1 q; V. N+ E3 u# d: J
77.                      stack(stack_ptr) = m;$ Y, x) m9 @# }: c3 Z0 w3 ?6 |
    
78.                      nodeinstack(m) = nodeinstack(m) + 1;; W$ |  a7 {' ]# [& f
    
79.               elseif tree_nodeneighbor(n) ~= 08 O; \* F, y/ |\" y
    
80.               %否则，如果节点右边有兄弟，节点出栈，然后将右边兄弟入栈. x. M- J. ?( J) b- v4 p0 _
    
81.                      m = tree_nodeneighbor(n);
    ( {3 q$ ^5 N' S& D' ]6 a: B: E) @+ y
82.                      stack(stack_ptr) = m;. u1 H' |; t8 e6 |' K
    
83.                      nodeinstack(m) = nodeinstack(m) + 1;
    ! V% F4 f& j5 `7 C7 k/ A1 D: y
84.               else
    ; b0 f  [! u+ {2 Z2 j/ G6 [
85.               %再否则，出栈，然后将父亲节点的入栈次数加一% |. L, S9 X$ Q: H) G+ l
    
86.                      stack_ptr = stack_ptr - 1;2 t3 [/ F1 O. W: p7 R* c* r3 i
    
87.                      m = stack(stack_ptr);' m* ^4 D+ Y# O$ g( Y
    
88.                      nodeinstack(m) = nodeinstack(m) + 1;/ U! U8 B\" }: P) i% Z% }+ ^2 I
    
89.               end
    4 p) A' ], ~8 w5 c: u0 \3 R
90.        end

复制代码