数据结构:二叉树的建立和遍历(C#实现)

发表于 Disqus： 本文字数： 1.9k 阅读时长 ≈ 2 分钟

遍历只做了先序,递归实现的,中序和后序都类似.代码比较简单,就不写注释,直接贴出来了

代码:

TreeNode:结点类

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
using System;
using System.Collections.Generic;
using System.Text;

namespace 二叉树的建立和遍历
{
    class TreeNode
    {
        public char data;
        public TreeNode left, right;

        public TreeNode(char c, TreeNode l, TreeNode r)
        {
            data = c;
            left = l;
            right = r;
        }

        public TreeNode()
        {
            left = right = null;
        }
    }
}

Tree:树类 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
using System;
using System.Collections.Generic;
using System.Text;

namespace 二叉树的建立和遍历
{
    class Tree
    {
        public TreeNode root;
        Stack<TreeNode> stack = new Stack<TreeNode>();

        public void CreateTree(String description)
        {
            bool left = true;
            char[] descriptionarray = description.ToCharArray();
            root = new TreeNode();
            root.data = descriptionarray[0];
            TreeNode temp = root;
            for (int i = 1; i <= descriptionarray.Length - 1; i++)
            {
                if (descriptionarray[i] == '(')
                {
                    left = true;
                    stack.Push(temp);
                }
                else if (descriptionarray[i] == ',')
                {
                    left = false;
                }
                else if (descriptionarray[i] == ')')
                {
                    stack.Pop();
                }
                else
                {
                    temp = new TreeNode();
                    temp.data = descriptionarray[i];
                    if (left == true)
                    {
                        stack.Peek().left = temp;
                    }
                    else
                    {
                        stack.Peek().right = temp;
                    }
                }
            }
        }

        public void PreOrder(TreeNode t, String sign)
        {
            if (t != null)
            {
                Console.WriteLine(sign + t.data);
                sign += sign;
                if (t.left != null)
                {
                    PreOrder(t.left, sign);
                }

                if (t.right != null)
                {
                    PreOrder(t.right, sign);
                }
            }
        }
    }
}

Program:调用者 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
using System;
using System.Collections.Generic;
using System.Text;

namespace 二叉树的建立和遍历
{
    class Program
    {
        static void Main(string[] args)
        {
            //TreeNode t=null;
            Tree tree = new Tree();
            Console.WriteLine("请输入用字符串表示的二叉树");
            string input = Console.ReadLine();
            tree.CreateTree(input);
            Console.WriteLine("遍历");
            tree.PreOrder(tree.root, "--");
            Console.Read();
        }
    }
}