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

作者：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
深入探讨C++中的GCD函数与队列

在iOS开发中，多线程技术的应用非常广泛，能够高效地执行多个调度任务。本文将重点介绍GCD（Grand Central Dispatch）在多线程开发中的应用，包括其函数和队列的实现细节。 ... [详细]

蜡笔小新 2024-11-16 14:59:50
int
设计无SQL死锁的编码模式 - Achieving SQL Deadlock-Free Design

在运行于MS SQL Server 2005的.NET 2.0 Web应用中，我偶尔会遇到令人头疼的SQL死锁问题。过去，我们主要通过调整查询来解决这些问题，但这既耗时又不可靠。我希望能找到一种确定性的查询模式，确保从设计上彻底避免SQL死锁。 ... [详细]

蜡笔小新 2024-11-16 13:09:51
int
使用Tkinter构建51Ape无损音乐爬虫UI

本文介绍了如何使用Python的内置模块Tkinter来构建一个简单的用户界面，用于爬取51Ape网站上的无损音乐百度云链接。虽然Tkinter入门相对简单，但在实际开发过程中由于文档不足可能会带来一些不便。 ... [详细]

蜡笔小新 2024-11-15 10:31:11
input
普通树(每个节点可以有任意数量的子节点)级序遍历

普通树(每个节点可以有任意数量的子节点)级序遍历 ... [详细]

蜡笔小新 2024-11-14 18:53:26
int
C语言利用前缀表达式实现复杂科学计算器

用C语言实现的科学计算器，支持2种常量，10种基本函数，Ans寄存器。相对来说拓展性应该是不错的，思路是首先化简复杂名称的函 ... [详细]

蜡笔小新 2024-11-16 11:46:11
int
Android异步处理系列文章四篇之三

Android异步处理一：使用Thread+Handler实现非UI线程更新UI界面Android异步处理二：使用AsyncTask异步更新UI界面Android异步处理三：Handler+Loope ... [详细]

蜡笔小新 2024-11-15 19:09:29
int
OpenGLPBO

PBO(PixelBufferObject),将像素数据存储在显存中。优点：1、快速的像素数据传递，它采用了一种叫DMA（DirectM ... [详细]

蜡笔小新 2024-11-15 14:56:34
int
【数据结构】线段数/segment tree/interval tree

【线段树】　　本质是二叉树，每个节点表示一个区间[L,R]，设m(R-L+1)2(该处结果向下取整)左孩子区间为[L，m]，右孩子区间为[m ... [详细]

蜡笔小新 2024-11-14 23:11:47
int
iOS 多线程技术之 GCD

本文将深入探讨 iOS 中的 Grand Central Dispatch (GCD)，并介绍如何利用 GCD 进行高效多线程编程。如果你对线程的基本概念还不熟悉，建议先阅读相关基础资料。 ... [详细]

蜡笔小新 2024-11-14 15:57:40
int
Python多进程高效读取超大文件的技巧

本文详细介绍了如何使用Python的多进程技术来高效地分块读取超大文件，并将其输出为多个文件。通过这种方式，可以显著提高读取速度和处理效率。 ... [详细]

蜡笔小新 2024-11-14 10:59:08
int
Python基础：使用NLTK和Python构建机器学习应用

本文节选自《NLTK基础教程——用NLTK和Python库构建机器学习应用》一书的第1章第1.2节，作者Nitin Hardeniya。本文将带领读者快速了解Python的基础知识，为后续的机器学习应用打下坚实的基础。 ... [详细]

蜡笔小新 2024-11-13 21:23:34
int
2017.11.26【清华集训2017】模拟

T15483.【清华集训2017模拟11.26】简单路径T25484.【清华集训2017模拟11.26】快乐树T35485.【清华集训2017模拟11.26】字符串T1结论题，结论很 ... [详细]

蜡笔小新 2024-11-13 20:25:28
int
（7）Python爬虫——爬取豆瓣电影Top250

利用python爬取豆瓣电影Top250的相关信息，包括电影详情链接,图片链接,影片中文名,影片外国名,评分,评价数,概况,导演,主演,年份,地区,类别这12项内容，然后将爬取的信息写入Exce ... [详细]

蜡笔小新 2024-11-13 11:35:24
input
面试中如何回答“零拷贝”技术问题？

零拷贝技术是提高I/O性能的重要手段，常用于Java NIO、Netty、Kafka等框架中。本文将详细解析零拷贝技术的原理及其应用。 ... [详细]

蜡笔小新 2024-11-13 02:03:52

wumu

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

Tags | 热门标签

RankList | 热门文章