#include<iostream>
#include<string.h>
#include<queue>
#include<stack>
using namespace std;
template<typename T>
struct BinaryTreeNode//给出二叉树节点的结构体
{
BinaryTreeNode(const T& value)
:_value(value)
,_pLeft(NULL)
,_pRight(NULL)
{}
T _value;//值
BinaryTreeNode<T>* _pLeft;//左孩子
BinaryTreeNode<T>* _pRight;//右孩子
};
template<typename T>
class BinaryTree
{
public:
typedef BinaryTreeNode<T> Node;
BinaryTree()
{}
BinaryTree(const T arr[], size_t size, const T& invalid)//构造函数
{
size_t idex = 0;
_CreateBinaryTree(_pRoot, arr, size, idex, invalid);//前序创建二叉树
}
BinaryTree(const BinaryTree<T>& bt)//拷贝构造
{
_pRoot = _CopyBinaryTree(bt._pRoot);//先序
}
BinaryTree<T>& operator=(const BinaryTree<T>& bt)
{
if(this != &bt)
{
_DestoryBinaryTree(_pRoot);
_pRoot = _CopyBinaryTree(bt._pRoot);
}
return *this;
}
~BinaryTree()
{
_DestoryBinaryTree(_pRoot);
}
void PreOrder_Nor()//先序遍历 非递归
{
if(_pRoot == NULL)//空树
return;
stack<Node*> s;//用栈消除递归
s.push(_pRoot);
while(!s.empty())//当栈不为空
{
Node* pCur = s.top();//取栈顶元素
cout<<pCur->_value<<" ";//访问
s.pop();//出栈
if(pCur->_pRight)//保存右孩子
s.push(pCur->_pRight);
if(pCur->_pLeft)//保存左孩子
s.push(pCur->_pLeft);
}
}
void InOrder_Nor()//中序遍历 非递归
{
if(_pRoot == NULL)
return;
stack<Node*> s;
Node* pCur = _pRoot;
while(pCur || !s.empty()) //栈不为空 或 pCur存在
{
while(pCur)//找最左边的节点，并保存路径上所有节点
{
s.push(pCur);
pCur = pCur->_pLeft;
}
pCur = s.top(); //取栈顶
cout<<pCur->_value<<" "; //访问
s.pop();//出栈
//方法1 右子树不存在 单独处理
while(NULL == pCur->_pRight && !s.empty())//处理左单支树可以一次性连续处理 注意条件应加上栈不为空，否则最上面节点右子树为空 但进来后栈为空
{
pCur = s.top();//取栈顶元素
cout<<pCur->_value<<" ";//访问
s.pop();//出栈
}
pCur = pCur->_pRight;//右子树存在
//方法2 直接处理右子树
//pCur = pCur->_pRight;
}
cout<<endl;
}
void PostOrder_Nor()//后序遍历 非递归
{
if(_pRoot == NULL)
return;
stack<Node*> s;
Node* pCur = _pRoot;
Node* prev = NULL;//临时变量 保存刚刚访问过的节点
while(pCur || !s.empty())
{
while(pCur)//保存左边路径上的节点
{
s.push(pCur);
pCur = pCur->_pLeft;
}
if(!s.empty())//???????
{
pCur = s.top();
if(pCur->_pRight == NULL || pCur->_pRight == prev)
{
cout<<pCur->_value<<" ";
prev = pCur;
s.pop();
pCur = NULL;//?????
}
else
pCur = pCur->_pRight;
}
}
}
bool IsCompleteBinaryTree()
{
if(_pRoot == NULL)
return true;
queue<Node*> q;
Node* pCur = _pRoot;
q.push(pCur);
bool flag = false;
while(!q.empty())
{
pCur = q.front();
if(flag)
{
if(pCur->_pLeft || pCur->_pRight)
return false;
}
else
{
if(pCur->_pLeft && pCur->_pRight)
{
q.push(pCur->_pLeft);
q.push(pCur->_pRight);
}
else if(pCur->_pLeft)
{
q.push(pCur->_pLeft);
flag = true;
}
else if(pCur->_pRight)
return false;
else
flag = true;
}
q.pop();
}return true;
}
void PreOrder()
{
cout<<"前序遍历:"<<endl;
_PreOrder(_pRoot);
cout<<endl;
}
void InOrder()
{
cout<<"中序遍历:"<<endl;
_InOrder(_pRoot);
cout<<endl;
}
void PostOrder()
{
cout<<"后序遍历:"<<endl;
_PostOrder(_pRoot);
cout<<endl;
}
void LevelOrder()
{
cout<<"层序遍历:"<<endl;
_LevelOrder(_pRoot);
cout<<endl;
}
Node* Find(Node* pRoot, const T& value)//查找值为value的节点//
{
//Node* pCur = NULL;
if(pRoot == NULL)
return NULL;
if(pRoot->_value == value)
return pRoot;
Node* pCur = Find(pRoot->_pLeft,value);
if(pRoot->_pLeft && pCur->_value == value)
return pCur;
if(pRoot->_pRight)
return Find(pRoot->_pRight, value);
}
Node* Parent(Node* pNode)//
{
_pRoot = _Parent(_pRoot,pNode);
}
Node* _pRoot;
Node* GetLeftChild(Node* pCur)//左孩子
{
return (pCur == NULL)?NULL:pCur->_pLeft;
}
Node* GetRightChild(Node* pCur)//右孩子
{
return (pCur == NULL)?NULL:pCur->_pRight;
}
size_t _Height(Node* pRoot)//求树高
{
if(pRoot == NULL)//树为空
return 0;
if(pRoot->_pLeft == NULL && pRoot->_pRight == NULL)//只有一个节点
return 1;
//递归求出左子树或右子树中较大的一个的高度 加一即为树高
size_t LeftHeight = _Height(pRoot->_pLeft);//求左子树高度
size_t RightHeight = _Height(pRoot->_pRight);
return (LeftHeight > RightHeight) ? LeftHeight+1 : RightHeight+1;
}
size_t GetLeefCount(Node* pRoot)//叶子节点个数
{
if(pRoot == NULL)
return 0;
if(pRoot->_pLeft == NULL && pRoot->_pRight == NULL)
return 1;
return GetLeefCount(pRoot->_pLeft)+GetLeefCount(pRoot->_pRight);
}
size_t GetKLevelCount(Node* pRoot, size_t k)//获取第k层节点个数
{
if(pRoot == NULL)
return 0;
if(k == 1)
return 1;
return GetKLevelCount(pRoot->_pLeft, k-1) + GetKLevelCount(pRoot->_pRight, k-1);
}
void BinaryMirror_Nor(Node* pRoot)//求镜像 非递归
{
if(pRoot == NULL)
return;
queue<Node*> q;
q.push(pRoot);
while(!q.empty())
{
Node* pCur = q.front();
if(pCur->_pLeft)
q.push(pCur->_pLeft);
if(pCur->_pRight)
q.push(pCur->_pRight);
std::swap(pCur->_pLeft, pCur->_pRight);
q.pop();
}
}
//递归 求二叉树镜像 先序
void BinaryMirror(Node* pRoot)
{
if(pRoot)
{
std::swap(pRoot->_pLeft, pRoot->_pRight);
BinaryMirror(pRoot->_pLeft);
BinaryMirror(pRoot->_pRight);
}
}
private:
void _CreateBinaryTree(Node* &pRoot, const T arr[], size_t size, size_t &idex, const T& invalid)//创建
{
if(idex < size && invalid != arr[idex])//条件：当数组下标不超过元素个数并且当前值不为无效值
{
//创建根节点
pRoot = new Node(arr[idex]);
//递归创建左子树
_CreateBinaryTree(pRoot->_pLeft, arr, size, ++idex, invalid);
//递归创建右子树
_CreateBinaryTree(pRoot->_pRight, arr, size, ++idex, invalid);
}
}
Node* _CopyBinaryTree(Node* pRoot)//拷贝
{
Node* pNewRoot = NULL;
if(pRoot)//原二叉树节点不为空
{
pNewRoot = new Node(pRoot->_value);
pNewRoot->_pLeft = _CopyBinaryTree(pRoot->_pLeft);
pNewRoot->_pRight = _CopyBinaryTree(pRoot->_pRight);
}
return pNewRoot;
}
void _DestoryBinaryTree(Node*& pRoot)//销毁
{
if(pRoot != NULL)
{
_DestoryBinaryTree(pRoot->_pLeft);
_DestoryBinaryTree(pRoot->_pRight);
delete pRoot;
pRoot = NULL;
}
}
void _PreOrder(Node* pRoot)
{
if(pRoot)
{
cout<<pRoot->_value<<" ";
_PreOrder(pRoot->_pLeft);
_PreOrder(pRoot->_pRight);
}
}
void _InOrder(Node* pRoot)
{
if(pRoot)
{
_InOrder(pRoot->_pLeft);
cout<<pRoot->_value<<" ";
_InOrder(pRoot->_pRight);
}
}
void _PostOrder(Node* pRoot)
{
if(pRoot)
{
_PostOrder(pRoot->_pLeft);
_PostOrder(pRoot->_pRight);
cout<<pRoot->_value<<" ";
}
}
void _LevelOrder(Node* pRoot)
{
if(pRoot == NULL)
return;
queue<Node*> q;//
q.push(pRoot);//将二叉树节点放入队列
while(!q.empty())//队列不为空
{
Node* pCur = q.front();//队头赋给一个节点指针
if(pCur->_pLeft)
q.push(pCur->_pLeft);//保存左节点
if(pCur->_pRight)
q.push(pCur->_pRight);//保存右节点
cout<<pCur->_value<<" ";
q.pop();//弹出栈顶元素
}
}
Node* _Parent(Node* pRoot, Node* pCur)//获取某节点的双亲
{
assert(pCur);//1、当前节点不为空
if(pRoot == NULL || pCur == pRoot)//2、空树或要找的节点为根节点
return NULL;
if(pRoot->_pLeft == pCur || pRoot->_pRight == pCur)//3、双亲节点为根节点
return pRoot;
Node* Parent = _Parent(pRoot->_pLeft, pCur);
if(Parent)
return Parent;
return _Parent(pRoot->_pRight, pCur);
}
};
#include"test.h"
void FunTest()
{
char* arr = "124##5##36##7";
char* arr1 = "124##5##3";
size_t size = strlen(arr);
BinaryTree<char> bt(arr, size, '#');
BinaryTree<char> bt1(bt);
BinaryTree<char> bt2(arr1, strlen(arr1), '#');
bt2 = bt;
//bt.PreOrder();
//bt.PreOrder_Nor();
//bt.InOrder();
//bt.InOrder_Nor();
//bt.PostOrder();
//bt.PostOrder_Nor();
//bt.LevelOrder();
//cout<<bt.Find(bt._pRoot,'7')->_value<<endl;//
cout<<bt.IsCompleteBinaryTree()<<endl;
}
void FunTest1()
{
char* arr = "124###35##6";
BinaryTree<char> bt(arr, strlen(arr), '#');
//BinaryTreeNode<char>* pNode = bt.GetLeftChild(bt._pRoot->_pRight);
//cout<<pNode->_value<<endl;
cout<<bt._Height(bt._pRoot)<<endl;
cout<<bt.GetLeefCount(bt._pRoot)<<endl;
cout<<bt.GetKLevelCount(bt._pRoot,3)<<endl;
//bt.BinaryMirror(bt._pRoot);
}
int main()
{
FunTest();
system("pause");
return 0;
}
转载请注明原文地址: https://www.6miu.com/read-78928.html
