二叉树的定义
以递归形式给出的：一棵二叉树是结点的一个有限集合，该集合或者为空，或者是由一个根结点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成。二又树的特点是每个结点最多有两个子女，分别称为该结点的左子女和右子女。在二又树中不存在度大于2的结点，并且二又树的子树有左、右之分，其子树的次序不能颠倒。二又树是分支数最大不超过2的有根有序树。它可能有5种不同的形态。
遇到空子树，应在编号时假定有此子树进行编号，而在顺序存储时当作有此子树那样把位置留出来。这样才能反映二叉树结点之间的相互关系，由其存储位置找到它的父结点、子女、兄弟结点的位置。但这样做有可能会消耗大量的存储空间。例如：单支二叉树，会浪费很多空间。
如果根节点编号是从1开始有有以下结论：
中间节点一定在倒数第二层，最后一个节点的数就是总节点的个数，总结点数除2就是中间节点的数的个数，父节点的节点数*2<总节点个数，当前节点一定有两个孩子，如果=就只有一个孩子，如果<就没有一个孩子。
二叉树的链表存储表示
1 template<typename T> 2 struct BinTreeNode 3 { 4 T data; //结点中存储的数据 5 BinTreeNode<T> *leftChild, *rightChild; //左子树和右子树 6 BinTreeNode() :leftChild(NULL), rightChild(NULL) {} //无参构造函数 7 BinTreeNode(T x, BinTreeNode<T> *l = NULL, BinTreeNode<T> *r = NULL) :data(x), leftChild(l), rightChild(r) {} //带默认值的有参构造参数 8 };
二叉树的基本框架
//二叉树 //结点类型 template <typename T> struct BinTreeNode { T data; //结点中存储的数据 BinTreeNode<T> *leftChild, *rightChild; //左子树和右子树 BinTreeNode() : leftChild(NULL), rightChild(NULL) {} //无参构造函数 BinTreeNode(T x, BinTreeNode<T> *l = NULL, BinTreeNode<T> *r = NULL) : data(x), leftChild(l), rightChild(r) {} //带默认值的有参构造参数 }; //二叉树类 template <typename T> class BinaryTree { public: //==========二叉树构造与析构==========// //构造函数 BinaryTree() : root(NULL) {} //指定结束标志的构造函数 BinaryTree(T value) : RefValue(value), root(NULL) {} //析构函数 ~BinaryTree() { Destroy(root); } //==========二叉树的创建==========// //使用广义表创建二叉树，以'#'字符代表结束 void CreateBinTree() { CreateBinTree(root); } //前序遍历创建二叉树(前序遍历的应用)，用#表示空结点 void CreateBinTree_PreOrder() { CreateBinTree_PreOrder(root); } //使用先序遍历和中序遍历创建二叉树 void CreateBinTreeBy_Pre_In(const char *pre, const char *in) { int n = strlen(pre); CreateBinTreeBy_Pre_In(root, pre, in, n); } //使用后序遍历和中序遍历创建二叉树 void CreateBinTreeBy_Post_In(const char *post, const char *in) { int n = strlen(post); CreateBinTreeBy_Post_In(root, post, in, n); } //==========二叉树的遍历==========// //先序遍历（递归） void PreOrder() { PreOrder(root); } //中序遍历(递归) void InOrder() { InOrder(root); } //后序遍历（递归） void PostOrder() { PostOrder(root); } //先序遍历(非递归) void PreOrder_NoRecurve() { PreOrder_NoRecurve(root); } //中序遍历(非递归) void InOrder_NoRecurve() { InOrder_NoRecurve(root); } //后序遍历(非递归) void PostOrder_NoRecurve() { PostOrder_NoRecurve(root); } //层次遍历(非递归) void LevelOrder() { LevelOrder(root); } //==========获取结点==========// //获取二叉树的根节点 BinTreeNode<T> *getRoot() const { return root; } //获取current结点的父节点 BinTreeNode<T> *Parent(BinTreeNode<T> *current) { return (root == NULL || root == current) ? NULL : Parent(root, current); //如果没有根节点或current结点就是root结点，就没有父节点 } //获取current结点的左结点 BinTreeNode<T> *LeftChild(BinTreeNode<T> *current) { return (current != NULL) ? current->leftChild : NULL; } //获取current结点的右结点 BinTreeNode<T> *RightChild(BinTreeNode<T> *current) { return (current != NULL) ? current->rightChild : NULL; } //==========成员函数==========// //销毁函数 void Destroy() { Destroy(root); } //拷贝二叉树(前序遍历的应用) BinaryTree(BinaryTree<T> &s) { root = Copy(s.getRoot()); } //判断两颗二叉树是否相等(前序遍历的应用) bool operator==(BinaryTree<T> &s) { return (equal(this->getRoot(), s.getRoot())); } //计算二叉树的结点的个数(后序遍历的应用) int Size() { return Size(root); } //计算二叉树的高度（后序遍历的应用） int Height() { return Height(root); } //判断二叉树是否为空 bool Empty() { return (root == NULL) ? true : false; } //以广义表的形式输出二叉树(前序遍历的应用) void PrintBinTree() { PrintBinTree(root); } private: BinTreeNode<T> *root; //根节点 T RefValue; //数据输入停止的标志，需要一个构造函数 };
二叉树的创建
1.使用广义表创建
从广义表
A（B（D，E（G，）），C（，F））# 建立起来的二叉树。
算法基本思路：
1.若是字母（假定以字母作为结点的值），则表示是结点的值，为它建立一个新的结点，并把该结点作为左子女（当k=1）或右子女（当k=2）链接到其父结点上。
2.若是左括号"("，则表明子表的开始，将k置为1；若遇到的是右括号")"，则表明子表结束。
3.若遇到的是逗号","，则表示以左子女为根的子树处理完毕，应接着处理以右子女为根的子树，将k置为2。如此处理每一个字符，直到读入结束符“#”为止。
在算法中使用了一个栈s，在进入子表之前将根结点指针进栈，以便括号内的子女链接之用。在子表处理结束时退栈。
1 //使用广义表创建二叉树函数,这里以“字符”创建二叉树,以'#'字符代表结束 2 void CreateBinTree(BinTreeNode<T>* &BT) 3 { 4 stack< BinTreeNode<T>* > s; 5 BT = NULL; 6 BinTreeNode<T> *p, *t; //p用来记住当前创建的节点，t用来记住栈顶的元素 7 int k; //k是处理左、右子树的标记 8 T ch; 9 cin >> ch; 10 11 while (ch != RefValue) 12 { 13 switch (ch) 14 { 15 case '(': //对(做处理 16 s.push(p); 17 k = 1; 18 break; 19 20 case ')': //对)做处理 21 s.pop(); 22 break; 23 24 case ',': //对,做处理 25 k = 2; 26 break; 27 28 default: 29 p = new BinTreeNode<T>(ch); //构造一个结点 30 if (BT == NULL) //如果头节点是空 31 { 32 BT = p; 33 } 34 else if (k == 1) //链入*t的左孩子 35 { 36 t = s.top(); 37 t->leftChild = p; 38 } 39 else //链入*t的右孩子 40 { 41 t = s.top(); 42 t->rightChild = p; 43 } 44 } 45 cin >> ch; 46 } 47 }
2.使用已知的二叉树的前序遍历创建
必须对应二又树结点前序遍历的顺序，并约定以输入序列中不可能出现的值作为空结点的值以结束递归，此值通过构造函数存放在RefValue中。例如用“#”或表示字符序列或正整数序列空结点。
前序遍历所得到的前序序列为ABC##DE#G##F###。
算法的基本思想是：
每读入一个值，就为它建立结点。该结点作为根结点，其地址通过函数的引用型参数subTree直接链接到作为实际参数的指针中。然后，分别对根的左、右子树递归地建立子树，直到读入“#”建立空子树递归结束。
1 //创建二叉树(利用已知的二叉树的前序遍历创建)用#表示空结点 2 void CreateBinTree_PreOrder(BinTreeNode<T>* &subTree) 3 { 4 T item; 5 if (cin >> item) 6 { 7 if (item != RefValue) 8 { 9 subTree = new BinTreeNode<T>(item); //构造结点 10 if (subTree == NULL) 11 { 12 cout << "空间分配错误！" << endl; 13 exit(1); 14 } 15 CreateBinTree_PreOrder(subTree->leftChild); //递归创建左子树 16 CreateBinTree_PreOrder(subTree->rightChild); //递归创建右子树 17 } 18 else 19 { 20 subTree == NULL; 21 } 22 } 23 }
3.根据已知的前序遍历和中序遍历创建二叉树
根据前序遍历，先找到这棵树的根节点，也就是数组受中第一个结点的位置，创建根节点。
然后在中序遍历中找到根的值所在的下标，切出左右子树的前序和中序
注意：如果前序遍历的数组长度为0，说明是一棵空树。
举例：
首先可以确定A是这棵树的根节点，然后根据中序遍历切出A的左右子树，得到BCD属于A的左子树，E属于A的右子树，如下图：
接着以B为根节点，在中序遍历中再次切出B的左右子树，得到CD为B的左子树，右子树为空。
再以C为根节点，结合中序遍历，得到D为C的右子树，左子树为空。
创建好的二叉树如下图所示：
1 //
