文章目录

二叉树的存储链表数组 二叉树的基本操作插入递归非递归 删除查找并修改计算结点数计算树高 二叉树的算法二叉树遍历前序遍历中序遍历后序遍历层序遍历 二叉树判别判别完全二叉树思路1 入队列 & 最后一个非叶结点后的结点必无孩子思路2 入队列 & 出现空结点后不能再有非空 判别满二叉树思路1 完全二叉树 & 树高h+总结点数==2^树高^-1思路2 层序遍历 & 每层结点数==2^当前层高度^-1 判别二叉搜索树思路1 中序遍历为升序序列思路2 中序遍历 & 前一个数必小于后一个数

二叉树的存储

链表

数组

适用于 完全二叉树、满二叉树

二叉树的基本操作

插入

递归

// 二叉搜索树的插入---递归 void insert_dg(Node * &p, int x) { if(p==NULL) { p = new Node(x); return; } if(p->d==x)return; //如果已经存在，就不插入 else if(p->d>x) insert_dg(p->l,x); else insert_dg(p->r,x); }

非递归

void insert(int x) { if(root==NULL) { root = new Node(x); return; } Node* p=root; while(p!=NULL) { if(p->d==x)return; //如果已经存在，就不插入 else if(p->d>x) { if(p->l==NULL) { p->l = new Node(x); } p = p->l; } else { if(p->l==NULL) { p->r = new Node(x); } p = p->r; } } }

删除

查找并修改

// 二叉树查找修改 bool search_update(Node * root,int x,int newx) { if(root==NULL)return false;// 树空 if(root->d==x) { root->d=newx; return true; } bool f = search_update(root->l,x,newx); if(f) return true; return search_update(root->r,x,newx); }

计算结点数

// c为结点总数 方法一 void count(Node * nd,int &c){ if(nd==NULL)return; c++; count(nd->l,c); count(nd->r,c); } // 返回值为结点总数 方法二 int count(Node *nd){ if(nd==NULL)return 0; int lc = count(nd->l); int rc = count(nd->r); return lc+rc+1; }

计算树高

// 返回值为树高 int high(Node * nd){ if(nd==NULL)return 0; int lh = high(nd->l); int rh = high(nd->r); return max(lh,rh)+1; }

二叉树的算法

二叉树遍历

前序遍历

void pre_order(Node *p) { if(p==NULL)return; printf("%d ",p->d); pre_order(p->l); pre_order(p->r); }

中序遍历

void in_order(Node *p) { if(p==NULL)return; in_order(p->l); printf("%d ",p->d); in_order(p->r); }

后序遍历

void post_order(Node *p) { if(p==NULL)return; post_order(p->l); post_order(p->r); printf("%d ",p->d); }

层序遍历

void level_order() { if(root==NULL)return; //空树 queue<Node *> q; q.push(root); while(!q.empty()) { Node* now = q.front(); q.pop(); printf("%d ",now->d); if(now->l!=NULL)q.push(now->l); if(now->r!=NULL)q.push(now->r); } }

二叉树判别

判别完全二叉树

思路1 入队列 & 最后一个非叶结点后的结点必无孩子

BFS 将每一个节点都加入到队列，同时执行下面的判断

当前节点有右孩子，但没有左孩子，直接返回 false当前节点有左孩子没右孩子，那么接下来遇到的所有节点必须是叶子节点 bool isCBT(){ queue<Node *> q; q.push(root); bool leaf=false; while(!q.empty()){ Node * now = q.front(); q.pop(); if(leaf&&(now->l!=NULL||now->r!=NULL))return false; //最后一个非叶子节点已出现，后序节点不可再为非叶子 if(now->l!=NULL)q.push(now->l); else if(now->r!=NULL) return false; //左孩子空，右孩子不空，不是CBT if(now->r!=NULL)q.push(now->r); else leaf = true; //最后一个非叶子节点已出现 } return true; }

思路2 入队列 & 出现空结点后不能再有非空

// 判别是否完全二叉树---链表存储的树 bool isCBT(){ queue<Node *> q; q.push(root); while(!q.empty()){ Node * now = q.front(); q.pop(); if(now==NULL)break; // 出现空节点后，队列剩余所有节点都必须为空 q.push(now->l); q.push(now->r); } while(!q.empty()){ Node * now = q.front(); q.pop(); if(now!=NULL)return false; } return true; }

判别满二叉树

思路1 完全二叉树 & 树高h+总结点数==2^树高-1

// 判别是否满二叉树 bool isFBT() { // 1 判断是否完全二叉树 bool cbt = isCBT(); if(cbt==false)return false; // 2 计算树高 int h = high(root); // 3 计算总结点数 int c = count(root); // 3 判断是否满 if(c==pow(2,h)-1)return true; return false; }

思路2 层序遍历 & 每层结点数==2^{当前层高度}-1

判别二叉搜索树

思路1 中序遍历为升序序列

思路2 中序遍历 & 前一个数必小于后一个数

// 判别是否二叉搜索树 bool isBST(Node * nd,int &pre){ if(nd==NULL)return true; bool l = isBST(nd->l,pre); if(l==false)return false; if(pre>nd->d)return false; pre=nd->d; return isBST(nd->r,pre); }