首页 > 代码库 > 数据结构快速回顾——二叉树
数据结构快速回顾——二叉树
二叉树（Binary Tree）是个有限元素的集合，该集合或者为空、或者由一个称为根(root)的元素及两个不相交的、被分别称为左子树和右子树的二叉树组成。当集合为空时，称该二叉树为空二叉树。在二叉树中，一个元素也称作一个结点。
基本概念：
（1）结点的度。结点所拥有的子树的个数称为该结点的度。
（2）叶结点。度为0的结点称为叶结点，或者称为终端结点。
（3）分枝结点。度不为0的结点称为分支结点，或者称为非终端结点。一棵树的结点除叶结点外，其余的都是分支结点。
（4）左孩子、右孩子、双亲。树中一个结点的子树的根结点称为这个结点的孩子。这个结点称为它孩子结点的双亲。具有同一个双亲的孩子结点互称为兄弟。
（5）路径、路径长度。如果一棵树的一串结点n1,n2,…,nk有如下关系：结点ni是ni+1的父结点（1≤i<k）,就把n1,n2,…,nk称为一条由n1至nk的路径。这条路径的长度是k-1。
（6）祖先、子孙。在树中，如果有一条路径从结点M到结点N，那么M就称为N的祖先，而N称为M的子孙。
（7）结点的层数。规定树的根结点的层数为1，其余结点的层数等于它的双亲结点的层数加1。
（8）树的深度。树中所有结点的最大层数称为树的深度。
（9）树的度。树中各结点度的最大值称为该树的度。
（10）满二叉树，在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子结点都在同一层上，这样的一棵二叉树称作满二叉树。
下面给出二叉树的节点结构：
1 //定义树节点结构2 3 typedef struct BinaryTreeNode4 {5 int m_nValue;6 BinaryTreeNode *m_pLeft;7 BinaryTreeNode *m_pRight;8 9 }node;
二叉树的基本操作：节点个数计算、树深度计算、前序遍历、中序遍历、后序遍历 以及广度搜索
其中前序遍历给出了使用堆栈代替递归的实现方法。
1 //求二叉树中的节点个数 2 3 int getNodeNum(node *pRoot) 4 { 5 if(pRoot == NULL) 6 return 0; 7 return getNodeNum(pRoot->m_pLeft)+getNodeNum(pRoot->m_pRight)+1; 8 } 9 10 11 //求二叉树深度 12 int getDepth(node *pRoot) 13 { 14 if(pRoot == NULL) 15 return 0; 16 int depthLeft = getDepth(pRoot->m_pLeft); 17 int depthRight = getDepth(pRoot->m_pRight); 18 19 return depthLeft>depthRight ? (depthLeft+1) :(depthRight+1); 20 21 } 22 23 //前序遍历 中序遍历 后序遍历 24 /*前序遍历递归解法： 25 （1）如果二叉树为空，空操作 26 （2）如果二叉树不为空，访问根节点，前序遍历左子树，前序遍历右子树 27 参考代码如下： 28 */ 29 void PreOrderTraverse(node *pRoot) 30 { 31 if(pRoot == NULL) 32 return; 33 Visit(pRoot); 34 PreOrderTraverse(pRoot->m_pLeft); 35 PreOrderTraverse(pRoot->m_pRight); 36 } 37 //前序遍历的堆栈实现 38 void PreOrderTraverse(node *pRoot) 39 { 40 InitStack(S); 41 while(!StackEmpty(S)) 42 { 43 node *p = new node(); 44 //遍历到最左边的叶子节点 45 while(GetTop(S,p)&& p) 46 Push(p->m_pLeft); 47 Pop(S,p);//弹出叶子节点 48 if(!StackEmpty(S)) 49 { 50 Pop(S,p); 51 if(!Visit(p->data)) 52 return 0;//访问数据出现错误 53 Push(S,p->m_pRight); 54 } 55 } 56 } 57 58 //中序遍历 59 60 void InOrderTraverse(node *pRoot) 61 { 62 if(pRoot == NULL) 63 return; 64 InOrderTraverse(pRoot->m_pLeft); 65 Visit(pRoot); 66 InOrderTraverse(pRoot->m_pRight); 67 } 68 69 //后序遍历 70 void PostOrderTraverse(node *pRoot) 71 { 72 if(pRoot == NULL) 73 return; 74 75 PostOrderTraverse(pRoot->m_pLeft); 76 PostOrderTraverse(pRoot->m_pRight); 77 Visit(pRoot); 78 } 79 80 //广度优先搜索 81 /* 82 队列初始化，将根节点压入队列。当队列不为空，进行如下操作：弹出一个节点，访问，若左子节点或右子节点不为空，将其压入队列。 83 */ 84 void LevelTraverse(node *pRoot) 85 { 86 if(pRoot == NULL) 87 return; 88 89 quene<node *> q; 90 q.push(pRoot); 91 92 while(!q.empty()) 93 { 94 node *pNode = q.front(); 95 q.pop(); 96 97 Visit(pNode); 98 if(pNode->m_pLeft != NULL) 99 q.push(pNode->m_pRight);100 if(pNode->m_pRight != NULL)101 q.push(pNode->m_pRight);102 }103 return;104 }
参考：http://www.cztvu.ah163.net/czcai/soft/kj/sjjg/jj/ch6.htm
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。