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