• 推荐
  • 评论
  • 收藏

二叉树

2023-01-29    2601次浏览

 【数据机构和算法】章节中的【二叉树】,一直都觉得比较难。

  使用C++语言用类进行了封装,以便于今后学习!

 

  首先,定义了二叉树的节点类

View Code
// BinaryTreeNode.h: interface for the BinaryTreeNode class.
// 二叉树的节点 NODE
// 节点 、 左节点 、右节点
// 2011-12-13 chen ang
//////////////////////////////////////////////////////////////////////

#if !defined(AFX_BINARYTREENODE_H__C6FD71B8_0809_43C0_B6C3_E6B7B5B032D2__INCLUDED_)
#define AFX_BINARYTREENODE_H__C6FD71B8_0809_43C0_B6C3_E6B7B5B032D2__INCLUDED_

#if _MSC_VER > 1000
#pragma once
#endif // _MSC_VER > 1000

template<class T>
class BinaryTreeNode
{
private:
T m_element; //节点数据域
BinaryTreeNode<T>* m_pLeft; //左节点指针
BinaryTreeNode<T>* m_pRight; //右节点指针
BinaryTreeNode<T>* m_pParent; //父节点指针:使用三叉链表存储
public:
//默认的构造函数
BinaryTreeNode()
{
memset(&m_element, 0, sizeof(T));
m_pLeft = NULL;
m_pRight = NULL;
m_pParent = NULL;
};
//析构函数
virtual ~BinaryTreeNode(){};
//传参的构造函数:二叉链表
BinaryTreeNode(const T& element, BinaryTreeNode<T>* l=NULL, BinaryTreeNode<T>* r=NULL)
{
m_element = element;
m_pLeft = l;
m_pRight = r;
m_pParent = NULL;
};
//传参的构造函数:三叉链表
BinaryTreeNode(const T& element, BinaryTreeNode<T>* p, BinaryTreeNode<T>* l=NULL, BinaryTreeNode<T>* r=NULL)
{
m_element = element;
m_pLeft = l;
m_pRight = r;
m_pParent = p;
};
//设置节点内容
void SetValue(const T& element)
{
m_element = element;
};
//设置左节点指针
void SetLeftChild(BinaryTreeNode<T>* l)
{
m_pLeft = l;
};
//设置右节点指针
void SetRightChild(BinaryTreeNode<T>* r)
{
m_pRight = r;
};
//设置父节点指针
void SetParent(BinaryTreeNode<T>* p)
{
if (NULL == m_pParent)
{
m_pParent = p;
}
};
//获取节点内容
T GetValue() const
{
return m_element;
};
//获取节点内容
void DisplayValue() const
{
cout<<GetValue()<<" ";
};
//获取左节点指针
BinaryTreeNode<T>* GetLeftChild() const
{
return m_pLeft;
};
//获取右节点指针
BinaryTreeNode<T>* GetRightChild() const
{
return m_pRight;
};
//获取父节点指针
BinaryTreeNode<T>* GetParent() const
{
return m_pParent;
};
//重载赋值函数
BinaryTreeNode<T>& operator=(const BinaryTreeNode<T>& node)
{
m_element = node.m_element;
m_pLeft = node.m_pLeft;
m_pRight = node.m_pRight;
m_pParent = node.m_pParent;
};
//判断当前节点是否为叶节点:是则返回true, 否则返回false
bool IsLeaf() const
{
if ((NULL == m_pLeft) && (NULL == m_pRight))
{
return true;
}
else
{
return false;
};
};
};

#endif // !defined(AFX_BINARYTREENODE_H__C6FD71B8_0809_43C0_B6C3_E6B7B5B032D2__INCLUDED_)


  其次:定义和实现了二叉树

View Code
// BinaryTree.h: interface for the BinaryTree class.
// 二叉树
// 2011-12-13 chen ang
//////////////////////////////////////////////////////////////////////

#if !defined(AFX_BINARYTREE_H__E94D44AE_ADCE_4F3E_A731_699E58A76F6C__INCLUDED_)
#define AFX_BINARYTREE_H__E94D44AE_ADCE_4F3E_A731_699E58A76F6C__INCLUDED_

#if _MSC_VER > 1000
#pragma once
#endif // _MSC_VER > 1000

#include <stack>
#include "BinaryTreeNode.h"

template<class T>
class BinaryTree
{
private:
BinaryTreeNode<T>* m_root; //二叉树的根节点
public:
//默认的构造函数
BinaryTree()
{
//默认为空树
m_root = NULL;
};
//传参的构造函数
BinaryTree(const T& element)
{
//只有根节点一个节点的树
m_root = new BinaryTreeNode<T>(element);
};
//析构函数
virtual ~BinaryTree(){};
//判断二叉树是否为空:空返回true; 非空返回false.
bool IsEmpty() const
{
if (NULL == m_root)
{
return true;
}
else
{
return false;
}
};
//返回二叉树的根节点
BinaryTreeNode<T>* GetRoot() const
{
return m_root;
};
//返回current结点的父结点
BinaryTreeNode<T>* GetParent(BinaryTreeNode<T>* current)
{
if ((NULL == current) || (m_root == current))
{
return NULL;
}

stack<BinaryTreeNode<T>*> s_t;
BinaryTreeNode<T>* temp = m_root;
while(!s_t.empty() || temp)
{
if (temp)
{
s_t.push(temp);
if (temp->GetLeftChild() == current || temp->GetRightChild() == current)
{
return temp;
}
temp = temp->GetLeftChild();
}
else
{
temp = s_t.top();
s_t.pop();
temp = temp->GetRightChild();
}
}

return NULL;
};
//返回current结点的左兄弟结点
BinaryTreeNode<T>* GetLeftSibling(BinaryTreeNode<T>* current)
{
if (current)
{
BinaryTreeNode<T>* temp = GetParent(current);
if ((NULL == temp) || (current == temp->GetLeftChild()))
{
return NULL;
}
else
{
return temp->GetLeftChild();
}
}
else
{
return NULL;
}
};
//返回current结点的右兄弟结点
BinaryTreeNode<T>* GetRightSibling(BinaryTreeNode<T>* current)
{
if (current)
{
BinaryTreeNode<T>* temp = GetParent(current);
if ((NULL == temp) || (current == temp->GetRightChild()))
{
return NULL;
}
else
{
return temp->GetRightChild();
}
}
else
{
return NULL;
}
};
//打印节点数据
void DisplayValue(BinaryTreeNode<T>* node)
{
if (node)
{
cout<<"值等于"<<node->GetValue()<<endl;
}
else
{
cout<<"该节点为NULL!"<<endl;
}
}
//概念: “周游”--系统地访问数据结构中的结点。每个结点都正好被访问到一次
//二叉树的遍历:前序周游二叉树或其子树
//二叉树抽象为以下共性: 所有二叉树都由【根节点或者子树的根节点】、 【左子树】、 【右子树】组成
void PreOrder(BinaryTreeNode<T>* root)
{
//方法一:深度优先周游二叉树 (使用递归)
if (NULL != root)
{
root->DisplayValue(); //访问【根节点或者子树的根节点】
PreOrder(root->GetLeftChild()); //访问【根节点或者子树的根节点】的左节点
PreOrder(root->GetRightChild()); //访问【根节点或者子树的根节点】的右节点
}
};
void PreOrderInStack(BinaryTreeNode<T>* root)
{
//方法二:非递归深度优先周游二叉树
// 栈是实现递归的最常用的结构
// 利用一个栈来记下尚待周游的结点或子树,以备以后访问。
stack<BinaryTreeNode<T>*> s_t;
BinaryTreeNode<T>* temp = root;
while (!s_t.empty() || temp)
{
if (temp)
{
temp->DisplayValue(); //访问【根节点或者子树的根节点】
s_t.push(temp); // 【根节点或者子树的根节点】入栈
temp = temp->GetLeftChild(); //转到【根节点或者子树的根节点】的左节点
}
else
{
temp = s_t.top(); //回到【根节点或者子树的根节点】
s_t.pop(); // 【根节点或者子树的根节点】弹出栈
temp = temp->GetRightChild(); //转到【根节点或者子树的根节点】的右节点
}
}
}
void PreOrderInStack1(BinaryTreeNode<T>* root)
{
//方法二:非递归深度优先周游二叉树
// 栈是实现递归的最常用的结构
// 利用一个栈来记下尚待周游的结点或子树,以备以后访问。
stack<BinaryTreeNode<T>*> s_t;
s_t.push(NULL);

BinaryTreeNode<T>* temp = root;
while(temp)
{
temp->DisplayValue();
if (temp->GetRightChild())
{
s_t.push(temp->GetRightChild());
}
if (temp->GetLeftChild())
{
temp = temp->GetLeftChild();
}
else
{
temp = s_t.top();
s_t.pop();
}
}
}

//二叉树的遍历:中序周游二叉树或其子树
void InOrder(BinaryTreeNode<T>* root)
{
//方法一:深度优先周游二叉树 (使用递归)
if (NULL != root)
{
InOrder(root->GetLeftChild()); //访问【根节点或者子树的根节点】的左节点
root->DisplayValue(); //访问【根节点或者子树的根节点】
InOrder(root->GetRightChild()); //访问【根节点或者子树的根节点】的右节点
}
};
void InOrderInStack(BinaryTreeNode<T>* root)
{
//方法二:非递归深度优先周游二叉树
// 栈是实现递归的最常用的结构
// 利用一个栈来记下尚待周游的结点或子树,以备以后访问。
stack<BinaryTreeNode<T>*> s_t;
BinaryTreeNode<T>* temp = root;
while (!s_t.empty() || temp)
{
if (temp)
{
s_t.push(temp); // 【根节点或者子树的根节点】入栈
temp = temp->GetLeftChild(); //转到【根节点或者子树的根节点】的左节点
}
else
{
temp = s_t.top(); //回到【根节点或者子树的根节点】
s_t.pop(); // 【根节点或者子树的根节点】弹出栈
temp->DisplayValue(); //访问【根节点或者子树的根节点】的左节点
temp = temp->GetRightChild(); //转到【根节点或者子树的根节点】的右节点
}
}
}

//二叉树的遍历:后序周游二叉树或其子树
void PostOrder(BinaryTreeNode<T>* root)
{
//方法一:深度优先周游二叉树 (使用递归)
if (NULL != root)
{
PostOrder(root->GetLeftChild()); //访问【根节点或者子树的根节点】的左节点
PostOrder(root->GetRightChild()); //访问【根节点或者子树的根节点】的右节点
root->DisplayValue(); //访问【根节点或者子树的根节点】
}
};
void PostOrderInStack(BinaryTreeNode<T>* root)
{
//方法二:非递归深度优先周游二叉树
// 栈是实现递归的最常用的结构
// 利用一个栈来记下尚待周游的结点或子树,以备以后访问。
cout<<"NULL"<<endl;
}

//二叉树的遍历:按层次周游二叉树或其子树
void LevelOrder(BinaryTreeNode<T>* root)
{
// 使用队列
deque<BinaryTreeNode<T>*> d_t;
BinaryTreeNode<T>* temp;

if (NULL != root)
{
d_t.push_back(root); // 【根节点或者子树的根节点】入队列尾部
}

while(!d_t.empty())
{
temp = d_t.front(); // 【根节点或者子树的根节点】
d_t.pop_front(); // 【根节点或者子树的根节点】出队列前端
temp->DisplayValue(); //访问【根节点或者子树的根节点】

if (temp->GetLeftChild())
{
d_t.push_back(temp->GetLeftChild());// 【根节点或者子树的根节点】的左节点入队列
}

if (temp->GetRightChild())
{
d_t.push_back(temp->GetRightChild());// 【根节点或者子树的根节点】的右节点入队列
}
} // end while
};

//删除二叉树或其子树
void DeleteBinaryTree(BinaryTreeNode<T>* root)
{
//后序周游二叉树或其子树
if (root)
{
DeleteBinaryTree(root->GetLeftChild()); //递归删除二叉树的左子树
DeleteBinaryTree(root->GetRightChild()); //递归删除二叉树的右子树
delete root; //删除根节点
root = NULL;
}
};
};

#endif // !defined(AFX_BINARYTREE_H__E94D44AE_ADCE_4F3E_A731_699E58A76F6C__INCLUDED_)


  最后,就是对二叉树进行数据录入,测试。

// 二叉树.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <iostream>

#include "BinaryTree.h"

using namespace std;

int main(int argc, char* argv[])
{
//创建一个二叉树
BinaryTree<int> bTree(0);

//判断是否为空
if (bTree.IsEmpty())
{
cout<<"binary tree is empty"<<endl;
}
else
{
cout<<"binary tree is not empty"<<endl;
}

//二叉树中插入节点
BinaryTreeNode<int>* pNode;
//新建节点
pNode = new BinaryTreeNode<int>(1);
bTree.GetRoot()->SetLeftChild(pNode);
pNode = new BinaryTreeNode<int>(2);
bTree.GetRoot()->SetRightChild(pNode);
pNode = new BinaryTreeNode<int>(3);
(bTree.GetRoot()->GetLeftChild())->SetLeftChild(pNode);
pNode = new BinaryTreeNode<int>(4);
(bTree.GetRoot()->GetLeftChild())->SetRightChild(pNode);
pNode = new BinaryTreeNode<int>(5);
(bTree.GetRoot()->GetRightChild())->SetLeftChild(pNode);
pNode = new BinaryTreeNode<int>(6);
(bTree.GetRoot()->GetRightChild())->SetRightChild(pNode);
//先序遍历
cout<<endl<<"先序遍历:";
bTree.PreOrder(bTree.GetRoot());
cout<<endl<<"先序遍历(栈):";
bTree.PreOrderInStack(bTree.GetRoot());
//中序遍历
cout<<endl<<"中序遍历:";
bTree.InOrder(bTree.GetRoot());
cout<<endl<<"中序遍历(栈):";
bTree.InOrderInStack(bTree.GetRoot());
//后序遍历
cout<<endl<<"后序遍历:";
bTree.PostOrder(bTree.GetRoot());

//层次遍历
cout<<endl<<"层次遍历:";
bTree.LevelOrder(bTree.GetRoot());
//获取父节点
cout<<endl<<"获取父节点:";
bTree.DisplayValue(bTree.GetParent(pNode));
cout<<"获取左节点:";
bTree.DisplayValue(bTree.GetLeftSibling(pNode));
cout<<"获取右节点:";
bTree.DisplayValue(bTree.GetRightSibling(pNode));
//删除二叉树
bTree.DeleteBinaryTree(bTree.GetRoot());
cout<<endl;
return 0;
}


  总结:测试结果,输出数据,截图。

  

原文地址:https://www.cnblogs.com/Leo_wl/p/2289462.html