二叉树的存储表示

二叉树的数组存储表示

在数据处理过程中二叉树的大小、形态不发生剧烈的动态变化的场合，适宜采用数组方式来表示二叉树的抽象数据类型
1、完全二叉树的数组存储表示
设有一棵完全二叉树，将其所有结点按照层次自顶向下、同一层自左向右进行按序编号1 - n，得到一个结点的顺序（线性）序列。在数组下标为 i 的位置，存放编号为 i 的完全二叉树的结点。这种存储表示是存储完全二叉树最简单、最省存储的方式，因为可以从一个结点的编号推算出它的父结点、子女、兄弟等结点的编号

数组存储的缺陷：对待一般二叉树来说，有可能导致浪费大量存储空间。

二叉树的链表存储表示

使用链式存储，可以在形态剧烈变化的二叉树中，克服数组存储的缺点

1、根据二叉树的定义，每一个结点都有两个分支，指向左、右子树。所以二叉树的结点至少包括三个域：数组data、左子女指针left、右子女指针right。其称为二叉链表，可以很方便地找到左右子结点，但是找到其父结点很困难。

2、在含有n个结点的二叉链表中有n+1个空链指针域，因为在所有结点的2n个链指针域只有n-1个存有边信息的缘故。

三叉链表

在二叉链表的基础上，增加指向parent的指针，便于查找任意结点的父结点。三链表则有n+2个空链指针域。

二叉树结点定义

template<class T>
struct BinTreeNode{T data;BinTreeNode<T> *leftChild, *rightChild;BinTreeNode(): leftChild(nullptr), rightChild(nullptr){}BinTreeNode(T x, BinTreeNode<T> *l = nullptr, BinTreeNode<T> *r = nullptr):data(x), leftChild(l), rightChild(r){}
};

二叉树类定义

template<class T>
class BinaryTree{
public:BinaryTree(): root(nullptr){}               //构造函数BinaryTree(T value): RefValue(value), root(nullptr){}         //构造函数BinaryTree(BinaryTree<T>& s);          //复制构造函数~Binary(){ destroy(root); } 				//析构函数bool IsEmpty(){ return (root == nullptr) ? true : false; }             //判断二叉树空否BinTreeNode<T>* Parent(BinTreeNode<T> *current)                       //返回父结点{return (root == NULL || root == current)?NULL:Parent(root, current); }BinTreeNode<T>* LeftChild(BinTreeNode<T> *current)                    //返回左子女{return (current != NULL)?current->leftChild:NULL; }BinTreeNode<T>* RightChild(BinTreeNode<T> *current)					  //返回右子女{return (current != NULL)?current->rightChild:NULL; }int Height() { return Height(root); }                                 //返回树高度int Size() {return Size(root); }                                      //返回结点数BinTreeNode<T>* getRoot() const {return root; }                       //取根void preOrder(void (*visit)(BinTreeNode<T>* p))                       //前序遍历{preOrder(root, visit); }void inOrder(void (*visit)(BinTreeNode<T>* p))                        //中序遍历{inOrder(root, visit); }void postOrder(void (*visit)(BinTreeNode<T>* p))                      //后序遍历{postOrder(root, visit); }int Insert(const T& item);                                            //插入新元素BinTreeNode<T>* Find(T& item)const;                                   //搜索
protected:BinTreeNode<T>* root;                                                 //二叉树的根指针T RefValue;                  										  //数据输入停止标志void CreateBinTree(istream& in, BinTreeNode<T>* &subTree);            //从文件读入建树bool Insert(BinTreeNode<T>* &subTree, const T& x);                    //插入void destroy(BinTreeNode<T>* &subTree);								  //删除                      bool Find(BinTreeNode<T>* subTree, const T& x)const;                  //查找BinTreeNode<T>* Copy(BinTreeNode<T>* orignode);                       //复制int Height(BinTreeNode<T>* subTree);								  //返回树高度int Size(BinTreeNode<T> *sunTree);                                    //返回结点数BinTreeNode<T>* Parent(BinTreeNode<T>* subTree, BinTreeNode<T>* current);      //返回父结点BinTreeNode<T>* Find(BinTreeNode<T>* subTree, const T& x)const;         //搜寻xvoid Traverse(BinTreeNode<T>* subTree, ostream& out);                 //前序遍历输出void preOrder(BinTreeNode<T>* subTree, void (*visit)(BinTreeNode<T>* p))               //前序遍历void inOrder(BinTreeNode<T>* subTree, void (*visit)(BinTreeNode<T>* p))                //中序遍历void postOrder(BinTreeNode<T>* subTree, void (*visit)(BinTreeNode<T>* p))              //后序遍历friend istream& operator>>(istream& in, BinaryTree<T>& Tree);			//重载输入操作符friend ostream& operator<<(ostream& out, BinaryTree<T>& Tree);			//重载输出操作符
};

部分成员函数实现

//删除根为subTree的子树
template<class T>
void BinaryTree<T>::destroy(BinTreeNode<T>* &subTree){if(subTree != nullptr){destroy(subTree->leftChild);destroy(subTree->rightChild);delete subTree;}
};//搜索current结点的父结点
template<class T>
BinTreeNode<T>* BinaryTree<T>::Parent(BinTreeNode<T>* subTree, BinTreeNode<T>* current){if(subTree == nullptr){return nullptr;}if(subTree -> leftChild == current || subTree -> rightChild == current){return subTree;}BinTreeNode<T> *p;if((p = Parent(subTree->leftChild, current)) != nullptr) return p;else return Parent(subTree->rightChild, current);
};//搜索并输入根为subTree的二叉树
template<class T>
void BinaryTree<T>::Traverse(BinTreeNode<T> *subTree, ostream& out){if(subTree != nullptr){out << subTree -> data << ' ';            //输出当前结点的数据Traverse(subTree->leftChild, out);	      //输出Traverse(subTree->rightChild, out);}
};//重载输入操作符
template<class T>
istream& operator>>(istream& in, BinaryTree<T>& Tree){CreateBinTree(in, Tree.root);                     //采用广义表表示的建立二叉树的算法return in;
}//重载输出操作符
template<class T>
ostream& operator<<(ostream& out, BinaryTree<T>& Tree){out << "输出二叉树的前序遍历\n";Tree.Traverse(Tree.root, out);out << endl;return out;
}

一种采用广义表表示的建立二叉树的算法

假定有一广义表 A（B（D，E（G，）），C（，F））#
算法基本思路：依次从保存广义表的字符串中输入字符。
1、以字母作为结点的值，k=1时为左子女，k=2时为右子女。
2、遇到左括号，表示子表开始；遇到右括号，表示子表结束。
3、遇到逗号，则表示左子女处理完毕，接着处理右子女，k置为2，直到#。在进入子表之前将根结点入栈，子表处理结束之后退栈。

template<class T>
void BinaryTree<T>::CreateBinTree(istream& in, BinTreeNode<T>* &subTree){stack<BinTreeNode<T>*> s;               //存放根结点的栈subTree = nullptr;						//置空二叉树BinTreeNode<T> *p, *t;int k;									//作为处理左、右子树标记T ch;in >> ch;        						//从in顺序读入一个字符while (ch != RefValue) {switch (ch) {case '(': s.push(p); k = 1; break;			//进入子树case ')': s.pop(); break;					//退出子树case ',': k = 2; break;						//处理右子树default: p = new BinTreeNode<T>(ch);	if (subTree == nullptr) subTree = p;else if (k == 1) {t = s.top();t->leftChild = p;					//链接左子女}else {t = s.top();t->rightChild = p;					//链接右子女}}in >> ch;}
}