算法之树形结构

发表于 | 更新于
本文字数： 6k | 阅读时长 ≈ 5 分钟

思考并回答以下问题：

C#实现的树形结构。树的遍历使用的先序遍历，两个类，一个是节点结构，一个是管理节点的树。采用链式存储。直接上代码。

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
using UnityEngine;
using System.Collections;
using System.Collections.Generic;
/// <summary>
/// 文件夹树目录的节点基类,这应该写成接口的，类似树节点已经集成其他基类的结构可以实现这个接口，便于ListTree类对节点实现多态
/// </summary>
public class ListTreeNode <T> {
    public ListTreeNode <T> parent;                                     //父节点
    public List<ListTreeNode <T>> children;                             //子节点集合
	public T data;														//存放信息
	public ListTreeNode () {
 
	}
	public ListTreeNode (T data) {
		this.data = data;
        this.children = new List<ListTreeNode<T>>();
	}
	public ListTreeNode (T data, List <ListTreeNode <T>> list) {
		this.data = data;
		this.children = list;
	}
	public ListTreeNode (T data, List <ListTreeNode <T>> list, ListTreeNode <T> parent) {
		this.data = data;
		this.children = list;
		this.parent = parent;
	} 
}
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
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
using UnityEngine;
using System.Collections;
using System.Collections.Generic;
/// <summary>
/// 存放ListTreeNode的容器基类，对于节点的操作节点一定要从树中取得，我没有封装在一起，这写的不好
/// </summary>
public class ListTree <T> {
	#region 变量
	private ListTreeNode <T> mRoot;							//树的头节点
	#endregion
	#region 属性
	public ListTreeNode <T> Root {
		get {
			return mRoot;
		}
		set {
			mRoot = value;
		}
	}
	#endregion
	#region 构造方法
	public ListTree () {
		
	}
	public ListTree (ListTreeNode <T> root) {
		mRoot = root;
	}
	#endregion
	#region 方法
	//判断树是否为空
	public bool IsEmpty () {
		return null == mRoot ? true : false;
	}
	//获取节点，使用树的非递归先序遍历
	public ListTreeNode <T> GetNode (T nodeData) {
		if (null == mRoot) {
			return null;
		}
		ListTreeNode <T> temp = null;
		Stack <ListTreeNode <T>> stack = new Stack<ListTreeNode <T>> ();
		stack.Push (mRoot);
		while (stack.Count != 0) {
			temp = stack.Pop ();
			if (nodeData.Equals (temp.data)) {
				return temp;
			}
			for (int i = temp.children.Count - 1; i >= 0; i--) {
				stack.Push (temp.children [i]);
			}
		}
		return null;
	}
    //获取节点的路径信息集合
    public List<T> GetNodeDataArray(ListTreeNode <T> node) {
        List<T> list = new List<T>();
        Stack<T> stack = new Stack<T>();
        while (node.parent != null) {
            stack.Push(node.data);
            node = node.parent;
        }
        stack.Push(mRoot.data);
        while (stack.Count != 0) {
            list.Add(stack.Pop ());
        }
        return list;
    }
    //获取节点路径上的所有节点集合
    public List<ListTreeNode<T>> GetNodeArray(ListTreeNode <T> node) {
        List<ListTreeNode<T>> list = new List<ListTreeNode<T>>();
        Stack<ListTreeNode <T>> stack = new Stack<ListTreeNode<T>>();
        while (node.parent != null)
        {
            stack.Push(node);
            node = node.parent;
        }
        stack.Push(mRoot);
        while (stack.Count != 0)
        {
            list.Add(stack.Pop());
        }
        return list;
    }
	//判断一个节点是否存在
	public bool HaveNode (T nodeData) {
		ListTreeNode <T> temp = null;
		Stack <ListTreeNode <T>> stack = new Stack<ListTreeNode <T>> ();
		stack.Push (mRoot);
		while (stack.Count != 0) {
			temp = stack.Pop ();
			if (nodeData.Equals (temp.data)) {
				return true;
			}
			for (int i = temp.children.Count - 1; i >= 0; i--) {
				stack.Push (temp.children [i]);
			}
		}
		return false;
	}
	//插入节点，注意节点要通过GetNode方法从树中获取(用于插入一层结构)
	public bool InsertNode (ListTreeNode <T> parent, T nodeData) {
		if (null == parent) {
			return false;
		}
		ListTreeNode <T> node = new ListTreeNode<T> (nodeData);
		node.children = parent.children;
		node.parent = parent;
		parent.children.Add (node);
		return true;
	}
	//删除节点，注意节点要通过GetNode方法从树中获取
	public bool DeleteNode (ListTreeNode <T> parent, T nodeData) {
		if (null == parent) {
			return false;;
		}
		for (int i = 0; i < parent.children.Count; i++) {
			if (nodeData.Equals (parent.children [i].data)) {
				parent.children.RemoveAt (i);
			}
		}
		return true;
	}
	//添加叶子节点。注意节点要通过GetNode方法从树中获取，若返回值为假说明传入的父亲节点是空或者该父节点下的孩子节点存在此信息的节点
	public bool AddLeave (ListTreeNode <T> parent, T nodeData) {
		if (null == parent) {
			return false;
		}
		for (int i = 0; i < parent.children.Count; i++) {
			if (parent.children [i].data.Equals (nodeData)) {
				return false;
			}
		}
		ListTreeNode <T> node = new ListTreeNode<T> (nodeData);
		parent.children.Add (node);
		return true;
	}
    //添加叶子节点，并可回调该叶子节点
    public bool AddLeave(ListTreeNode<T> parent, T nodeData, out ListTreeNode <T> node)
    {
        node = new ListTreeNode<T>(nodeData);
        if (null == parent)
        {
            return false;
        }
        for (int i = 0; i < parent.children.Count; i++)
        {
            if (parent.children[i].data.Equals(nodeData))
            {
                node = parent.children[i];
                return false;
            }
        }
        parent.children.Add(node);
        node.parent = parent;
        return true;
    }
    //判断一个节点是否为叶子节点，注意节点要通过GetNode方法从树中获取
    public bool IsLeave (ListTreeNode <T> node) {
		return node.children.Count == 0 ? true : false;
	}
	#endregion
}
0%