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

qiandongdong

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

madio

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

1. 首先需要定义树的存储。如果是C实现，应该是链表实现，每个节点用四个属性标志：. Y5 ^# N( V# d5 Z) Y8 v\" p
   
2.        tree_nodename：节点名字或序号
   ( X' W: L) ^, }& F/ I8 e# [- H9 N
3.        tree_nodevalue：节点对应的值
   2 R  c& U; I3 I
4.        tree_nodefather：节点父亲，如果没有父亲，值为空' k\" o4 _4 M7 p9 D$ d. Y
   
5.        tree_nodeson：节点的第一个儿子（最左边），如果没有儿子，值为空3 o( l4 ~5 M5 g9 a* b- s
   
6.        tree_nodeneighbor：节点的右边兄弟，如果右边没有兄弟，值为空
   5 V! v$ [' r0 S7 p) z
7.        树的搜索，因为不限制搜索顺序，这里使用深度优先。不用递归，可以用栈实现。. z! Q- ]# f5 [' P! C+ l
   
8. 
   \" w! \2 q$ r, A' ]2 I2 m
9.        刚学了点matlab，就使用matlab实现。Matlab中没有链表的概念，用数组实现。
   4 v0 e$ O: D+ x
10. 5 o9 p. ]4 b5 P' w8 y
    
11.        %matlab源程序2 }' q5 ?3 u+ D
    
12.        %输入：树的深度、树的广度、搜索的值, g) R4 }( `* q1 O
    
13.        %返回：树中接近的值、节点名字，如果没有接近的值，节点名字为空
    5 X( E3 d+ d- i( z
14.        function[valueintree, nodeintree] = tree(tree_depth, tree_width, seek_value)
    / U( ]) a5 @) [8 }9 u
15.        %根据树的深度、节点的儿子数量计算树总的节点个数- j3 y\" L3 j/ x
    
16.        node_num = 0;3 j* L' k: E, _* j  b
    
17.        for n= 0 : (tree_depth-1)
    & a1 Z6 J( V: [* k& [
18.               node_num = node_num + tree_width ^ n;( Y' k0 C\" z8 h8 I# ?4 z; T/ x
    
19.        end, Y! y, ]/ O  y1 C- ^; H# X
    
20. 
    ( C( M8 o0 b& A9 B3 k
21.        %为树的存储空间赋值( D$ U( b  m/ J' `1 R
    
22.        %node name，按照广度优先为节点排号
    + ]# o! V: P/ _! o
23.        tree_nodename = (1 : node_num);
    $ r$ \! j0 P; _- H' z' N
24.        %node value! V$ ?# _4 y- _) M' C
    
25.        tree_nodevalue = rand(1 : node_num);
    . Y3 L9 A# L( B: l8 S& M
26.        %node father and son6 [& U# p' p2 d. V; M
    
27.        tree_nodefather(1) = 0;/ z2 `* ]* V9 i
    
28.        tree_nodeson = zeros(1, node_num);# k1 \2 e% {9 F, _1 I! u
    
29.        n = 2;3 ~+ a+ l  I8 E
    
30.        k = 1;0 K+ x+ P) t6 H% G  L0 T* v& x5 S
    
31.        while n <= node_num
    * u3 C2 Q/ B3 F9 Q1 e
32.               for m = 1 : tree_width/ D+ f' u1 ^- J- J# y/ a
    
33.                      tree_nodefather(n) = k;6 x\" ]7 @1 f+ Q! s; q* `: a2 {
    
34.                      if m==1
    / ~# M8 ]- B$ O3 X3 b* y% F/ h8 x: A
35.                             tree_nodeson(k) = n;
    6 ~$ l' {& l8 O; O
36.                      end
    4 c6 R2 |  v$ ]9 B( P
37.                      n = n + 1;
    ! }/ n5 \9 }+ `9 D
38.               end6 q' C9 E( g- C9 o' V5 T% u
    
39.               k = k + 1;\" n% i& M0 [2 j) |' ^* |2 Q' ~) F+ t' t
    
40.        end
    : M5 g$ Y$ H  X5 x/ ]  p! S7 M
41.        %node neighbor  ]1 d& o8 Y* f* Q+ q$ ?, x5 ^
    
42.        tree_nodeneighbor(1) = 0;
    7 ~( M* [7 R  A. {, S* v6 Y8 g
43.        n = 2;
    / t- b1 E; Y& y- ?2 q, E+ S
44.        while n <= node_num# b1 k# ]8 n! ~( L
    
45.               for m = 1 : tree_width
    / K: H% o\" }( u( q
46.                      if m ==tree_width
    - i\" |\" i1 c& d  k
47.                             tree_nodeneighbor(n) = 0;
    & G3 n$ ~- l. o4 V# j$ M- A
48.                      else
    6 S) R1 Y; M: }7 R9 k( x# N
49.                             tree_nodeneighbor(n) = n + 1;
    $ e' M2 ]7 ^6 C8 m* y
50.                      end+ s6 V4 U; D. [. Z, l
    
51.                      n = n + 1;
    7 V4 {8 X% J3 `
52.               end: U# ~& D* m; K* I3 w+ m: u9 k8 c: j
    
53.        end
    ' g3 I) E% N2 g7 x\" D. N
54. 
    0 l$ t! a/ u# D. _0 V
55.        %下面是有效程序段，用栈实现
      ]8 L: Y7 l\" T$ r& k+ c
56.        stack = zeros(1, tree_depth);
      O; D' i3 b7 G0 a
57.        nodeinstack = zeros(1, node_num);
    ! B% W8 f  {: K3 E\" L- [1 K
58.        stack_ptr = 1;
    1 y6 c) @; U6 Y+ p' j( U
59.        stack(1) = 1;; x9 `' ?; Q5 e9 A
    
60.        nodeinstack(1) = 1;2 s0 M0 }5 @( g/ ^4 y8 M2 @
    
61.        valueintree = seek_value;  j: R. I, H3 T5 o
    
62.        nodeintree = 0;6 `7 q. X- d, ~
    
63. 2 E- }, i4 a; k. u
    
64.        while stack_ptr > 0
      y7 x( B* b$ Z1 Q
65.               n = stack(stack_ptr);
    , ~* I. s; b' m) c, `0 T/ m
66.               if abs(tree_nodevalue(n) – seek_value) < 1e-3
      e& a( v& J/ `  f$ c) u4 U
67.               %如果搜索到值，返回
    # n\" \. m1 F  F5 a: B
68.                      valueintree = tree_nodevalue(n);5 e' {6 [3 ?( [\" u5 v9 \
    
69.                      nodeintree = tree_nodename(n);
    9 l  m5 [5 s* O% m
70.                      break;
      h9 _  L& \0 W) }3 v\" A# T( o* ~. |
71.               end; G0 _8 j- i3 `5 L  `4 T
    
72. \" D) Y6 c8 y$ ~\" f0 E
    
73.               if tree_nodeson(n) ~= 0 & nodeinstack(n) == 1
    % x# b1 u. B7 Q- [' U
74.               %如果节点有儿子，并且第一次入栈，将儿子节点入栈' \. a  W: v9 ~$ l) a8 X: ?
    
75.                      stack_ptr = stack_ptr + 1;' k, j) j5 V% l$ x
    
76.                      m = tree_nodeson(n);$ U, |: C\" c$ g
    
77.                      stack(stack_ptr) = m;
    $ g: ]* {\" C' C% J- p/ h* a
78.                      nodeinstack(m) = nodeinstack(m) + 1;7 @4 F! J: C2 M( D& K/ \2 c
    
79.               elseif tree_nodeneighbor(n) ~= 0! U* L6 V: U\" ~! c$ A  ^
    
80.               %否则，如果节点右边有兄弟，节点出栈，然后将右边兄弟入栈
    $ K3 T; U/ G8 A
81.                      m = tree_nodeneighbor(n);
    : D7 \9 k: x- y! T\" D+ J
82.                      stack(stack_ptr) = m;! w- x* |' w3 |6 R, a! ?% C
    
83.                      nodeinstack(m) = nodeinstack(m) + 1;$ d0 @; U/ ^0 Z+ T8 x
    
84.               else: S. ~- w$ k  C* b0 Y$ |
    
85.               %再否则，出栈，然后将父亲节点的入栈次数加一0 L. h7 l' G! b( P$ e3 Y
    
86.                      stack_ptr = stack_ptr - 1;
    # O! a' B4 I. o9 q, U% p. t/ Y
87.                      m = stack(stack_ptr);, d% b' T/ m( J' d, g\" G8 w
    
88.                      nodeinstack(m) = nodeinstack(m) + 1;9 D- D5 B' F; a, ^
    
89.               end
    \" Z8 A- c( [+ Z2 U
90.        end

复制代码