1 基本定义
①二叉树是n（n>=0）个结点的有限集，当n=0时，二叉树为空。当n>0时，二叉树是由一个根节点及至多两颗子树组成，且左右子树都是二叉树。
不同于树，二叉树中的结点要区分左子树和右子树，即使只有一颗子树，左单子树不同于右单子树。
②树的一些基本术语：
结点：包含了数据元素及若干个指向其子树的分支。
结点的度：结点的子树数目或分支个数。
树的度：在树中取各结点的度的最大值。
结点的路径：从根结点到该结点所经分支和结点构成的结点的路径。
结点的层次：设根结点的层次为1，则其子树的根结点层次为2，第L层结点的子树的根结点层次为L。
树的深度：树中结点（该结点必为叶子结点）的最大层次。
无序树：子树之间不存在次序关系（子树能够调换）
有序树：子树之间存在次序关系（子树不能调换）
③几种特殊形态的二叉树
满二叉树：一棵深度为k的二叉树，若每一层上的结点树都达到最大则称其为满二叉树。
完全二叉树：一棵具有n个结点且深度为k的二叉树，若前k-1层的结点树都达到最大，剩余的结点在第k层中从左到右连续分布则称其为完全二叉树。
拟满二叉树：一棵具有n个结点且深度为k的二叉树，若前k-1层的结点树都达到最大，剩余的结点在第k层中随机分布则称其为完全二叉树。
正则二叉树：在一棵二叉树中，如果只存在度为0和度为2的结点，则称其为正则二叉树。
平衡二叉树：在一棵二叉树中，若任一子树均满足：|左子树的深度 - 右子树的深度| <= 1，则称其为平衡二叉树。
2 二叉树的存储结构
2.1 二叉树的顺序存储结构
const int MAXSIZE = 100;
template<class ElemType>
struct SqBiTree
{
ElemType* base;
int nodeNum; //二叉树中结点树
};
①为了能够在存储结构中表达结点之间的逻辑关系，必须将二叉树的结点按照一定的规律安排在顺序存储单元中。
②二叉树的顺序存储结构对于具有n个结点的普通二叉树而言，为保证既存储数据，又表达数据元素之间的关系，必须为其分配2^n - 1个顺序存储单元，空间复杂度为O(2^n)。因此顺序存储结构对于普通二叉树而言并不理想，因此二叉树大多采用链式存储结构。
2.2 二叉树的链式存储结构
2.2.1 分类
①二叉链表：二叉树的结点包含数据元素及指向其左、右子树的分支。C++模板方式定义如下：
template<class T>
struct BTnode
{
T data;
BTnode<T> *Lchild, *Rchild;
};
②三叉链表：在二叉链表的基础上增设了一个双亲指针域
③静态二叉树表：在结点包括游标域的结构类型向量中用游标代替指针，同样可以表示二叉链表和三叉链表。静态二叉树表常用于数据对象中的元素个数是限定的情况，或用于不支持指针的高级语言中。
2.2.2 二叉链表类的定义
//BinaryTree.h
#ifndef _BINARYTREE_H_
#define _BINARYTREE_H_
#include <stack>
#include <queue>
#include "BTnode.h"
using namespace std;
template<class T>
class BinaryTree
{
public:
BinaryTree():m_root(NULL){}
BinaryTree(const BinaryTree &rhs)
{
m_root = _Copy(rhs.m_root);
}
BinaryTree& operator=(const BinaryTree& rhs)
{
if (&rhs == this)
{
return *this;
}
_Destroy(m_root);
m_root = _Copy(rhs.m_root);
return *this;
}
~BinaryTree()
{
_Destroy(m_root);
}
void Create1(T ch[], const T&);
void Create2(T ch1[], T ch2[], int);
void Clear()
{
_Destroy(m_root);
}
bool IsEmpty() const
{
return m_root == NULL;
}
BTnode<T>* Root() const
{
return m_root;
}
BTnode<T>* Locate(T& e)
{
return _Locate(m_root, e);
}
int Depth()
{
return _Depth(m_root);
}
BTnode<T>* Parent(BTnode<T>* p)
{
return _Parent(m_root, p);
}
BTnode<T>* LeftChild(BTnode<T>* p)
{
return p->Lchild;
}
BTnode<T>* RightChild(BTnode<T>* p)
{
return p->Rchild;
}
BTnode<T>* LeftSibling(BTnode<T>* p);
BTnode<T>* RightSibling(BTnode<T>* p);
void PreorderTraverse(void (*visit)(const T&));
void PreorderTraverseNonRecursive(void (*visit)(const T&));
void InorderTraverse(void (*visit)(const T&));
void InorderTraverseNonRecursive(void (*visit)(const T&));
void PostorderTraverse(void (*visit)(const T&));
void PostorderTraverseNonRecursive(void (*visit)(const T&));
void LevelTraverse(void (*visit)(const T&));
bool InsertChild(BTnode<T>* p, const int&, BinaryTree<char>&);
void DeleteChild(BTnode<T>*p, int);
private:
BTnode<T> *m_root;
BTnode<T>* _Copy(BTnode<T>*);
void _Create1(BTnode<T>* &, T ch[], const T&, int&);
void _Create2(BTnode<T>* &, T ch1[], T ch2[], int, int, int&);
void _Destroy(BTnode<T>* &);
int _Depth(BTnode<T>*);
BTnode<T>* _Locate(BTnode<T>*, const T&);
BTnode<T>* _Parent(BTnode<T>*, BTnode<T>*);
void _PreorderTraverse(BTnode<T>* R, void (*visit)(const T& e));
void _InorderTraverse(BTnode<T>*, void (*visit)(const T&));
void _PostorderTraverse(BTnode<T>*, void (*visit)(const T&));
};
template<class T> void BinaryTree<T>::_PreorderTraverse(BTnode<T>* R, void (*visit)(const T& e))
{
if (R)
{
visit(R->data);
_PreorderTraverse(R->Lchild,visit);
_PreorderTraverse(R->Rchild,visit);
}
}
template<class T> void BinaryTree<T>::PreorderTraverse(void (*visit)(const T& e))
{
_PreorderTraverse(m_root, visit);
}
template<class T> void BinaryTree<T>::_InorderTraverse(BTnode<T>* R, void (*visit)(const T& e))
{
if (R)
{
_InorderTraverse(R->Lchild,visit);
visit(R->data);
_InorderTraverse(R->Rchild,visit);
}
}
template<class T> void BinaryTree<T>::InorderTraverse(void (*visit)(const T& e))
{
_InorderTraverse(m_root,visit);
}
template<class T> void BinaryTree<T>::_PostorderTraverse(BTnode<T>* R, void (*visit)(const T& e))
{
if (R)
{
_PostorderTraverse(R->Lchild,visit);
_PostorderTraverse(R->Rchild,visit);
visit(R->data);
}
}
template<class T> void BinaryTree<T>::PostorderTraverse(void (*visit)(const T& e))
{
_PostorderTraverse(m_root,visit);
}
template<class T> void BinaryTree<T>::_Create1(BTnode<T>* &R, T ch[], const T& c, int& i)
{
if (ch[i] == c) //c is a special character which indicates a null pointer
{
R = NULL;
}
else
{
R = new BTnode<T>;
R->data = ch[i];
_Create1(R->Lchild,ch,c,++i);
_Create1(R->Rchild,ch,c,++i);
}
}
template<class T> void BinaryTree<T>::Create1(T ch[], const T& c)
{
int i = 0;
_Create1(m_root,ch,c,i);
}
template<class T> void BinaryTree<T>::_Destroy(BTnode<T>* &R)
{
if (R)
{
_Destroy(R->Lchild);
_Destroy(R->Rchild);
delete R;
}
R = NULL;
}
template<class T> int BinaryTree<T>::_Depth(BTnode<T>* R)
{
if (!R)
{
return 0;
}
int h1,h2;
h1 = _Depth(R->Lchild);
h2 = _Depth(R->Rchild);
return h1 > h2 ? h1 + 1 : h2 + 1;
}
//中序遍历二叉树--非递归算法
template<class T> void BinaryTree<T>::InorderTraverseNonRecursive(void (*visit)(const T& e))
{
stack<BTnode<T>*> S;
S.push(m_root);
while (!S.empty())
{
BTnode<T>* p = S.top();
while (p)
{
p = p->Lchild;
S.push(p); //向左走到尽头
}
S.pop();
if (!S.empty())
{
p = S.top();
S.pop();
visit(p->data);
S.push(p->Rchild);
}
}
}
//层次遍历二叉树--非递归算法
template<class T> void BinaryTree<T>::LevelTraverse(void (*visit)(const T& e))
{
queue<BTnode<T>*> Q;
if (m_root)
{
Q.push(m_root);
}
while (!Q.empty())
{
BTnode<T>* p = Q.front();
Q.pop();
visit(p->data);
if (p->Lchild)
{
Q.push(p->Lchild);
}
if (p->Rchild)
{
Q.push(p->Rchild);
}
}
}
//返回左兄弟指针
template<class T> BTnode<T>* BinaryTree<T>::LeftSibling(BTnode<T>* p)
{
BTnode<T>* father = Parent(p);
if (father && father->Rchild == p)
{
return father->Lchild;
}
return NULL;
}
template<class T> BTnode<T>* BinaryTree<T>::RightSibling(BTnode<T>* p)
{
BTnode<T>* father = Parent(p);
if (father && father->Lchild == p)
{
return father->Rchild;
}
return NULL;
}
template<class T> BTnode<T>* BinaryTree<T>::_Copy(BTnode<T>* R)
{
if (R == NULL)
{
return NULL;
}
BTnode<T>* p = new BTnode<T>;
p->data = R->data;
p->Lchild = _Copy(R->Lchild);
p->Rchild = _Copy(R->Rchild);
return p;
}
//返回二叉树中元素之为e的结点的指针
template<class T> BTnode<T>* BinaryTree<T>::_Locate(BTnode<T>* bt, const T& e)
{
if (!bt || bt->data == e)
{
return bt;
}
BTnode<T>* p = _Locate(bt->Lchild, e);
if (p)
{
return p;
}
p = _Locate(bt->Rchild, e);
return p;
}
template<class T> BTnode<T>* BinaryTree<T>::_Parent(BTnode<T>* R, BTnode<T>* p)
{
if (R == NULL || R == p)
{
return NULL;
}
if (R->Lchild == p || R->Rchild == p)
{
return R;
}
BTnode<T>* q = _Parent(R->Lchild, p);
if (q)
{
return q;
}
q = _Parent(R->Rchild, p);
return q;
}
template<class T> bool BinaryTree<T>::InsertChild(BTnode<T>* p, const int& LR, BinaryTree<char>& r)
{
BTnode<T> *q,*s;
if (p)
{
q = r.Root(); //取根节点
s = _Copy(q); //对象复制
if (LR == 0)
{
s->Rchild = p->Lchild;
p->Lchild = s;
}
else
{
s->Rchild = p->Rchild;
p->Rchild = s;
}
return true;
}
return false;
}
template<class T> void BinaryTree<T>::DeleteChild(BTnode<T>*p, int which)
{
if (which == 0)
{
_Destroy(p->Lchild);
}
else
{
_Destroy(p->Rchild);
}
}
#endif
2.3 二叉树的遍历
二叉树的遍历分为先序遍历、中序遍历和后序遍历，其区别主要在于遍历根节点的顺序。
3 线索二叉树
通过模板形式定义的结点结构为：
enum PointerTag{Link=0,Thread=1};
template<class T>
struct BiThrnode
{
T data;
BiThrnode<T>* Lchild;
BiThrnode<T>* Rchild;
PointerTag Ltag,Rtag;
};对中序线索二叉树进行遍历的函数如下：
template<class T> void BinaryThrTree<T>::Traverse_InorderBiThrTree(void (*visit)(const T& e))
{
BiThrnode<T>* p;
p = m_T->lchild;
while (p != m_T)
{
while (p->Ltag == Link)
{
p = p->Lchild;
}
visit(p->data);
while (p->Rtag == Thread && p->Rchild != m_T)
{
p = p->Rchild;
visit(p->data);
}
p = p->Rchild;
}
}中序线索化二叉树的两个关联函数描述如下：
template<class T>
void BinaryThrTree<T>::_InorderThreading(BinaryTree<T>* &T)
{
BiThrnode<T>* pre;
BiThrnode<T>* Thrt = new BiThrnode<T>;
Thrt->Ltag = Link;
Thrt->Rtag = Thread;
Thrt->Rchild = Thrt;
if (!T)
{
Thrt->Lchild = Thrt;
}
else
{
Thrt->Lchild = T;
pre = Thrt;
_Threading(T,pre);
pre->Rchild = Thrt;
pre->Rtag = Thread;
Thrt->Rchild = pre;
}
T = Thrt;
}
template<class T>
void BinaryThrTree<T>::_Threading(BiThrnode<T>* &p, BiThrnode<T>* &pre)
{
if (p)
{
_Threading(p->Lchild, pre);
if (!p->Lchild)
{
p->Ltag = Thread;
p->Lchild = pre;
}
if (!pre->Rchild)
{
pre->Rtag = Thread;
pre->Rchild = p;
}
pre = p;
_Threading(p->Rchild, pre);
}
}
转载：http://blog.csdn.net/foreverling/article/details/43229285
