1、基本概念

  二叉树，顾名思义，就是子节点最多只有两个的树。由于最多只有两个，可以区分左右，我们称子节点为左子女和右子女，次序不可颠倒。根据二叉树的结构，我们可以得到以下特性： 1. 第i层的节点个数最多为2^(i-1)(i>=1)个； 2. 深度为h的二叉树最多有2^h -1(h>=1)个节点，最少为h个； 3. 若叶节点的个数为n1，度数为2的节点个数为n2，则n1=n2+1；

2、特殊结构

  当二叉树满足一些特殊的条件时，会形成特殊的结构，可以很好的作为其他数据结构的底层结构，目前有如下几种特殊情况： 1. 完全二叉树。若二叉树的高度为h，则除了第h层的其他层都达到该层节点的最大个数，同时第h层的节点是从左至右连续排列的。由于节点顺序是紧密排列的，可以使用序列容器进行存储，主要应用于二叉堆。以下是完全二叉树的特性，设定根节点的索引位置为1： * 对于索引位置为i的节点，其到根节点的节点总数也为i； * 对于索引位置为i的节点，其左子女的索引位置为2*i，右子女的索引位置为2*i+1； * 对于索引位置为i（i>1）的节点，其父节点的索引位置为int(i/2)； * 对于索引位置为i的节点，若节点总数为n且i>int(n/2),则该节点为叶子节点； * 对于索引位置为i的节点，若节点总数为n且int((n-1)/2)>i,则该节点必有两个子节点； * 对于任意节点，若其右子树的深度为d，则左子树的深度为d或d+1； * 若子节点总数为n，则叶子节点个数为l= math.ceil（n/2）。 2. 满二叉树。二叉树的每一层的节点个数都达到最大个数，因而满二叉树一定是完全二叉树，但完全二叉树不一定是满二叉树。 3. 平衡二叉树。对于树中的任意节点，其左右子树的高度相差不超过1。平衡二叉树要保证高度平衡，避免出现链表式的树。

3、查找节点

  在树中查找节点，就是采用递归方法，从根节点开始，一次判读根节点、左子树、右子树，从而找的对应的节点，一下是实现代码：

bool BTree::contains(int key, BTreeNode* &node) { if (node == NULL) { return false; } if (key == node->data) { return true; } return contains(key,node->leftChild) || contains(key,node->rightChild); }

4、插入节点

  二叉树在插入时是没有固定规则，可自行定义，下面我使用构造满二叉树的方式进行插入，这里通过queue找到节点的插入位置，代码如下：

void BTree::insert(int key, BTreeNode* &node) { if (node == NULL) { node = new BTreeNode(key); } else { //按照插入顺序放置 queue<BTreeNode*> q; q.push(node); while(!q.empty()) { BTreeNode* temp = q.front(); q.pop(); if (temp->leftChild == NULL) { temp->leftChild = new BTreeNode(key); return; } if (temp->rightChild == NULL) { temp->rightChild = new BTreeNode(key); return; } q.push(temp->leftChild); q.push(temp->rightChild); } } }

5、删除节点

  二叉树删除节点也是没有规则的，但不管使用什么规则，都要考虑下面三种情况： 1. 删除节点没有子节点。这种情况最简单，将该节点的父节点指向该节点的指针置为空，然后删除该节点即可； 2. 删除节点有一个子节点。此时将该节点的父节点指向该节点的指针置为指向改节点的子节点，然后删除该节点； 3. 删除节点有两个子节点。这里采用的策略是先查找到该节点的右子树中的最后一个节点，然后将查找到的节点的键值与该节点的键值进行交换，最后使用递归方法删除查找到的节点。   下面是二叉树删除的实现代码：

void BTree::remove(int key, BTreeNode* &node) { if (node == NULL) { return; } if (key == node->data) { if (node->leftChild != NULL && node->rightChild != NULL) { //查找子树的最后一个节点 queue<BTreeNode*> q; q.push(node->leftChild); q.push(node->rightChild); while(true) { BTreeNode* curNode = q.front(); q.pop(); if (curNode->leftChild != NULL) { q.push(curNode->leftChild); } if (curNode->rightChild != NULL) { q.push(curNode->rightChild); } if (q.empty()) { node->data = curNode->data; curNode->data = key; remove(key,node); return; } } } else { BTreeNode* temp = node; node = (node->leftChild != NULL)?node->leftChild:node->rightChild; delete temp; return; } } remove(key,node->leftChild); remove(key,node->rightChild); }

6、清理操作

  若要清理整棵树的节点，可以使用递归的方法清理节点的左右子树，然后释放节点自己，下面是实现代码：

void BTree::clear(BTreeNode* &node) { if (node == NULL) { return; } clear(node->leftChild); clear(node->rightChild); delete node; node = NULL; }

7、综合结果

  下面，我们对算法进行测试，结果如下：

BTree* tree = new BTree(); for (int i = 0; i < 10; ++i) { tree->insert(i); } cout<<"contains 5:"<<tree->contains(5)<<endl; //contains 5:1 cout<<"contains 10:"<<tree->contains(10)<<endl; //contains 10:0 BTreeNode* minNode = tree->findMin(); if (minNode != NULL) { cout<<"findMin:"<<minNode->data<<endl; //findMin:0 } BTreeNode* maxNode = tree->findMax(); if (minNode != NULL) { cout<<"findMax:"<<maxNode->data<<endl; //findMax:9 } tree->breadthFirstTravel(); //bft:0 1 2 3 4 5 6 7 8 9 tree->depthFirstTravel_DLR(); //depthFirstTravel_DLR:0 1 3 7 8 4 9 2 5 6 tree->depthFirstTravel_LDR(); //depthFirstTravel_LDR:7 3 8 1 9 4 0 5 2 6 tree->depthFirstTravel_LRD(); //depthFirstTravel_LRD:7 8 3 9 4 1 5 6 2 0 tree->remove(1); tree->breadthFirstTravel(); //bft:0 9 2 3 4 5 6 7 8 tree->depthFirstTravel_DLR(); //depthFirstTravel_DLR:0 9 3 7 8 4 2 5 6 tree->depthFirstTravel_LDR(); //depthFirstTravel_LDR:7 3 8 9 4 0 5 2 6 tree->depthFirstTravel_LRD(); //depthFirstTravel_LRD:7 8 3 4 9 5 6 2 0 tree->clear(); tree->breadthFirstTravel(); //bft:

8、效率分析

  二叉树的查找操作需要遍历整棵树，其算法复杂度为O（n）；插入操作根据插入策略的不同而不同的，平均查找到插入位置的算法复杂度为O（logn）；删除操作由于要先查找到节点，其算法复杂度以查找操作一致。