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

qiandongdong

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

madio

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

1. 首先需要定义树的存储。如果是C实现，应该是链表实现，每个节点用四个属性标志：* b6 P3 R2 F+ @9 a0 x
   
2.        tree_nodename：节点名字或序号7 C4 z3 T* l5 b2 t
   
3.        tree_nodevalue：节点对应的值9 ^# d1 U) P4 \
   
4.        tree_nodefather：节点父亲，如果没有父亲，值为空
   1 Q1 E% d& z9 Y/ d: G$ v/ [, ?
5.        tree_nodeson：节点的第一个儿子（最左边），如果没有儿子，值为空- o2 E0 T\" C9 g$ s\" T7 B/ I7 X
   
6.        tree_nodeneighbor：节点的右边兄弟，如果右边没有兄弟，值为空2 C: C  m6 S! @/ w2 @! g7 N! Q! p
   
7.        树的搜索，因为不限制搜索顺序，这里使用深度优先。不用递归，可以用栈实现。
   9 F( P% s8 @# S. s
8. & e0 j! `( P( p$ q; U; B
   
9.        刚学了点matlab，就使用matlab实现。Matlab中没有链表的概念，用数组实现。
   9 d6 Z; z/ w8 {* ?
10. 
    : D+ W# t- U/ P5 D, x' F1 R
11.        %matlab源程序
      I$ I# b) J; U4 L\" e6 @# X2 [# r\" a
12.        %输入：树的深度、树的广度、搜索的值
    7 a1 f5 x1 z\" X! _  X
13.        %返回：树中接近的值、节点名字，如果没有接近的值，节点名字为空2 J: R7 i, ?& k+ J  F7 z  J
    
14.        function[valueintree, nodeintree] = tree(tree_depth, tree_width, seek_value)- K5 F, x1 x4 [) B# Y
    
15.        %根据树的深度、节点的儿子数量计算树总的节点个数
    * _\" M/ c- n; R7 Y$ {4 w9 R; W4 g
16.        node_num = 0;
    : s& L; B/ h, w3 C; Q) j
17.        for n= 0 : (tree_depth-1)
    ) A' M. W1 h5 v7 P' @
18.               node_num = node_num + tree_width ^ n;
    3 O5 _* R& R6 Z6 G) S; U1 L% Y
19.        end0 g% P3 J% l9 n# S8 o( t# C
    
20. 
    4 [  f0 [0 e- X
21.        %为树的存储空间赋值' h& U0 G- L8 J/ r  r! Z
    
22.        %node name，按照广度优先为节点排号
    ! ^! d( z; z% R4 o/ Z3 n
23.        tree_nodename = (1 : node_num);6 w\" y+ K6 l' d
    
24.        %node value/ S$ ]- o- U, @8 W4 X; I
    
25.        tree_nodevalue = rand(1 : node_num);7 A8 `+ X7 K, a6 A6 \1 p& F
    
26.        %node father and son
    1 x0 d3 T. P1 l! o' C
27.        tree_nodefather(1) = 0;
    \" a8 T: r\" F& R/ l& |% Q1 t
28.        tree_nodeson = zeros(1, node_num);
    % O% U* E  w& @& M
29.        n = 2;8 K/ ^  G2 |! v& f6 @- z
    
30.        k = 1;# }5 N0 c! I\" u) F
    
31.        while n <= node_num
    , A; j+ N) U( R& E
32.               for m = 1 : tree_width
    # x# f. S5 J\" ^+ _4 N% d
33.                      tree_nodefather(n) = k;
    # p$ n2 x% r1 K0 I
34.                      if m==1
    3 ^: h* d3 M& o) L- `: D5 R$ ~7 H
35.                             tree_nodeson(k) = n;+ l3 W) X8 g4 P& k% w: B! j$ Q
    
36.                      end0 [$ D( s0 d: G2 J/ C
    
37.                      n = n + 1;
    0 `7 N0 I\" G\" b7 b  k- Y. Y
38.               end5 b$ F2 n5 _; [5 r1 W
    
39.               k = k + 1;% B# D1 O- i% e/ y9 C. z
    
40.        end
    8 V! z+ w+ j# d; ~. T) ^% k9 ?3 [* l# J
41.        %node neighbor
    : X% z/ b2 X! }; E5 m
42.        tree_nodeneighbor(1) = 0;# ]0 h1 }; S+ ^8 N4 P- _( L
    
43.        n = 2;# d6 H# H3 k/ s2 d% s
    
44.        while n <= node_num
    / c\" p- _' ?0 B& K& z3 p1 D6 Z
45.               for m = 1 : tree_width  z+ m2 F8 p, V: y( [9 M  V
    
46.                      if m ==tree_width5 h0 a$ n1 B0 j% N; }
    
47.                             tree_nodeneighbor(n) = 0;
    3 m0 W0 R# ?, x7 I8 K) z
48.                      else. r- Z! C; V! q* X8 o$ i3 w% ^
    
49.                             tree_nodeneighbor(n) = n + 1;) o  d. U) s5 E
    
50.                      end2 y. O+ m  f! u
    
51.                      n = n + 1;
      @$ t; D9 p) V9 ~, T+ Y# B9 @
52.               end
    3 o( ^7 O- ]0 l7 i% n
53.        end% p8 D0 G  i( d
    
54. 
    . h# s& ~% I: B
55.        %下面是有效程序段，用栈实现! _! y: u! M% P2 W
    
56.        stack = zeros(1, tree_depth);
    & L% @4 U( A3 ^) Y' g% X, ~
57.        nodeinstack = zeros(1, node_num);0 N7 }5 l7 g+ x, f& e\" L
    
58.        stack_ptr = 1;
      l+ ~. b( n$ a; g\" v0 \8 F+ M6 f% ~
59.        stack(1) = 1;
    , B9 G- s\" R; ~
60.        nodeinstack(1) = 1;
    5 L! c4 B3 t6 i\" g# y( H\" g
61.        valueintree = seek_value;  J# B. n\" p5 ~) x0 C7 w
    
62.        nodeintree = 0;
    4 U- E7 H5 q% [2 [
63. : B& B  Z7 Z& j. V0 f# }
    
64.        while stack_ptr > 0, W8 S4 }& D0 ]8 {
    
65.               n = stack(stack_ptr);
    ) |. Z6 |' X. Y8 ~- E/ \  W+ d
66.               if abs(tree_nodevalue(n) – seek_value) < 1e-3
    ) d. Z, ~% e: s\" r- {1 b; Y! ^8 ~& L+ s
67.               %如果搜索到值，返回: g7 d1 N- i. h
    
68.                      valueintree = tree_nodevalue(n);, Q2 e( W- H/ @' x/ F$ K  j; {0 R
    
69.                      nodeintree = tree_nodename(n);
    7 Z; E; K) r4 e/ l
70.                      break;
    4 U$ Y3 R. I( b! _
71.               end5 ?% G' S# l$ l  n2 y* H- N
    
72. , H$ N. P& N. F& k) G
    
73.               if tree_nodeson(n) ~= 0 & nodeinstack(n) == 1
    4 _, G2 C- c% {8 e5 @3 A
74.               %如果节点有儿子，并且第一次入栈，将儿子节点入栈
    3 G! ]6 Z4 K8 N8 U8 }% T9 Q  q\" R
75.                      stack_ptr = stack_ptr + 1;! T# M; @  o% z
    
76.                      m = tree_nodeson(n);' _! `# z: E0 b8 Q3 \. B9 i
    
77.                      stack(stack_ptr) = m;3 F. h/ Y  Z( s! B2 q- k& V% k
    
78.                      nodeinstack(m) = nodeinstack(m) + 1;\" O6 Q( V( s) o* x3 {; k0 X
    
79.               elseif tree_nodeneighbor(n) ~= 0\" G, k' ?\" d9 }1 B3 T\" D/ B5 K7 d
    
80.               %否则，如果节点右边有兄弟，节点出栈，然后将右边兄弟入栈
    ( D/ n- e) L6 S6 g
81.                      m = tree_nodeneighbor(n);
    8 Y- \4 h# c7 i
82.                      stack(stack_ptr) = m;/ z, z7 \& ^' E9 M1 _2 h
    
83.                      nodeinstack(m) = nodeinstack(m) + 1;
    / z' m! G4 G: e( {3 e# x/ h
84.               else
    9 C% ?; l% g+ C$ `$ [  W
85.               %再否则，出栈，然后将父亲节点的入栈次数加一4 I5 A; T- U9 v
    
86.                      stack_ptr = stack_ptr - 1;: a# l! \3 X3 ]! @- h/ C( |- }
    
87.                      m = stack(stack_ptr);+ V7 W8 a0 I7 k5 [6 R
    
88.                      nodeinstack(m) = nodeinstack(m) + 1;1 k7 g; z\" P! \0 V0 `( g
    
89.               end
      t& |3 I- {# w! E$ L( e
90.        end

复制代码