非线性数据结构
树的密度=结点数/高度
二叉树类
1 #pragma once 2 3 class stnode 4 { 5 public: 6 int nodeValue; // node data 7 8 stnode *left, *right, *parent; // child pointers and pointer to the node‘s parent 9 10 // constructor 11 stnode (const int item, stnode *lptr = NULL, stnode*rptr = NULL, stnode *pptr = NULL): 12 nodeValue(item), left(lptr), right(rptr), parent(pptr) 13 {} 14 }; 15 16 class stree 17 { 18 public: 19 stree(); // constructor. initialize root to NULL and size to 0 20 ~stree(); // destructor 21 bool insert(const int item); 22 void Output(); 23 24 private: 25 stnode *root; // pointer to tree root 26 int treeSize; // number of elements in the tree 27 stnode *creatSTNode(const int item, stnode *lptr, stnode *rptr, stnode*pptr); 28 }; 29 30 stnode * stree::creatSTNode (const int item, stnode *lptr, stnode *rptr, stnode *pptr) 31 { 32 stnode*newNode; 33 34 // initialize the data and all pointers 35 newNode = new stnode (item, lptr, rptr, pptr); 36 37 return newNode; 38 }
完全二叉树（complete tree）：
所有非叶子节点有两个子结点或一个左子结点。按从左到右顺序建树。
包含n个元素的完全二叉树 h=(int)(log2(n))
遍历：
1、层次遍历
按层从左到右遍历。
1 //层序遍历二叉树 2 void stree::LevelByLevel(stnode *root) 3 { 4 std::queue<stnode*> q;//建队 5 q.push(root);//根节点入队 6 stnode *cur; 7 while(!q.empty()) 8 { 9 cur=q.front(); //获得队列的首元素 10 q.pop(); //首元素出队 11 temp.Format("%d ",cur->nodeValue); //输出结点的值 12 str+=temp; 13 14 if(cur->left!=NULL) //若结点的左子树不空 15 { 16 q.push(cur->left); 17 } 18 if(cur->right!=NULL)//若结点的右子树不空 19 { 20 q.push(cur->right); 21 } 22 } 23 }
2、中序遍历（LDR）
先访问左结点数据，直到左节点为空则访问中间（父结点）数据，再访问右子结点数据。
盗一张百度的图：
3、前序遍历（DLR）
先访问父结点数据，再访问左子结点，最后右子结点。到达即访问，根结点在遍历的第一个。
上图的前序遍历结果为：ABDGJEHCFI
4、后序遍历（LRD）
先访问左子结点数据，再访问右子结点，最后父结点。根结点在遍历的最后一个。
上图的前序遍历结果为：JGDHEBIFCA
树的递归
1、递归遍历叶子结点
void CountLeaf(tnode<T> *t,int &count) { if(t!=NULL) { if(t->left==NULL&&t->right==NULL) count++; CountLeaf(t->left,count); CountLeaf(t->right,count); } }
2、树的高度
1 int depth(tnode<T> *t) 2 { 3 int depthleft,depthright,depthval; 4 if(t==NULL) 5 depthval=-1; 6 else 7 { 8 depthleft=depth(t->left); 9 depthright=depth(t->right); 10 depthval=1+(depthleft>depthright? depthleft:depthright); 11 } 12 return depthval; 13 }
3、删除整树
1 void deleteTree(tnode<T> *t) 2 { 3 if(t!=NULL) 4 { 5 deleteTree(t->left); 6 deleteTree(t->right); 7 delete t; 8 } 9 }
原文：http://www.cnblogs.com/verlen11/p/4198908.html
