树论_二叉树的定义和性质-开发者社区

二叉树可以处理每个阶段都是两种结果的情形，如：大和小，0和1，真和假等

二叉树的定义

二叉树特点：

每个节点最多有两颗子树
是有序树，即左子树和右子树有次序

特殊二叉树

斜二叉树

特殊的表现为线性表

满二叉树

所有分支节点都有左子树和右子树，所有叶子节点在同一层

完全二叉树

适合用顺序结构即数组表示
叶子节点只会出现在最下面两层
若有n个节点，其深度为[log2 n]+1，[]表示取整
若从1开始编号，对于节点i，若左子树存在，左儿子序号（下标）为i*2，若右子树存在，右儿子序号（下标）为i*2+1，若节点存在双亲，则双亲为i/2（需要取整）
若从0开始编号，则分别为i*2+1，i*2+2，(i-1)/2
从根节点一直沿着左儿子遍历并计数可以得到树的高度

计算完全二叉树的节点

计算左子树的高度lheight，计算右子树满树区域的高度rheight
若lheight和rheight相等，说明这是一颗满二叉树，直接用公式n=2^h -1
若lheight和rheight不相等，递归计算左子树和右子树的节点个数

计算height的时间复杂度O(logN)，由于完全二叉树的左子树和右子树至少有一颗是满二叉树，所以只会有一颗子树继续递归，另一颗子树满足lheight==rheight的条件就退出递归，同样的，不是满二叉树的那颗子树也是一颗完全二叉树，所以需要递归的时间复杂度为O(logN)，每次递归加上计算height的时间，总的算法时间复杂度就是O(logN* logN)

int getNodeNum(TreeNode* root){ int lheight=0,rheight=0; TreeNode *p=root->left; TreeNode *q=root->right; while(p){ lheight++; p=p->left; //沿左儿子走 } while(q){ rheight++; q=p->right; //沿右儿子走 } if(lheight==rheight){ //root是满二叉树 return (1<<(lheight+1))-1; } else return getNodeNum(root->left)+getNodeNum(root->right)+1; }

二叉树的普适性质

二叉树第i层最多有2^(i-1)个节点
深度为k的二叉树最多有2^k -1个节点（证明：等比数列求和）
二叉树的边数等于节点数-1
n0：度为0的节点，n1：度为1的节点，n2：度为2的节点，则n0=n2+1（证明：n0+n1+n2-1=0*n0+1*n1+2*n2）

二叉树的顺序存储结构

从上到下，从左到右将二叉树的节点放在数组中，适合完全二叉树，节点与其双亲，儿子的下标对应关系与完全二叉树相同：[[2 二叉树的定义和性质#完全二叉树]]

二叉树的链式存储结构

用二叉链表储存，每个节点含一个data域，两个指针域，分别是左儿子left，右儿子right，根据需要可增加双亲域parent

typdef int DataType typedef struct treenode_{ DataType data; struct treenode_ *left,*right; }TreeNode;

左儿子或右儿子不存在就设置为NULL

二叉树的遍历

三种遍历经过的路线一样，只是每个节点的访问时机不同
一般来说默认先遍历左子树再遍历右子树，但根据实际情况不同可以先遍历右子树再遍历左子树

先序遍历（递归

先访问根节点，再递归遍历左子树，再递归遍历右子树

递归算法：

void PreOrderTraversal(TreeNode* t){ if(t){ cout<<t->data; PreOrderTraversal(t->left); PreOrderTraversal(t->right); } }

中序遍历（递归

先递归遍历左子树，再访问根节点，再递归遍历右子树

递归算法：

void InOrderTraversal(TreeNode* t){ if(t){ PreOrderTraversal(t->left); cout<<t->data; PreOrderTraversal(t->right); } }

后序遍历（递归

先递归遍历左子树，再递归遍历右子树，再访问根节点

递归算法：

void PostOrderTraversal(TreeNode* t){ if(t){ PreOrderTraversal(t->left); PreOrderTraversal(t->right); cout<<t->data; } }

中序遍历（非递归

基本思想：利用指示指针p和stack模拟中序遍历，基于指示指针或stack不为空的大循环，先让指示指针p沿着左链走到底，边走边将指示过的节点push，然后若stack不为空就pop并且访问，再让p指向该pop出来的节点的右儿子

void InOrderTraversal(TreeNode* t){ TreeNode* p=t; //指示指针 stack<TreeNode*> s; //堆栈 while(p||!s.empty()){ //大循环 while(p){ //让p沿着左链走到底，并push s.push(p); p=p->left; } if(!s.empty()){ //stack不为空就pop并访问 p=s.top(); s.pop(); cout<<p->data; //pop并访问 p=p->right; //访问右儿子 } } }

迁移：中序遍历是出栈时访问，根据先序遍历访问节点的时机不同，先序遍历非递归算法是在入栈时访问

先序遍历（非递归

void InOrderTraversal(TreeNode* t){ TreeNode* p=t; //指示指针 stack<TreeNode*> s; //创建堆栈 while(p||!s.empty()){ //大循环 while(p){ //让p沿着左链走到底，并push s.push(p); cout<<p->data; //push并访问 p=p->left; } if(!s.empty()){ //stack不为空就pop并访问 p=s.top(); s.pop(); p=p->right; //访问右儿子 } } }

层序遍历

前三种都是Depth First Search，层序遍历是Breadth First Search

基本思想：利用queue模拟层序遍历，每次迭代，先pop，再将pop出来的节点的所有子节点push，当队列为空停止迭代，进入迭代前先将根节点push

void LevelOrderTraversal(TreeNode* t){ if(!t)return; //空树直接返回 queue<TreeNode*> q; //创建队列 q.push(t); TreeNode* p; //用于接收pop出来的节点 q.push(t); //先将根节点入队 while(!q.empty()){ p=q.front(); q.pop(); cout<<p->data; //出队并访问 if(p->left)q.push(p->left); //将左儿子入队 if(p->right)q.push(p->right); //将右儿子入队 } }

推广：若要获得每层最左边的节点（假设将每层的最左边的节点储存在vector中），可用size记录queue中全部是同一层的节点时的节点个数，然后通过size次循环把queue中的节点pop并push其子节点

void LevelOrderTraversal(TreeNode* t){ queue<TreeNode*> q; //创建队列 q.push(t); TreeNode* p; //用于接收pop出来的节点 q.push(t); //先将根节点入队 vector<TreeNode*> v; while(!q.empty()){ int size=q.size(); v.push_back(q.front()); //此时队列中的第一个节点就是最左节点 while(size--){ p=q.front(); q.pop(); cout<<p->data; //出队并访问 if(p->left)q.push(p->left); //将左儿子入队 if(p->right)q.push(p->right); //将右儿子入队 } } }

再推广：若要获得每层最右边的节点，就先push右子树，再push左子树

要获得每层单独的层序遍历序列基本思路一样，也是利用size记录当前queue的大小

推导遍历结果

根据中序遍历和先序遍历或中序遍历和后序遍历和推导出二叉树或另一种遍历

前提：必须有中序遍历
基本思想：递归处理两个遍历序列相对应的一段
先假定遍历序列都储存在数组中
注意要检查边界情况

根据先序和中序推二叉树

关键参数：
对于待处理的两段相对应的序列段，用preL记录先序遍历待处理序列段的左端（起始）下标，用inL记录中序遍历待处理序列段的左端（起始）下标，用len记录待处理序列段的长度
可推出先序遍历待处理序列右端下标为preL+len-1，记录为preR，中序遍历待处理序列右端下标为inL+len-1，记录为inR
找中序遍历中的根节点：
对于先序遍历序列段的第一个元素（左端），该元素就是根节点，在中序遍历序列段中通过遍历找到这个元素并记录该元素的下标，记录为i）
找左子树和右子树的先序遍历序列段和中序遍历序列段：
对于中序遍历，根据根节点的下标i和inL和len可以确定左子树序列长度为i-inL，记录为leftLen，右子树序列长度为inR-i，记录为rightLen
可推出中序遍历左子树的待处理序列左端为inL，右子树的待处理序列左端为i+1
对于先序遍历，可推出先序遍历左子树的待处理序列左端为preL+1，右子树的待处理序列左端为PreL+leftLen+1
递归处理左子树序列段和右子树序列段，边界情况（len == 0）时返回NULL

目的是建树，所以在每次找到根节点后建一个节点，赋为对应的data

TreeNode* solveTree(preL,inL,len){ if(len==0)return NULL; //边界情况 int preR=preL+len-1; int inR=inR+len-1; DataType root=preOrder[preL]; TreeNode* t=new TreeNode; //建根节点 t->data=root; int i; for(i=inL;i<=inR;i++){ if(inOrder[i]==root)break; } int leftLen=i-inL; int rightLen=inR-i; t->left=solveSequence(preL+1,inL,leftLen); t->right=solveSequence(preL+leftLen+1,i+1,rightLen); return t; }

根据先序和中序推后序

假设将得到的后序遍历序列储存在数组postOrder[]中

和根据先序遍历和中序遍历推二叉树不同的是，推后序遍历只需要将找到的root放到后序对应的序列段的右端（最后一个元素）

void solveSequence(preL,inL,postL,len){ if(len==0)return; //边界情况 int preR=preL+len-1; int inR=inR+len-1; int postR=postL+len-1; DataType root=preOrder[preL]; postOrder[postR]=root; int i; for(i=inL;i<=inR;i++){ if(inOrder[i]==root)break; } int leftLen=i-inL; int rightLen=inR-i; t->left=solveSequence(preL+1,inL,postL,leftLen); t->right=solveSequence(preL+leftLen+1,i+1,postL+leftLen+1,rightLen); return t; }