本文共 3730 字，大约阅读时间需要 12 分钟。
二叉树的基本实现
创建二叉树类。二叉树的存储结构使用链表。提供操作:前序遍历、中序遍历、后序遍历、层次遍历、计算二叉树结点数目、计算二叉树高度。
格式
输入格式
第一行为一个数字n (10<=n<=100000)，表示有这棵树有n个节点，编号为1~n。
之后n行每行两个数字，第 i 行的两个数字a、b表示编号为 i 的节点的左孩子节点为 a，右孩子节点为 b，-1表示该位置没有节点。
保证数据有效，根节点为1。
输出格式
第一行，n个数字，表示该树的层次遍历。
第二行，n个数字，第i个数字表示以 i 节点为根的子树的节点数目。
第三行，n个数字，第i个数字表示以 i 节点为根的子树的高度。
样例1
输入
5
2 3
4 5
-1 -1
-1 -1
-1 -1
输出
1 2 3 4 5
5 3 1 1 1
3 2 1 1 1
样例2
输入
5
3 2
-1 -1
4 5
-1 -1
-1 -1
输出
1 3 2 4 5
5 1 3 1 1
3 1 2 1 1
样例3
输入
10
2 -1
4 3
6 -1
5 8
9 7
-1 -1
-1 -1
-1 -1
10 -1
-1 -1
输出
1 2 4 3 5 8 6 9 7 10
10 9 2 6 4 1 1 1 2 1
6 5 2 4 3 1 1 1 2 1
Hint
请仔细读题，注意建树过程。
#include using namespace std;int counts[999999];int deep[999999];template struct binaryTreeNode{ T element;int leaves; binaryTreeNode *leftChild,*rightChild; //左子树和右子树 };template void erase(binaryTreeNode *& proot){ if(proot!=NULL) { erase(proot->leftChild); erase(proot->rightChild); delete proot; proot=NULL; }}template class binaryTree{ public: binaryTree(){ root=NULL;treeSize=0;}//构造函数 ~binaryTree(){ erase(root);}//析构函数 bool empty() const{ return treeSize==0;} int size() const{ return treeSize;} binaryTreeNode ** rootElement(){ return &root;} void makeTree(T* elem,int n); void preOrder(binaryTreeNode * t); void inOrder(binaryTreeNode * t); void postOrder(binaryTreeNode * t); int treeCount(binaryTreeNode * t); void levelOrder(); int height(binaryTreeNode *t); private: binaryTreeNode *root; int treeSize; static void (*visit)(binaryTreeNode *); }; template void (*binaryTree ::visit)(binaryTreeNode *);template int binaryTree ::treeCount(binaryTreeNode * t){ int n=0; if(t!=NULL) { n=treeCount(t->leftChild)+treeCount(t->rightChild)+1; } return n;}template void binaryTree ::makeTree(T* elem,int n){ binaryTreeNode ** (array[n/2])={ }; array[0]=&root; root=new binaryTreeNode ; root->element=elem[0]; root->leftChild=NULL; root->rightChild=NULL; root->leaves=0; for(int i=1;i * p=new binaryTreeNode ; if(elem[i]!=-1) { p->element=elem[i]; p->leftChild=NULL; p->rightChild=NULL; p->leaves=0; } else p=NULL; if(i%2!=0) { (*array[index])->leftChild=p; if(p!=NULL) array[(p->element)-1]=&((*array[index])->leftChild); } else { (*array[index])->rightChild=p; if(p!=NULL) array[(p->element)-1]=&((*array[index])->rightChild); } } treeSize=n;}template void binaryTree ::preOrder(binaryTreeNode *t){ // Preorder traversal. if (t != NULL) { counts[(t->element)-1]=treeCount(t); deep[(t->element)-1]=height(t); //binaryTree ::visit(t); preOrder(t->leftChild); preOrder(t->rightChild); }}template void binaryTree ::inOrder(binaryTreeNode *t){ // Inorder traversal. if (t != NULL) { inOrder(t->leftChild); binaryTree ::visit(t); inOrder(t->rightChild); }}template void binaryTree ::postOrder(binaryTreeNode *t){ // Postorder traversal. if (t != NULL) { postOrder(t->leftChild); postOrder(t->rightChild); binaryTree ::visit(t); }}template void binaryTree ::levelOrder(){ // Level-order traversal. binaryTreeNode * q[treeSize]; q[0]=root; cout< element<<" "; for(int i=1;i leaves==1) { index++; } if(i%2!=0) { q[i]=q[index]->leftChild; if(q[i]!=NULL) cout< element<<" "; } else { q[i]=q[index]->rightChild; q[index]->leaves=1; if(q[i]!=NULL) cout< element<<" "; } }}template int binaryTree ::height(binaryTreeNode *t){ // Return height of tree rooted at *t. if (t == NULL) return 0; // empty tree int hl = height(t->leftChild); // height of left int hr = height(t->rightChild); // height of right if (hl > hr) return ++hl; else return ++hr;}int main(){ int n; cin>>n; int *tr=new int[2*n+1]; binaryTree tre; tr[0]=1; for(int i=1;i<=(2*n);i++) { cin>>tr[i]; } tre.makeTree(tr,2*n+1); tre.levelOrder(); cout<
* node=*tre.rootElement(); tre.preOrder(node); for(int i=0;i