C++二叉树的创建与遍历

朱雀 2023-07-17 06:07 127阅读 0赞

最近学习了二叉树的一点知识，感觉数据结构真的很难啊，所以学习过程中的笔记还是要记录一下。

### 文章目录 ###

*  一、二叉树
 *  二、实现代码
 *  三、运行效果
 *  四、小结

# 一、二叉树 #

在我们使用的数据结构中，一对一的线性结构是我们经常所使用到的，但是现实中却有着许多一对多的情况，这也就产生了“树”这一概念。二叉树则是“树”这一概念中的一种特殊情况，其定义为：“是n(n>=0)个结点的有限集合。该集合或者为空集(称为空二叉树)。或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树的二叉树组成。”  
二叉树的特点：  
(1)每个节点最多有两个子树，所以二叉树的节点的度均小于等于2。  
(2)左子树和右子树是有顺序的，千万不能对其进行任意颠倒。  
…(其特点还有很多，就不一一叙述了)  
总的来说，如果说我之前使用的vector和list是一维结构的话，那二叉树就是二维结构。

# 二、实现代码 #

Node.h

#ifndef _NODE_
    #define _NODE_
    #include<string>
    using namespace std;
    
    class Node
    { 
    public:
    	string data;
    	Node* lchild=nullptr;
    	Node* rchild=nullptr;
    	Node(string);
    	~Node();
    };
    
    #endif // _NODE_

Node.cpp

#include "Node.h"
    Node::Node(string data)
    	:data(data)
    { 
    }
    
    Node::~Node()
    { 
    }

BinaryTree.h

#ifndef _BINATYTREE_
    #define _BINATYTREE_
    #include"Node.h"
    #include<queue>
    #include<iostream>
    using namespace std;
    
    class BinaryTree
    { 
    public:
    	Node* root = nullptr;
    	BinaryTree();
    	void Add(string data);	//添加节点，创建二叉树使用层次遍历
    	void PreOrder(const Node* node);	//先序遍历
    	void InOrder(const Node* node);		//中序遍历
    	void PostOrder(const Node* node);	//后序遍历
    	~BinaryTree();	//销毁二叉树
    
    private:
    	void DestoryBinaryTree(Node *tree);
    };
    
    #endif // !_BINATYTREE_

BinaryTree.cpp

#include "BinaryTree.h"
    
    
    BinaryTree::BinaryTree()
    { 
    }
    
    void BinaryTree::Add(string data)
    { 
    	Node* node=new Node(data);	//创建节点
    	queue<Node*> queue;
    	queue.push(root);		//将节点压入队列
    	if (!this->root)
    	{ 
    		root = node;
    		return;
    	}
    	while (!queue.empty())
    	{ 
    		Node* curNode =queue.front();
    		queue.pop();
    		if (!curNode->lchild)		//如果该节点没有左孩子，则把节点赋给它
    		{ 
    			curNode->lchild = node;
    			return;
    		}
    		else
    		{ 
    			queue.push(curNode->lchild);	//如果有则压入队列中
    		}
    		if (!curNode->rchild)
    		{ 
    			curNode->rchild = node;
    			return;
    		}
    		else
    		{ 
    			queue.push(curNode->rchild);
    		}
    	}
    
    }
    
    void BinaryTree::PreOrder(const Node* node)
    { 
    	if (!node)
    	{ 
    		return;
    	}
    	cout << node->data << " ";
    	PreOrder(node->lchild);
    	PreOrder(node->rchild);
    }
    
    void BinaryTree::InOrder(const Node * node)
    { 
    	if (!node)
    	{ 
    		return;
    	}
    	InOrder(node->lchild);
    	cout << node->data << " ";
    	InOrder(node->rchild);
    }
    
    void BinaryTree::PostOrder(const Node * node)
    { 
    	if (!node)
    	{ 
    		return;
    	}
    	PostOrder(node->lchild);
    	PostOrder(node->rchild);
    	cout << node->data << " ";
    }
    
    void BinaryTree::DestoryBinaryTree(Node * node)
    { 
    	if (node)	//如果有节点
    	{ 
    		if (node->lchild)	//如果存在左孩子
    		{ 
    			DestoryBinaryTree(node->lchild);	//销毁二叉树的左子树
    		}
    		if (node->rchild)
    		{ 
    			DestoryBinaryTree(node->rchild);	//销毁二叉树的右子树
    		}
    	}
    	delete node;	//销毁节点
    	node = nullptr;	
    }
    
    BinaryTree::~BinaryTree()
    { 
    	//遍历销毁
    	DestoryBinaryTree(root);
    }

main.cpp

#include<iostream>
    #include"BinaryTree.h"
    
    using namespace std;
    
    int main()
    { 
    	BinaryTree tree;
    	tree.Add("A");
    	tree.Add("B");
    	tree.Add("C");
    	tree.Add("D");
    	tree.Add("E");
    	tree.Add("F");
    	tree.Add("G");
    	//tree.Add("1");
    	//tree.Add("2");
    	//tree.Add("3");
    	//tree.Add("4");
    	//tree.Add("5");
    	cout << "先序遍历：";
    	tree.PreOrder(tree.root);
    	cout << endl << "中序遍历：";
    	tree.InOrder(tree.root);
    	cout << endl << "后序遍历：";
    	tree.PostOrder(tree.root);
    	cout << endl;
    
    	system("pause");
    	return 0;
    }

# 三、运行效果 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RheXVoYWl0YW5nMQ_size_16_color_FFFFFF_t_70]

# 四、小结 #

在整个过程中，要注意以下几点：  
(1)你怎么对二叉树进行遍历，你就可以使用这种遍历方式来创建二叉树。因此二叉树的创建方式有很多种，我选择的是层次创建(与其相对应的是层次遍历，也叫广度优先遍历)。  
(2)二叉树的销毁也可以使用其特定的遍历方式进行销毁。  
(3)因为层次遍历的过程很适合队列这种结构，所以可以使用queue来实现该遍历过程。

> 参考书籍：《大话数据结构》

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RheXVoYWl0YW5nMQ_size_16_color_FFFFFF_t_70]: /images/20230528/345d145a4c784da7a250269bef138be0.png