开发笔记:树的浅析与实现

作者：wumu | 来源：互联网 | 2024-11-16 15:46

一、基本概念　　树是一种简单的非线性结构，所有元素之间具有明显的层次特性。在树结构中，每一个结点只有一个前驱节点，称为父结点，没有前驱节点的结点只有一个，称为树的根结点，简称树的根。

一、基本概念

　　树是一种简单的非线性结构，所有元素之间具有明显的层次特性。在树结构中，每一个结点只有一个前驱节点，称为父结点，没有前驱节点的结点只有一个，称为树的根结点，简称树的根。每一个结点可以有多个后继节点，称为该结点的子结点。没有后继节点的结点称为叶子结点。在树结构中，一个结点所拥有的后件的个数称为该结点的度，所有结点中最大的度称为树的度。树的最大层次称为树的深度。

二、二叉树

　　定义：二叉树是每个结点最多有两个子树的树结构。通常子树被称作“左子树”（left subtree）和“右子树”（right subtree）。二叉树常被用于实现二叉查找树和二叉堆。二叉树通常分为满二叉树和完全二叉树。

　　（1）满二叉树：一个深度为K且有2^k+1-1个节点的二叉树。

　　（2）完全二叉树：只多有最下面的两层的节点的度数可以小于2，其余各层节点的度数都等于2，并且最下面一层的节点都集中在该层最左边的若干位置。

　　性质：

　　（1）对于非空二叉树，其i层最大的节点数目为2ⁱ，其中i>=0。

　　（2）深度为k的二叉树之多有2^k+1-1个节点，其中k>=-1。

　　（3）在任意一棵非空二叉树中，若终端节点的个数为n_0，度为2的节点数为n₂，则存在n₀ = n₂ +1。

　　（4）具有n个节点的完全二叉树的深度为k等于log₂(n+1)向上取整再减1。

　　（5）如将一棵有n个节点的完全二叉树子上（根节点）向下（叶节点），同一层，子做向右连续赋予节点编号0,1,2,3,4....，n-1则对任意下标为i的节点有：

　　　　1、若i=0，则i为根节点，无父节点；若i>0,i>0，则i的父节点下标为（i-1）/2向下取整。

　　　　2、若2*i+1

　　　　3、若2*i+2

　　　　4、若i为偶数，且i≠0，则左兄弟为i-1。

　　　　5、若i为奇数，且i≠n-1，则右兄弟为i+1。

　　　　6、节点i所在的层次为log₂(i+1)向下取整。

　　实现：

树节点定义

1 #pragma once
2 #include <iostream>
3 #include
4 using namespace std;
5 template <class T>
6 class BinaryTreeNode
7 {
8 public:
9 BinaryTreeNode();
10 BinaryTreeNode(BinaryTreeNode* node);
11 void setData(const T &value); //设置节点值
12 void setParent(BinaryTreeNode*parent); //设置父节点
13 void setLeftChild(BinaryTreeNode*leftchild); //设置左孩子节点
14 void setRightChild(BinaryTreeNode*rightchild); //设置右孩子节点
15 T& getData(); //获取节点值
16 BinaryTreeNode* getparent(); //获取父节点
17 BinaryTreeNode* getLeftChild(); //获取左孩子节点
18 BinaryTreeNode* getRightChild(); //获取右孩子节点
19
20 private:
21 T m_value; //存储值
22 BinaryTreeNode* m_parent; //指向父节点
23 BinaryTreeNode* m_leftChilde; //指向左孩子节点
24 BinaryTreeNode* m_rightChilde; //指向右孩子节点
25 };
26
27
28
29
30 template <class T>
31 BinaryTreeNode::BinaryTreeNode()
32 {
33 m_parent = NULL;
34 m_leftChilde = NULL;
35 m_rightChilde = NULL;
36 }
37
38 template <class T>
39 BinaryTreeNode::BinaryTreeNode(BinaryTreeNode* node)
40 {
41 m_value = node->getData();
42 m_parent = node->getparent();
43 m_leftChilde = node->getLeftChild();
44 m_rightChilde = node->getRightChild();
45 }
46
47 template <class T>
48 void BinaryTreeNode::setData(const T &value)
49 {
50 m_value = value;
51 }
52
53 template <class T>
54 void BinaryTreeNode::setParent(BinaryTreeNode*parent)
55 {
56 m_parent = parent;
57 }
58
59 template <class T>
60 void BinaryTreeNode::setRightChild(BinaryTreeNode*rightchild)
61 {
62 m_rightChilde = rightchild;
63 }
64
65 template <class T>
66 void BinaryTreeNode::setLeftChild(BinaryTreeNode*leftchild)
67 {
68 m_leftChilde = leftchild;
69 }
70
71 template <class T>
72 T& BinaryTreeNode::getData()
73 {
74 return m_value;
75 }
76
77 template <class T>
78 BinaryTreeNode* BinaryTreeNode::getparent()
79 {
80 return m_parent;
81 }
82
83 template <class T>
84 BinaryTreeNode* BinaryTreeNode::getRightChild()
85 {
86 return m_rightChilde;
87 }
88
89 template <class T>
90 BinaryTreeNode* BinaryTreeNode::getLeftChild()
91 {
92 return m_leftChilde;
93 }

binaryTreeNode.h

树定义

1 #pragma once
2 #include
3 #include
4 #include
5 #include
6 #include "binaryTreeNode.h"
7 using namespace std;
8 template <class T>
9 class BinaryTree
10 {
11 public:
12 BinaryTree(T &value);
13 BinaryTree(BinaryTreeNode* node);
14 BinaryTreeNode* getRoot(); //获取根节点
15 void insertLeftChild(BinaryTreeNode* root, T &value); //插入左孩节点
16 void insertRightChild(BinaryTreeNode* root,T &value); //插入右孩子节点
17 bool isEmpty(); //判断是否为空
18 //树的遍历
19 //前序遍历
20 void preOrderTraverse1(BinaryTreeNode* root) const; //使用递归实现
21 void preOrderTraverse2(BinaryTreeNode* root) const; //使用栈结构实现
22 //中序遍历
23 void inOrderTraverse1(BinaryTreeNode* root) const; //使用递归实现
24 void inOrderTraverse2(BinaryTreeNode* root) const; //使用栈结构实现
25 //后序遍历
26 void postOrderTraverse1(BinaryTreeNode* root) const; //使用递归实现
27 void postOrderTraverse2(BinaryTreeNode* root) const; //使用栈结构实现
28 //层序遍历
29 void levelOrderTraverse(BinaryTreeNode* root) const;
30 private:
31 BinaryTreeNode* m_root; //根节点
32 };
33
34
35
36
37
38 //构造函数
39 template <class T>
40 BinaryTree::BinaryTree(T &value)
41 {
42 m_root = new BinaryTreeNode();
43 m_root->setData(value);
44 }
45
46 template <class T>
47 BinaryTree::BinaryTree(BinaryTreeNode* node)
48 {
49 m_root = new BinaryTreeNode(); //创建一个新的节点
50 m_root = node;
51 }
52
53 //设置子节点函数
54 template <class T>
55 void BinaryTree::insertRightChild(BinaryTreeNode* root, T &value)
56 {
57 BinaryTreeNode* childNode = new BinaryTreeNode();
58 childNode->setData(value);
59 childNode->setParent(root);
60 root->setRightChild(childNode);
61 }
62
63 template <class T>
64 void BinaryTree::insertLeftChild(BinaryTreeNode* root, T &value)
65 {
66 BinaryTreeNode* childNode = new BinaryTreeNode();
67 childNode->setData(value);
68 childNode->setParent(root);
69 root->setLeftChild(childNode);
70 }
71
72 //获取根节点函数
73 template <class T>
74 BinaryTreeNode* BinaryTree::getRoot()
75 {
76 return m_root;
77 }
78
79 template <class T>
80 bool BinaryTree::isEmpty()
81 {
82 return m_root->getparent();
83 }
84
85 //遍历函数
86 //1、前序遍历
87 template <class T>
88 void BinaryTree::preOrderTraverse1(BinaryTreeNode* root) const
89 {
90 if (NULL !=root)
91 {
92 cout <getData() <<"->";
93 preOrderTraverse1(root->getLeftChild());
94 preOrderTraverse1(root->getRightChild());
95 }
96 }
97
98 template <class T>
99 void BinaryTree::preOrderTraverse2(BinaryTreeNode* root) const
100 {
101 stack*> s;
102 BinaryTreeNode* p = root;
103 while (!s.empty() || p!=NULL)
104 {
105 while (p)
106 {
107 s.push(p);
108 cout <getData() <<"->";
109 p = p->getLeftChild();
110 }
111 p = s.top();
112 s.pop();
113 p = p->getRightChild();
114
115 }
116 }
117
118 //2、中序遍历
119 template <class T>
120 void BinaryTree::inOrderTraverse1(BinaryTreeNode* root) const
121 {
122 if (NULL != root)
123 {
124 inOrderTraverse1(root->getLeftChild());
125 cout <getData() <<"->";
126 inOrderTraverse1(root->getRightChild());
127 }
128 }
129
130 template <class T>
131 void BinaryTree::inOrderTraverse2(BinaryTreeNode* root) const
132 {
133 stack*> s;
134 BinaryTreeNode*p = root;
135 while (!s.empty() || p != NULL)
136 {
137 while (p)
138 {
139 s.push(p);
140 p = p->getLeftChild();
141 }
142 p = s.top();
143 s.pop();
144 cout <getData()<<"->";
145 p = p->getRightChild();
146 }
147 }
148
149 //2、后序遍历
150 template <class T>
151 void BinaryTree::postOrderTraverse1(BinaryTreeNode* root) const
152 {
153 if (NULL!=root)
154 {
155 postOrderTraverse1(root->getLeftChild());
156 postOrderTraverse1(root->getRightChild());
157 cout <getData() <<"->";
158 }
159 }
160
161 template <class T>
162 void BinaryTree::postOrderTraverse2(BinaryTreeNode* root) const
163 {
164 stack*> s;
165 BinaryTreeNode *cur; //当前节点
166 BinaryTreeNode *pre = NULL; //上一次访问的节点
167 s.push(root);
168 while (!s.empty() )
169 {
170 cur = s.top();
171 if ((cur->getLeftChild() == NULL) && (cur->getRightChild() == NULL)
172 || (pre != NULL)&&(pre ==cur->getLeftChild()||pre==cur->getRightChild()))
173 {
174 cout <getData() <<"->"; //如果当前结点没有孩子结点或者孩子节点都已被访问过
175 s.pop();
176 pre = cur;
177 }
178 else
179 {
180 if (cur->getRightChild() != NULL)
181 {
182 s.push(cur->getRightChild());
183 }
184 if (cur->getLeftChild() != NULL)
185 {
186 s.push(cur->getLeftChild());
187 }
188 }
189
190 }
191
192
193 }
194 //层序遍历
195 template <class T>
196 void BinaryTree::levelOrderTraverse(BinaryTreeNode* root) const
197 {
198 queue* > q;
199 BinaryTreeNode* p;
200 q.push(root);
201 while (!q.empty())
202 {
203 p = q.front();
204 if (p->getLeftChild() != NULL)
205 q.push(p->getLeftChild());
206 if (p->getRightChild() != NULL)
207 q.push(p->getRightChild());
208 q.pop();
209 cout <getData() <<"->";
210 }
211 }

BinaryTree.h

测试代码

1 #include
2 #include
3 #include "BinaryTree.h"
4 #include "binaryTreeNode.h"
5 using namespace std;
6 int main()
7 {
8 char value = ‘A‘;
9 BinaryTree<char> mytree(value);
10 value++;
11 mytree.insertLeftChild(mytree.getRoot(), value);
12 value++;
13 mytree.insertRightChild(mytree.getRoot(), value);
14 value++;
15 mytree.insertLeftChild(mytree.getRoot()->getLeftChild(), value);
16 value++;
17 mytree.insertRightChild(mytree.getRoot()->getLeftChild(), value);
18 value++;
19 mytree.insertLeftChild(mytree.getRoot()->getRightChild(), value);
20 value++;
21 mytree.insertRightChild(mytree.getRoot()->getRightChild(), value);
22
23 cout <getData() <<"
";
24 cout <getLeftChild()->getData() <<"
";
25 cout <getRightChild()->getData() <<"
";
26 cout <getLeftChild()->getLeftChild()->getData() <<"
";
27 cout <getLeftChild()->getRightChild()->getData() <<"
";
28 cout <getRightChild()->getLeftChild()->getData() <<"
";
29 cout <getRightChild()->getRightChild()->getData() <<"
";
30 cout <<"前序遍历递归实现"<<endl;
31 mytree.preOrderTraverse1(mytree.getRoot());
32 cout << endl;
33 cout <<"前序遍历栈实现" << endl;
34 mytree.preOrderTraverse2(mytree.getRoot());
35 cout << endl;
36 cout <<"中序遍历递归实现" << endl;
37 mytree.inOrderTraverse1(mytree.getRoot());
38 cout << endl;
39 cout <<"中序遍历栈实现" << endl;
40 mytree.inOrderTraverse2(mytree.getRoot());
41 cout << endl;
42 cout <<"后序遍历递归实现" << endl;
43 mytree.postOrderTraverse1(mytree.getRoot());
44 cout << endl;
45 cout <<"后序遍历栈实现" << endl;
46 mytree.postOrderTraverse2(mytree.getRoot());
47 cout << endl;
48 cout <<"层序遍历实现" << endl;
49 mytree.levelOrderTraverse(mytree.getRoot());
50
51
52 return 0;
53 }

测试代码

测试结果

技术分享图片

推荐阅读

int
Weight the Tree（树形dp）

题目Link题目学习link1题目学习link2题目学习link3%%%受益匪浅！－－－－－&# ... [详细]

蜡笔小新 2024-12-26 15:55:56
bit
Codeforces Round #566 (Div. 2) A~F个人题解

Dashboard-CodeforcesRound#566(Div.2)-CodeforcesA.FillingShapes题意：给你一个的表格，你 ... [详细]

蜡笔小新 2024-12-25 18:41:21
int
丽江客栈选择问题

本文介绍了一道经典的算法题，题目涉及在丽江河边的n家特色客栈中选择住宿方案。两位游客希望住在色调相同的两家客栈，并在晚上选择一家最低消费不超过p元的咖啡店小聚。我们将详细探讨如何计算满足条件的住宿方案总数。 ... [详细]

蜡笔小新 2024-12-22 20:15:25
int
使用Objective-C和dispatch库实现并发素数计算

本文介绍如何使用Objective-C结合dispatch库进行并发编程，以提高素数计数任务的效率。通过对比纯C代码与引入并发机制后的代码，展示dispatch库的强大功能。 ... [详细]

蜡笔小新 2024-12-28 08:44:35
int
USACO 2014 Jan - Moolympics区间记录优化算法

题目描述：给定n个半开区间[a, b)，要求使用两个互不重叠的记录器，求最多可以记录多少个区间。解决方案采用贪心算法，通过排序和遍历实现最优解。 ... [详细]

蜡笔小新 2024-12-27 18:14:31
int
洛谷 P4116 树上操作：颜色变换与路径查询

本题涉及一棵由N个节点组成的树（共有N-1条边），初始时所有节点均为白色。题目要求处理两种操作：一是改变某个节点的颜色（从白变黑或从黑变白）；二是查询从根节点到指定节点路径上的第一个黑色节点，若无则输出-1。 ... [详细]

蜡笔小新 2024-12-26 10:22:20
int
CUGB图论专题：排水系统中的最大流问题 - EK与Dinic算法解析

本题探讨如何通过最大流算法解决农场排水系统的设计问题。题目要求计算从水源点到汇合点的最大水流速率，使用经典的EK（Edmonds-Karp）和Dinic算法进行求解。 ... [详细]

蜡笔小新 2024-12-25 17:47:23
int
Tetris 排名系统 (拓扑排序与并查集的应用)

本题旨在通过给定的评级信息，利用拓扑排序和并查集算法来确定全球 Tetris 高手排行榜。题目要求判断是否可以根据提供的信息生成一个明确的排名表，或者是否存在冲突或信息不足的情况。 ... [详细]

蜡笔小新 2024-12-24 21:03:51
int
图论问题解析：POJ2762 从u到v或从v到u的可达性判断（强连通分量缩点与单向连通性检测）

本文深入探讨了POJ2762问题，旨在通过强连通分量缩点和单向连通性的判断方法，解决有向图中任意两点之间的可达性问题。文章详细介绍了算法原理、实现步骤，并附带完整的代码示例。 ... [详细]

蜡笔小新 2024-12-24 10:44:24
int
深入解析Linux pinctrl子系统：数据结构详解

本文将详细探讨Linux pinctrl子系统的各个关键数据结构，帮助读者深入了解其内部机制。通过分析这些数据结构及其相互关系，我们将进一步理解pinctrl子系统的工作原理和设计思路。 ... [详细]

蜡笔小新 2024-12-23 19:52:26
int
利用决策树预测NBA比赛胜负的Python数据挖掘实践

本文通过使用2013-14赛季NBA赛程与结果数据集以及2013年NBA排名数据，结合《Python数据挖掘入门与实践》一书中的方法，展示如何应用决策树算法进行比赛胜负预测。我们将详细讲解数据预处理、特征工程及模型评估等关键步骤。 ... [详细]

蜡笔小新 2024-12-23 09:07:40
command
使用arm-eabi-gdb调试Android C/C++应用程序的详细指南

本文详细介绍如何使用arm-eabi-gdb调试Android平台上的C/C++程序。通过具体步骤和实用技巧，帮助开发者更高效地进行调试工作。 ... [详细]

蜡笔小新 2024-12-28 10:25:18
int
GWT PopupPanel onKeyDownPreview 方法详解与实例

本文详细介绍了 GWT 中 PopupPanel 类的 onKeyDownPreview 方法，提供了多个代码示例及应用场景，帮助开发者更好地理解和使用该方法。 ... [详细]

蜡笔小新 2024-12-28 10:07:27
int
Java并发编程：LinkedBlockingQueue的实际应用

本文介绍了Java并发库中的阻塞队列（BlockingQueue）及其典型应用场景。通过具体实例，展示了如何利用LinkedBlockingQueue实现线程间高效、安全的数据传递，并结合线程池和原子类优化性能。 ... [详细]

蜡笔小新 2024-12-27 18:51:49
int
使用 NSTimer 实现倒计时功能

本文介绍如何使用 NSTimer 实现倒计时功能，详细讲解了初始化方法、参数配置以及具体实现步骤。通过示例代码展示如何创建和管理定时器，确保在指定时间间隔内执行特定任务。 ... [详细]

蜡笔小新 2024-12-26 19:08:19

wumu

这个家伙很懒，什么也没留下！

Tags | 热门标签

RankList | 热门文章