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

qiandongdong

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

madio

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

1. 首先需要定义树的存储。如果是C实现，应该是链表实现，每个节点用四个属性标志：! m3 @4 |/ e; Y( H
   
2.        tree_nodename：节点名字或序号5 K& d5 ]\" [0 b- y! a
   
3.        tree_nodevalue：节点对应的值
   & K) E% {/ o$ c8 f
4.        tree_nodefather：节点父亲，如果没有父亲，值为空$ t& o1 {$ f0 z( @& ], C
   
5.        tree_nodeson：节点的第一个儿子（最左边），如果没有儿子，值为空) C( ^  C2 U  r% _& V5 I
   
6.        tree_nodeneighbor：节点的右边兄弟，如果右边没有兄弟，值为空
   : j: O& }4 Z5 F8 [4 [
7.        树的搜索，因为不限制搜索顺序，这里使用深度优先。不用递归，可以用栈实现。( U$ T( F* n- f
   
8. 4 ?# d. C. H' R
   
9.        刚学了点matlab，就使用matlab实现。Matlab中没有链表的概念，用数组实现。4 P& d* |' l% ~2 p7 G
   
10. 
    7 L; B) u9 d. Y4 o! z% n
11.        %matlab源程序
    : E* W! W* A+ u4 \
12.        %输入：树的深度、树的广度、搜索的值
    & d! A: _: r8 n  x4 z; @  M( W9 \
13.        %返回：树中接近的值、节点名字，如果没有接近的值，节点名字为空# Z# ]& m* ?/ {8 n# w# g
    
14.        function[valueintree, nodeintree] = tree(tree_depth, tree_width, seek_value)
    7 y6 |; f; P% q' O) d
15.        %根据树的深度、节点的儿子数量计算树总的节点个数
    % Z0 j* t6 m; O# E% P% q
16.        node_num = 0;* @  L& }2 ^4 o
    
17.        for n= 0 : (tree_depth-1)* E' `3 d1 M4 Z8 n( i9 r/ \
    
18.               node_num = node_num + tree_width ^ n;- P% A7 N. A$ C
    
19.        end3 ^% I3 {+ L  K) A& R+ U
    
20. * `7 ^1 a7 P$ o( u1 r+ J- F8 ?
    
21.        %为树的存储空间赋值
    4 {: {/ v* {3 f8 s! n
22.        %node name，按照广度优先为节点排号5 l% g8 p4 d2 N
    
23.        tree_nodename = (1 : node_num);' ]2 ~) u0 h# @6 K3 U1 v/ x
    
24.        %node value
    ( ?. _6 S7 k0 t( J0 E. E; g& i
25.        tree_nodevalue = rand(1 : node_num);
      S+ z* R9 q6 N/ Q, s
26.        %node father and son3 |8 f; @* |  h9 B! z; L) t
    
27.        tree_nodefather(1) = 0;5 J3 P! n8 c5 }
    
28.        tree_nodeson = zeros(1, node_num);
    9 ^9 t# |$ ^- t4 y) C, f& a- I! F
29.        n = 2;
    5 C& v) T* Z6 N% \& {( R( n
30.        k = 1;
    % x: m5 x/ R+ B- e9 [% \4 N1 l
31.        while n <= node_num\" `' M( O% D6 {\" u: M1 [$ U3 r/ H! d
    
32.               for m = 1 : tree_width
      x3 h$ _! e3 O* L
33.                      tree_nodefather(n) = k;
    ( s: A7 R5 _4 S7 V, j: G
34.                      if m==1
    8 t* n: e6 z. t4 M& ]. D1 g2 |
35.                             tree_nodeson(k) = n;6 l2 f& ], g4 r8 _
    
36.                      end2 I1 _3 W4 Y. |- F. r* F
    
37.                      n = n + 1;
    ! J1 F\" i7 f. `0 D  c
38.               end
    $ X0 a1 Q8 e  M$ c5 H
39.               k = k + 1;' M0 z, p2 C5 x$ K$ f# H
    
40.        end
    6 m- K1 ?% W# R0 N  D. s0 F
41.        %node neighbor
    # r' _  c& ~. t. W3 Y
42.        tree_nodeneighbor(1) = 0;8 a, E* j1 l+ f6 m* P) r' x
    
43.        n = 2;
    & a! ?- _: l3 m0 A+ |: z
44.        while n <= node_num. `$ b# |9 ]2 L6 \% k8 f1 A% J
    
45.               for m = 1 : tree_width
    ( \+ Y5 p3 L; v( M6 z
46.                      if m ==tree_width
    5 h: \! t7 n# p' s' ^& w
47.                             tree_nodeneighbor(n) = 0;# Z- ~\" w- v5 X
    
48.                      else- @, t2 u$ D1 N. h6 j
    
49.                             tree_nodeneighbor(n) = n + 1;
      u( t) L5 R; m
50.                      end
    & C- ^% X8 J& ^: }! l; t
51.                      n = n + 1;; K+ h/ y3 q- B3 ^
    
52.               end
    0 t8 p% X0 u* ^: u
53.        end
    7 ?4 e2 c) S  ~  h0 i+ |- L
54. 0 L0 D\" T8 _1 B( T
    
55.        %下面是有效程序段，用栈实现
    $ f+ _* ]! V4 o  A: _8 _) Z
56.        stack = zeros(1, tree_depth);
    3 H8 V! T* V0 P
57.        nodeinstack = zeros(1, node_num);4 j/ T4 G- M7 o  T# r
    
58.        stack_ptr = 1;
    * S6 U1 x0 H$ s  h1 D* q
59.        stack(1) = 1;
    - c9 k6 ?& L& X2 H0 F
60.        nodeinstack(1) = 1;7 X! ~7 z3 l1 D8 h% P! ]+ o
    
61.        valueintree = seek_value;! G3 G! [6 H9 e- g* q! E! W
    
62.        nodeintree = 0;+ }3 h0 p; Q( F/ D\" z/ d
    
63. 
    - {8 r: n/ i, A8 g& @
64.        while stack_ptr > 0) Z5 |+ j7 I( v4 f2 \9 I7 ?
    
65.               n = stack(stack_ptr);& Q( ~8 `3 {2 [
    
66.               if abs(tree_nodevalue(n) – seek_value) < 1e-3
    ; k* u6 X7 K0 I  Y! s\" T  }4 N
67.               %如果搜索到值，返回
    : V. Z; h. m2 l4 _/ P1 v
68.                      valueintree = tree_nodevalue(n);
    ! |+ u# h$ r' L\" H
69.                      nodeintree = tree_nodename(n);
    . e\" f# y/ C, c6 S0 r6 @- A
70.                      break;/ o3 ^5 i% z# \
    
71.               end! e* ~2 ], E2 F. R% Y5 X! y
    
72. ( o1 I( X3 c4 c1 X9 U$ C
    
73.               if tree_nodeson(n) ~= 0 & nodeinstack(n) == 1* }$ |9 \3 x& z  D8 F# K
    
74.               %如果节点有儿子，并且第一次入栈，将儿子节点入栈9 s: b4 ~9 O: S/ x2 g
    
75.                      stack_ptr = stack_ptr + 1;5 G/ _' L0 N9 N$ L- o( j8 ]5 E1 i
    
76.                      m = tree_nodeson(n);
    * f3 [9 Z. @' F0 B) `4 \$ J; _
77.                      stack(stack_ptr) = m;5 v+ D5 T/ C; T! c
    
78.                      nodeinstack(m) = nodeinstack(m) + 1;6 I% X4 q' d\" L$ m
    
79.               elseif tree_nodeneighbor(n) ~= 0
    ) y\" X! a2 T; g1 g: k8 D
80.               %否则，如果节点右边有兄弟，节点出栈，然后将右边兄弟入栈
    * M! e5 G; h9 r8 P8 l
81.                      m = tree_nodeneighbor(n);
    ( {\" L( c8 J3 [5 Y% @- u
82.                      stack(stack_ptr) = m;* H0 ], e. P# y% [' T% u: g
    
83.                      nodeinstack(m) = nodeinstack(m) + 1;
    , {4 x: |  L! U\" i\" i3 e
84.               else- `0 k# j+ D/ ]/ z' J
    
85.               %再否则，出栈，然后将父亲节点的入栈次数加一9 t; p; P& c$ Z\" l+ D
    
86.                      stack_ptr = stack_ptr - 1;
    + W. M! K$ W1 r6 x; `0 q  X
87.                      m = stack(stack_ptr);
    # ^' Y. S8 t& q5 E, W% W7 M4 E
88.                      nodeinstack(m) = nodeinstack(m) + 1;: @# f( @3 F3 I: J\" \
    
89.               end
    7 W& u# C( j! ^+ ]; ^
90.        end

复制代码