二叉樹是結點的有限集合, 該集合或者為空集, 或者是由一個根和兩棵互不相交的稱為該根的左子樹和右子樹的二叉樹組成. 二叉樹可以為空集, 可以有空二叉樹, 也可以有空的左子樹 或/和 又子樹. 二叉樹的性質: 1.第i層至多有2^(i - 1)個結點. 2.高度為h的二叉樹上至多有2*h - 1個結點. 3.包含n個元素的二叉樹高度至少為>=log2(n + 1)取整. 3.任意一顆二叉樹中, 若葉結點的個數為n0, 度為2的結點個數為n2, 則必有n0 = n2 + 1.? 樹與二叉樹區別: 1.樹不能為空樹, 二叉樹可以為空. 2.樹的子樹之間是無序的, 其子樹不分次序. 二叉樹中結點的子樹要分左右子樹.? 滿二叉樹: 高度為h的二叉樹恰好有2^h - 1個結點. 完全二叉樹: 一棵二叉樹中, 只有最下面兩層結點的度可以小于2, 并且最下面一層的葉結點集中在靠左的若干位置上. 擴充二叉樹(2 - 樹): 除葉子結點外, 其余結點都必須有兩個孩子. 樹與二叉樹區別: 1.樹不能為空樹, 二叉樹可以為空. 2.樹的子樹之間是無序的, 其子樹不分次序. 二叉樹中結點的子樹要分左右子樹.? 實現代碼: ~~~ #include "iostream" #include "cstdio" #include "cstring" #include "algorithm" using namespace std; template <class T> struct BTNode { /* data */ BTNode() { lChild = rChild = NULL; } BTNode(const T& x) { element = x; lChild = rChild = NULL; } BTNode(const T& x, BTNode<T>* l, BTNode<T>* r) { element = x; lChild = l; rChild = r; } T element; BTNode<T>* lChild, *rChild; }; template <class T> class BinaryTree { public: BinaryTree() { root = NULL; } bool IsEmpty() const; // 判斷是否為空, 是返回true void Clear(); // 移去所有結點, 成為空二叉樹 bool Root(T& x) const; // 若二叉樹為空, 則x為根的值, 返回true BTNode<T>* Root(); int Size(); int Count() { return Count(root); } void MakeTree(const T& x, BinaryTree<T>& left, BinaryTree<T>& right); // 構造一顆二叉樹, 根的值為x, left & right為左右子樹 void BreakTree(T& x, BinaryTree<T>& left, BinaryTree<T>& right); // 拆分二叉樹為三部分, x為根的值, left & right為左右子樹 void PreOrder(void (*Visit)(T& x)); // 先序遍歷二叉樹 void InOrder(void (*Visit)(T& x)); // 中序遍歷二叉樹 void PostOrder(void (*Visit)(T& x)); // 后序遍歷二叉樹 /* data */ protected: BTNode<T>* root; private: void Clear(BTNode<T>* t); int Size(BTNode<T> *t); // 返回二叉樹結點個數 int Count(BTNode<T> *t); // 返回二叉樹只有一個孩子的結點個數 void PreOrder(void (*Visit)(T &x), BTNode<T> *t); void InOrder(void (*Visit)(T &x), BTNode<T> *t); void PostOrder(void (*Visit)(T &x), BTNode<T> *t); }; template <class T> void Visit(T &x) { cout << x << '\t'; } template <class T> BTNode<T>* BinaryTree<T>::Root() { return root; } template <class T> bool BinaryTree<T>::Root(T &x) const { if(root) { x = root -> element; return true; } return false; } template <class T> void BinaryTree<T>::Clear(BTNode<T>* t) { if(t) { Clear(t -> lChild); Clear(t -> rChild); cout << "delete" << t -> element << "..." << endl; delete t; } } template <class T> void BinaryTree<T>::MakeTree(const T& x, BinaryTree<T>& left, BinaryTree<T>& right) { if(root || &left == &right) return; root = new BTNode<T>(x, left.root, right.root); left.root = right.root = NULL; } template <class T> void BinaryTree<T>::BreakTree(T& x, BinaryTree<T>& left, BinaryTree<T>& right) { if(!root || &left == &right || left.root || right.root) return; x = root -> element; left.root = root -> lChild; right.root = root -> rChild; delete root; root = NULL; } template <class T> void BinaryTree<T>::PreOrder(void (*Visit)(T& x)) { PreOrder(Visit, root); } template <class T> void BinaryTree<T>::PreOrder(void (*Visit)(T& x), BTNode<T>* t) { if(t) { Visit(t -> element); PreOrder(Visit, t -> lChild); PreOrder(Visit, t -> rChild); } } template <class T> void BinaryTree<T>::InOrder(void (*Visit)(T& x)) { InOrder(Visit, root); } template <class T> void BinaryTree<T>::InOrder(void (*Visit)(T& x), BTNode<T>* t) { if(t) { InOrder(Visit, t -> lChild); Visit(t -> element); InOrder(Visit, t -> rChild); } } template <class T> void BinaryTree<T>::PostOrder(void (*Visit)(T& x)) { PostOrder(Visit, root); } template <class T> void BinaryTree<T>::PostOrder(void (*Visit)(T& x), BTNode<T>* t) { if(t) { PostOrder(Visit, t -> lChild); PostOrder(Visit, t -> rChild); Visit(t -> element); } } template <class T> int BinaryTree<T>::Size() { return Size(root); } template <class T> int BinaryTree<T>::Size(BTNode<T> *t) { if(!t) return 0; return Size(t -> lChild) + Size(t -> rChild) + 1; } template <class T> int BinaryTree<T>::Count(BTNode<T> *t) { if(!t) return 0; if(((t -> lChild) && (!t -> rChild)) || ((!t -> lChild) && (t -> rChild))) return 1; return Count(t -> lChild) + Count(t -> rChild); } int main(int argc, char const *argv[]) { BinaryTree<char> a, b, x, y, z; // 構造過程見課本75頁. char e; y.MakeTree('E', a, b); z.MakeTree('F', a, b); x.MakeTree('C', y, z); y.MakeTree('D', a, b); // 用y前y已經被置空 z.MakeTree('B', y, x); cout << endl << "PreOrder\t"; z.PreOrder(Visit); cout << endl << "InOrder\t\t"; z.InOrder(Visit); cout << endl << "PostOrder\t"; z.PostOrder(Visit); cout << endl; cout << "Tree's size = " << z.Size() << endl; cout << "Tree's count = " << z.Count() << endl; z.BreakTree(e, y, x); cout << endl << "PreOrder\t"; z.PreOrder(Visit); cout << endl << "InOrder\t\t"; z.InOrder(Visit); cout << endl << "PostOrder\t"; z.PostOrder(Visit); cout << endl; cout << "Tree's size = " << z.Size() << endl; cout << "Tree's count = " << z.Count() << endl; return 0; } ~~~