1.层次遍历可以用于寻找叶子节点，寻找路径，寻找树的最短最大高度的非递归实现。
2.中序遍历搜索二叉树后是升序的序列。这个特性可以判断搜索二叉树的有效性。
3.使用双向的递归可以遍历每个分支的每个节点。
/*
* Created by krislyy on 2018/11/23.
* 作为图的特殊形式，二叉树的基本组成单元是节点与边；
* 作为数据结构，其基本的组成实体是二叉树节点，而边则
* 对应于节点之间的相互引用
*/
#pragma once
#include<iostream>
#include<queue>
#include<stack>
using namespace std;
template <class T> //树的结构体
struct BinaryTreeNode
{
public:
T _data;
BinaryTreeNode<T>* _leftChild;
BinaryTreeNode<T>* _rightChild;
public:
BinaryTreeNode(const T& data)
:_data(data)
, _leftChild(NULL)
, _rightChild(NULL)
{}
~BinaryTreeNode()
{}
};
template <class T>
class BinaryTree //树的封装
{
public:
BinaryTreeNode<T>* _root;
public:
BinaryTree()
:_root(NULL)
{}
BinaryTree( T*a, size_t size)
{
size_t index = 0;
_root = _CreateBiTree(a, index, size);
}
BinaryTree(const BinaryTree& tmp)
:_root(NULL)
{
_root=_Copy(tmp._root);
}
~BinaryTree()
{
Destory();
}
BinaryTree<T>& operator=( BinaryTree<T> tmp)
{
swap(_root, tmp._root);
return *this;
}
void InOrder()//中序遍历递归方法
{
_InOrder(_root);
cout << endl;
}
void PreOrder()//前序遍历递归方法
{
_PreOrder(_root);
cout << endl;
}
void PosOrder()//后序遍历递归方法
{
_PosOrder(_root);
cout << endl;
}
void LevelOrder()//层序遍历
{
queue<BinaryTreeNode<T>*> s ;
s.push(_root);
while (!s.empty())
{
BinaryTreeNode<T>* cur = s.front();
cout<<cur->_data<<' ';
if (cur->_leftChild)
s.push(cur->_leftChild);
if (cur->_rightChild)
s.push(cur->_rightChild);
s.pop();
}
cout << endl;
}
void Size()//节点数
{
int size = 0;
cout<<_Size(_root,size)<<endl;
}
void Hight()//深度 /高度
{
cout << _Hight(_root) << endl;
}
void Destory()//销毁
{
_Destory(_root);
_root=NULL;
}
void LeafNum()//叶子节点数
{
int num = 0;
_LeafNum(_root, num);
cout <<num<<endl;
}
void PreOrderNonR()//前序 非递归 （借用栈）
{
if (_root == NULL)
return;
stack<BinaryTreeNode<T>*> s ;
s.push(_root);
while (!s.empty())
{
BinaryTreeNode<T>* cur;
cur=s.top();
s.pop();
cout << cur->_data << ' ';
if (cur->_rightChild)
s.push(cur->_rightChild);
if (cur->_leftChild)
s.push(cur->_leftChild);
}
cout << endl;
}
void InOrderNonR() //中序 非递归
{
if (_root == NULL)
return;
stack<BinaryTreeNode<T>*> s;
s.push(_root);
BinaryTreeNode<T>* prev=NULL;
BinaryTreeNode<T>* cur=NULL;
while (!s.empty())
{
cur = s.top();
if(prev != cur&&cur->_leftChild) //左不空 压左
{
s.push(cur->_leftChild);
}
else //左空 出栈 输出
{
cout << cur->_data << ' ';
s.pop();
if (!s.empty())
prev = s.top();//prev始终为出栈后的栈顶
if (cur->_rightChild)// cur右不空 压右
{
s.push(cur->_rightChild);
}
}
}
cout << endl;
}
void PosOrderNonR() //后续 非递归
{
if (_root == NULL)
return;
stack<BinaryTreeNode<T>*> s;
BinaryTreeNode<T>* cur = NULL;
BinaryTreeNode<T>* prev = NULL;
BinaryTreeNode<T>* tmp = NULL;
s.push(_root);
while (!s.empty())
{
cur = s.top();
if (prev != cur&&cur->_leftChild != NULL)//1.左不空且prev！=cur 压左
s.push(cur->_leftChild);
else//左空
{
if (cur->_rightChild!=tmp &&cur->_rightChild)//右不空 且 cur->right！=tmp 压右
{
s.push(cur->_rightChild);
}
else //右空 输出 cur
{
cout << cur->_data << ' ';
tmp = s.top(); //tmp(判断是否压右)始终为出栈前的栈顶
s.pop();
if (!s.empty())
{
prev = s.top();//prev（判断是否压右）始终为出栈后栈顶
}
}
}
}
cout << endl;
}
protected://以下为递归的调用函数
BinaryTreeNode<T>* _CreateBiTree(const T* tmp, size_t& index, size_t size)
{
BinaryTreeNode<T>* root = NULL;
if (index < size&&tmp[index]!='#')
{
root = new BinaryTreeNode<T>(tmp[index]);
root->_leftChild = _CreateBiTree(tmp, ++index, size);
root->_rightChild = _CreateBiTree(tmp, ++index, size);
}
return root;
}
void _InOrder(BinaryTreeNode<T>* &node)
{
if (node == NULL)
return;
_InOrder(node->_leftChild);
cout << node->_data << ' ';
_InOrder(node->_rightChild);
}
void _PreOrder(BinaryTreeNode<T>* &node)
{
if (node == NULL)
return;
cout << node->_data<<' ';
_PreOrder(node->_leftChild);
_PreOrder(node->_rightChild);
}
void _PosOrder(BinaryTreeNode<T>* &node)
{
if (node == NULL)
return;
_PosOrder(node->_leftChild);
_PosOrder(node->_rightChild);
cout << node->_data << ' ';
}
int _Size(BinaryTreeNode<T>* root,int & size)
{
if (root == NULL)
return 0;
size++;
_Size(root->_leftChild, size);
_Size(root->_rightChild, size);
return size;
}
int _Hight(BinaryTreeNode<T>* root)
{
int hight = 1;
if (root == NULL)
return 0;
hight += _Hight(root->_leftChild);
int ritHight = 0;
ritHight+= _Hight(root->_rightChild);
if (hight < ritHight)
hight = ritHight;
return hight;
}
void _Destory(BinaryTreeNode<T>* root)
{
if (root == NULL)
return;
BinaryTreeNode<T>* del = root;
_Destory(del->_leftChild);
_Destory(del->_rightChild);
delete root;
return;
}
void _LeafNum(BinaryTreeNode<T>* root,int& num)
{
if (root == NULL)
return ;
if (root->_leftChild == NULL&&root->_rightChild == NULL)
++num;
_LeafNum(root->_leftChild,num);
_LeafNum(root->_rightChild,num);
return ;
}
BinaryTreeNode<T>* _Copy(BinaryTreeNode<T>* root)
{
if (root == NULL)
return NULL;
BinaryTreeNode<T>* newRoot = NULL;
newRoot = new BinaryTreeNode<T>(root->_data);
newRoot->_leftChild = _Copy(root->_leftChild);
newRoot->_rightChild = _Copy(root->_rightChild);
return newRoot;
}
};
测试代码
void CheckBinaryTree(){
int l[j] = { 1, 2, 3,'#', '#', 4, '#', '#', 5, 6 };
int s[18] = { 1, 2, 3, 4, '#', '#', 5, '#', '#', 6,'#','#' ,7, 8, '#', '#', 9, 10 };
BinaryTree<int> t1;
BinaryTree<int> t2(s, 18);
BinaryTree<int> t3(t2);
t1 = t2;
t2.PreOrder();
t2.InOrder();
t2.PosOrder();
t2.LevelOrder();
t2.Size();
t2.Hight();
t2.Destory();
t3.InOrder();
t1.InOrder();
t3.LeafNum();
t3.PreOrderNonR();
t3.InOrderNonR();
t3.PosOrderNonR();
}
构造后形成的树如下结构
1
/ \
2 7
/ \ / \
3 6 8 9
/ \ /
4 5 10
输出：
pre : 1 2 3 4 5 6 7 8 9 10
in : 4 3 5 2 6 1 8 7 10 9
post : 4 5 3 6 2 8 10 9 7 1
level : 1 2 7 3 6 8 9 4 5 10
网友评论