首页 > 代码库 > 数据结构——二叉树（Binary Trees）
数据结构——二叉树（Binary Trees）
非线性数据结构
树的密度=结点数/高度
二叉树类
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 // constructor11 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 stree17 {18 public:19 stree(); // constructor. initialize root to NULL and size to 020 ~stree(); // destructor21 bool insert(const int item);22 void Output(); 23 24 private:25 stnode *root; // pointer to tree root26 int treeSize; // number of elements in the tree27 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 pointers35 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 }
数据结构——二叉树（Binary Trees）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。