二叉树
二叉树的定义
二叉树是另一种树形结构，其特点是每个结点至多只有两棵子树，（即二叉树中不存在度大于2的结点。且，二叉树左右有序，不能颠倒。
二叉树也是递归的形式定义：
1）为空二叉树，n=0；
2）由一个根结点和两个不相交的左子树和右子树组成。左右子树分别又是两棵二叉树。
特殊的二叉树：
1）满二叉树：一棵高度为h,并且含有2^h-1个结点的二叉树称为满二叉树，即树中的每一层都含有最多的结点。除叶子结点外每个结点度数都为2。
2）完全二叉树：一个高度为h，有n个结点的二叉树，当且仅当其每一个结点都与高度为h的满二叉书中编号为1~n的结点一一对应。（即比满二叉树少几个叶子结点）
3）二叉排序树：左子树上结点关键字小于结点，右子树上结点关键字大于结点，且子树也为二叉排序树。
4）平衡二叉树：树上任一结点的左右子树深度不超过1。
二叉树的存储结构：
顺序存储结构：
1）数组方式存储（自上向下从左往右依次存储，也就是1，2，4，8……的顺序）
2）0位不存元素，从pq[1]开始
3）元素0表示空结点
4）高度为log2^N+1（N为数组长N从1开始）
链表方式存储：
结点至少包含三个域：
数据域data、左指针域lchild、右指针域rchild；
数据域分为：key键和data值,key是每个结点的门牌号，唯一存在；
以及为了方便添加一个int域，存储每个结点的子结点数。
二叉树的遍历
先序遍历：
二叉树为空结束，否则：
1）访问根结点
2）先序遍历左子树
3）先序遍历右子树
中序遍历：
二叉树为空结束，否则：
1）中序遍历左子树
2）访问根结点
3）中序遍历右子树
后序遍历：
二叉树为空结束，否则：
1）后序遍历左子树
2）后序遍历右子树
3）访问根结点
遍历的顺序是指访问根结点的先后顺序。
二叉树API： class BTree{ BTree()构建二叉树void TLRtrave()先序遍历void LTRtrave()中序遍历void LRTtrave()后序遍历int defth()二叉树深度int leafnum()叶子数int size()结点数void clear()清空void put(int key,string item)插入元素void delete_1(int key)删除元素};
代码：
顺序存储结构：
class BTree { public: BTree(){ T.push_back("null"); }//元素0表示该结点为空 void put(int n,string item)//(插入元素，数组位序） {//从上往下从左往右按层存储(即每层按顺序存储进去） if (n > N + 1 || n<1 || T[n / 2] == "0")exit(0); if (n == N + 1){ T.push_back(item); N++; } else T[n] = item; } void TLRtrave(){ if (N>0) TLRtrave(1); cout << endl; }//先序遍历 void LTRtrave(){ if (N>0) LTRtrave(1); cout << endl; }//中序遍历 void LRTtrave(){ if (N>0) LRTtrave(1); cout << endl; }//后序遍历 int defth();//二叉树深度 int leafnum(){ return N>0 && T[1] != "0" ? leafnum(1) : 0; }//叶子数 int size();//结点数 void clear();//清空树 void delete_1(int t);//删除第t个结点 private: void TLRtrave(int t); void LTRtrave(int t); void LRTtrave(int t); int leafnum(int t); void visit(int t){ cout << T[t] << " "; }//工具函数，打印数据 vector<string> T;//动态数组（除去0位） int N = 0;//动态数组长 }; void BTree::TLRtrave(int t)//先序遍历（数组首元素位序） { visit(t); if (t * 2 <= N)TLRtrave(t * 2); if (t * 2 + 1 <= N)TLRtrave(t * 2 + 1); } void BTree::LTRtrave(int t)//中序遍历（数组首元素） { if (t * 2 <= N)LTRtrave(t * 2); visit(t); if (t * 2 + 1 <= N)LTRtrave(t * 2 + 1); } void BTree::LRTtrave(int t)//后序遍历（数组首元素） { if (t * 2 <= N)LRTtrave(t * 2); if (t * 2 + 1 <= N)LRTtrave(t * 2 + 1); visit(t); } int BTree::defth() { int t = N; while (true) { if (T[t] != "0")break; t--; } return log2(t) + 1; } int BTree::leafnum(int t) { if (2 * t > N)return 1; else if (T[2 * t] == "0" && (2 * t + 1 > N || T[2 * t + 1] == "0"))return 1; else { int l = 0, r = 0; if (2 * t <= N&&T[2 * t] != "0")l = leafnum(2 * t); if (2 * t + 1 <= N&&T[2 * t + 1] != "0")r = leafnum(2 * t + 1); return l + r; } } int BTree::size() { int t = 0; for (int i = 1; i <= N; i++) if (T[i] != "0")t++; return t; } void BTree::clear() { for (int i = 1; i <= N; i++) T.pop_back(); N = 0; } void BTree::delete_1(int t) { if (2 * t <= N)delete_1(2 * t); if (2 * t + 1 <= N)delete_1(2 * t + 1); T[t] = "0"; } 顺序存储比较简单，需要注意的有以下几点：
1.put函数是按层存入的，因为使用的是动态数组所以没法跳过前面的项直接存储后面的元素，所以要注意，测试时将空项值都设为0.
2.是在leafnum函数中，边界较多，需要考虑：
1）叶子没有左右孩子，
2）或者孩子值都为0，
3）亦或者左孩子为0，右孩子为空
三种情况下都为叶子结点
3.是defth函数，计算深度时，应该排除末尾为值0的元素。
链式存储结构：
class Node { friend class BTree; int key;//键（不重复） string data;//值域 Node* lchild;//左指针域 Node* rchild;//右指针域 int N;//以该结点为根的子结点总数 public: Node(int key, string item, int N) :key(key), data(item), N(N){} }; class BTree { public: void put(int key, string item) { root = put(root, key, item); } void TLRtrave(){ TLRtrave(root); }//先序遍历 void LTRtrave(){ LTRtrave(root); }//中序遍历 void LRTtrave(){ LRTtrave(root); }//后序遍历 int defth(){ return defth(root); }//二叉树深度 int leafnum(){ return leafnum(root); }//叶子数 int size(){ return size(root); }//结点数 void clear(){ clear(root); root = NULL; }//清空 void delete_1(int key)//删除键为key的元素 { root = delete_1(root, key); } private: Node* root = NULL;//根结点 //工具函数 Node* put(Node* x, int key, string item); void visit(Node* x)//打印元素 { cout << x->key << ":" << x->data << endl; } void TLRtrave(Node* root); void LTRtrave(Node* root); void LRTtrave(Node* root); int defth(Node* root); int leafnum(Node* x); int size(Node* x){ return !x ? 0 : x->N; } void clear(Node* x); Node* delete_1(Node* x, int key); }; Node* BTree::put(Node* x, int key, string item)//插入 { //如果key存在于以X为根结点的子树中则更新它的data //否则插入他的子树中，左子树key小于他，右子树key大于他 if (!x)return new Node(key, item, 1); if (key<x->key) x->lchild = put(x->lchild, key, item); else if (key>x->key)x->rchild = put(x->rchild, key, item); else x->data = item; x->N = size(x->lchild) + size(x->rchild) + 1; return x; } void BTree::TLRtrave(Node* x) { if (x) { visit(x); TLRtrave(x->lchild); TLRtrave(x->rchild); } } void BTree::LTRtrave(Node* x) { if (x) { LTRtrave(x->lchild); visit(x); LTRtrave(x->rchild); } } void BTree::LRTtrave(Node* x) { if (x) { LRTtrave(x->lchild); LRTtrave(x->rchild); visit(x); } } int BTree::defth(Node* x) { int l, r; if (x) { l = defth(x->lchild); r = defth(x->rchild); return l > r ? l + 1 : r + 1; } else return 0; } int BTree::leafnum(Node* x) { if (!x->lchild&&!x->rchild)return 1; else { int l = 0, r = 0; if(x->lchild)l = leafnum(x->lchild); if(x->rchild)r = leafnum(x->rchild); return l + r; } } void BTree::clear(Node* x) { if (x) { clear(x->lchild); clear(x->rchild); delete x; } } Node* BTree::delete_1(Node* x, int key) { if (!x)return NULL; if (key < x->key)x->lchild = delete_1(x->lchild, key); else if (key > x->key)x->rchild = delete_1(x->rchild, key); else { visit(x); clear(x); x = NULL; } return x; } 链式结构的基本点都是在递归的运用上，几乎每一个操作函数都用到了递归，我想这就应该是二叉树如此便洁的原因吧，通过堆栈的利用，将链表插入的灵活性和有序数组查找的高效性结合到一起。
在写代码过程中遇见的问题有：
1.键值的使用，准确来说链式结构代码写的是一棵有序树，通过键值将树的左右子树分为两半，这样做不仅为插入、删除带来了便利，更为后面写查找树打下基础。
2.依然是leafnum的边界问题，在调用递归前，必须先确定左右孩子是否存在。
3.是根结点root，构造树之前我们必须将他设为NULL，才能与插入函数向对应。同样的clear函数结束后，我们还是需要root=NULL，否则插入函数将会跳过构造结点，直接进行key的比较。
4.是delete_1函数，删除结点的同时，删除了结点上的左右子树，但是我想应该还会有一个删除函数支持只删除单个结点，不过知识点还涉及到了后面查找树的一些功能，所以就留到下一节在写。
测试用例：
int main() { BTree p; int m, n; string item; cout << "***********************************" << endl; cout << "0.打开菜单. 1.插入新元素." << endl; cout << "2.先序遍历. 3.中序遍历." << endl; cout << "4.后序遍历. 5.二叉树的深度." << endl; cout << "6.二叉树的叶子数. 7.求结点数." << endl; cout << "8.清空二叉树. 9.删除元素." << endl; cout << "***********************************\n" << endl; while (cin >> m) { switch (m) { case 0: cout << "***********************************" << endl; cout << "0.打开菜单. 1.插入新元素." << endl; cout << "2.先序遍历. 3.中序遍历." << endl; cout << "4.后序遍历. 5.二叉树的深度." << endl; cout << "6.二叉树的叶子数. 7.求结点数." << endl; cout << "8.清空二叉树. 9.删除元素." << endl; cout << "***********************************\n" << endl; break; case 1: cout << "输入插入元素键和值：" << endl; cin >> n >> item; p.put(n, item); break; case 2: cout << "先序遍历：" << endl; p.TLRtrave(); break; case 3: cout << "中序遍历：" << endl; p.LTRtrave(); break; case 4: cout << "后序遍历:" << endl; p.LRTtrave(); break; case 5: cout << "二叉树深度:" << p.defth() << endl; break; case 6: cout << "二叉树叶子数:" << p.leafnum() << endl; break; case 7: cout << "结点数:" << p.size() << endl; break; case 8: cout << "清空." << endl; p.clear(); break; case 9: cout << "输入删除元素键：" << endl; cin >> n; p.delete_1(n); break; } } }
