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

作者：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 }

测试代码

测试结果

技术分享图片

推荐阅读

go
Weight the Tree（树形dp）

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

蜡笔小新 2024-12-26 15:55:56
include
Splay Tree 区间操作优化

本文详细介绍了使用Splay Tree进行区间操作的实现方法，包括插入、删除、修改、翻转和求和等操作。通过这些操作，可以高效地处理动态序列问题，并且代码实现具有一定的挑战性，有助于编程能力的提升。 ... [详细]

蜡笔小新 2024-12-26 18:47:12
go
扫描线三巨头 hdu1928hdu 1255 hdu 1542 [POJ 1151]

学习链接：http:blog.csdn.netlwt36articledetails48908031学习扫描线主要学习的是一种扫描的思想，后期可以求解很 ... [详细]

蜡笔小新 2024-12-26 20:04:36
go
洛谷 P4116 树上操作：颜色变换与路径查询

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

蜡笔小新 2024-12-26 10:22:20
io
Codeforces Round #566 (Div. 2) A~F个人题解

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

蜡笔小新 2024-12-25 18:41:21
io
使用Objective-C和dispatch库实现并发素数计算

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

蜡笔小新 2024-12-28 08:44:35
tree
新浪笔试题

1:有如下一段程序：packagea.b.c;publicclassTest{privatestaticinti0;publicintgetNext(){return ... [详细]

蜡笔小新 2024-12-27 19:32:17
include
C++实现经典排序算法

本文详细介绍了七种经典的排序算法及其性能分析。每种算法的平均、最坏和最好情况的时间复杂度、辅助空间需求以及稳定性都被列出，帮助读者全面了解这些排序方法的特点。 ... [详细]

蜡笔小新 2024-12-27 19:25:14
go
词根词缀解析：greg、hap、helio及其他词源故事

本文基于刘洪波老师的《英文词根词缀精讲》，深入探讨了多个重要词根词缀的起源及其相关词汇，帮助读者更好地理解和记忆英语单词。 ... [详细]

蜡笔小新 2024-12-27 18:59:50
go
USACO 2014 Jan - Moolympics区间记录优化算法

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

蜡笔小新 2024-12-27 18:14:31
go
GDI基础介绍之几何绘图

使用GDI的一些AIP函数我们可以轻易的绘制出简 ... [详细]

蜡笔小新 2024-12-25 18:23:37
io
VxWorks中的双向链表与环形缓冲应用

本文详细探讨了VxWorks操作系统中双向链表和环形缓冲区的实现原理及使用方法，通过具体示例代码加深理解。 ... [详细]

蜡笔小新 2024-12-26 13:26:16
include
Linux设备驱动程序：异步时间操作与调度机制

本文介绍了Linux内核中的几种异步延迟操作方法，包括内核定时器、tasklet机制和工作队列。这些机制允许在未来的某个时间点执行任务，而无需阻塞当前线程，从而提高系统的响应性和效率。 ... [详细]

蜡笔小新 2024-12-26 08:55:03
include
探索1000以内的完美数：因数和等于自身

本文探讨了如何在1000以内找到所有完美数，即一个数的因数（不包括自身）之和等于该数本身。例如，6是一个完美数，因为1 + 2 + 3 = 6。通过编程实现这一过程，可以更好地理解完美数的特性。 ... [详细]

蜡笔小新 2024-12-25 19:21:06
io
POJ 1691 矩形涂色问题 (DFS/状态压缩DP)

本题通过将每个矩形视为一个节点，根据其相对位置构建拓扑图，并利用深度优先搜索（DFS）或状态压缩动态规划（DP）求解最小涂色次数。本文详细解析了该问题的建模思路与算法实现。 ... [详细]

蜡笔小新 2024-12-25 18:27:21

wumu

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

Tags | 热门标签

RankList | 热门文章