文章目录
树相关概念
1. 总体架构
相关术语
①结点：包含一个数据元素及若干指向子树分支的信息 。
②结点的度：一个结点拥有子树的数目称为结点的度 。
③叶子结点：也称为终端结点，没有子树的结点或者度为零的结点 。
④分支结点：也称为非终端结点，度不为零的结点称为非终端结点 。
⑤树的度：树中所有结点的度的最大值 。
⑥结点的层次：从根结点开始，假设根结点为第1层，根结点的子节点为第2层，依此类推，如果某一个结点位于第L层，则其子节点位于第L+1层 。
⑦树的深度：也称为树的高度，树中所有结点的层次最大值称为树的深度 。
⑧有序树：如果树中各棵子树的次序是有先后次序，则称该树为有序树 。
⑨无序树：如果树中各棵子树的次序没有先后次序，则称该树为无序树 。
⑩森林：由m（m≥0）棵互不相交的树构成一片森林。如果把一棵非空的树的根结点删除，则该树就变成了一片森林，森林中的树由原来根结点的各棵子树构成 。
2.二叉树的分类
- 完全二叉树
- 完全二叉树的特点：叶子结点只能出现在最下层和次下层，且最下层的叶子结点集中在树的左部。需要注意的是，满二叉树肯定是完全二叉树，而完全二叉树不一定是满二叉树。
- 完全二叉树判定
算法思路
判断一棵树是否是完全二叉树的思路
1>如果树为空，则直接返回错
2>如果树不为空：层序遍历二叉树
2.1>如果一个结点左右孩子都不为空，则pop该节点，将其左右孩子入队列；
2.1>如果遇到一个结点，左孩子为空，右孩子不为空，则该树一定不是完全二叉树；
2.2>如果遇到一个结点，左孩子不为空，右孩子为空,或者左右孩子都为空, 且该节点之后的队列中的结点都为叶子节点，那么该树是完全二叉树，否则就不是完全二叉树；
- 平衡二叉树
- 表现特征：平衡树(Balance Tree，BT) 指的是，任意节点的子树的高度差都小于等于1。
3. 模板代码
C语言版本左孩子右兄弟建树
#include<iostream> #include<cstdio> #define maxSize 100000 using namespace std; typedef struct CSNode { int parent; int leftChild; int siBling; }Node; typedef struct save{ Node data[maxSize]; }BT; Node T[maxSize]; // 获取节点深度 int getD(Node node){ int d=0; while(node.parent!=-1) { d++; node = T[node.parent]; } return d; } int main() { // 节点的数量 int t; cin>>t; int flag = t; // 初始化每个子节点的父节点为 -1 while(flag--){ T[flag].parent = -1; T[flag].leftChild = T[flag].siBling = -1; } // 输入节点信息 for(int k=0; k<t; k++){ // 父节点 int par; // 节点所拥有的孩子数量 int total; cin>>par>>total; int c,s=-1; for(int i=0; i<total; ++i){ cin>>c; T[c].parent=par; if(i==0){ // 第一个元素为左孩子 T[par].leftChild = c; }else{ // 其余的元素为T[s]的兄弟 T[s].siBling = c; } // 切换节点， 左孩子右兄弟 s=c; } } // 根节点 int root; for(int j=0; j<t; ++j){ if(T[j].parent == -1 ) root = j; } for(int i=0; i<t; i++){ string type; if(i==root) type="root"; else{ if(T[i].leftChild == -1) type="leaf"; else type = "internal node"; } cout<<"node "<<i<<": parent = " <<T[i].parent<<", depth = "<<getD(T[i])<<", "<<type<<", ["; // 从子结点的最左边开始遍历 int c = T[i].leftChild; while (c != -1) { printf("%d", c); if (T[c].siBling != -1) printf(", "); // 跳到右侧紧邻的兄弟结点 c = T[c].siBling; } cout<<"]"<<endl; } return 0; }
C 语言版本(二叉树搜索)
#include<iostream> using namespace std; #define maxSize 25 typedef struct BinaryTree{ int parent; int lchild,rchild; }BT; BT bt[maxSize]; string gettype(BT obj){ string type; if( obj.parent == -1) type="root"; else if(obj.lchild == -1 && obj.rchild == -1 ) type = "leaf"; else type = "internal node" ; return type; } int getsibling(BT obj, int cur, bool flag){ if(flag){ return -1; } if( bt[obj.parent].lchild == cur ) return bt[obj.parent].rchild; else if( bt[obj.parent].rchild == cur)return bt[obj.parent].lchild; else return -1; } int getdegree(BT o){ int te = 0; if(o.lchild != -1 ) te++; if(o.rchild != -1) te++; return te; } int getdp(BT o) { int de = 0; while(o.parent != -1 ) { de++; o = bt[o.parent]; } return de; } // 递归求高度 int getH( int u ){ int h1=0; int h2=0; if(bt[u].lchild != -1 ) h1 = getH(bt[u].lchild) +1; if(bt[u].rchild != -1 ) h2 = getH(bt[u].rchild) +1; return h1>h2?h1:h2; } void print(BT o, int mm){ int sibling; string type; type = gettype(bt[mm]); if(type == "root") sibling = getsibling(bt[mm] , mm, true) ; else sibling = getsibling(bt[mm] , mm, false) ; cout<<"node "<<mm<<": parent = "<< bt[mm].parent << ", sibling = "<< sibling << ", degree = " << getdegree(bt[mm]) << ", depth = " << getdp(bt[mm]) << ", height = " << getH( mm ) <<", " << type <<endl; } int main() { int t; cin>>t; // 节点初始化 for(int i = 0; i < t; ++i){ bt[i].parent = bt[i].lchild = bt[i].rchild = -1; } // 输入 for(int j = 0; j < t; ++j){ int a,b,c; cin >> a >> b >> c; bt[a].lchild = b; bt[a].rchild = c; bt[b].parent = a; bt[c].parent = a; } for(int m = 0; m < t; ++m){ print(bt[m],m); } cout<<endl; return 0; }
C语言版本的二叉树遍历
// 二叉树的遍历 #include<iostream> #define maxSize 25 using namespace std; typedef struct{ int parent; int l; int r; }Node; Node no[maxSize]; void preOrder(int t){ if(t == -1) return; cout<<' ' << t; preOrder(no[t].l); preOrder(no[t].r); } void inOrder(int t){ if(t == -1) return; inOrder(no[t].l); cout <<' '<< t ; inOrder(no[t].r); } void posOrder(int t){ if(t == -1) return; posOrder(no[t].l); posOrder(no[t].r); cout <<' '<< t ; } int main() { int n; cin>>n; int root; for(int i=0; i<n; ++i) no[i].parent = no[i].l = no[i].r = -1; for(int i = 0; i < n; ++i){ int a,b,c; cin >> a >> b >> c; no[a].l = b; no[a].r = c; no[b].parent = no[c].parent = a; } for(int i=0; i<n; ++i){ if(no[i].parent == -1 ) {root = i;break;} } cout<<"Preorder"<<endl; preOrder(root); cout<<endl; cout<<"Inorder"<<endl; inOrder(root); cout<<endl; cout<<"Postorder"<<endl; posOrder(root); cout<<endl; return 0; }
C++版本二叉树模板(二叉链表建树方法)
#include<iostream> #include<cstring> using namespace std; class BiTreeNode{ public: char data; BiTreeNode *lChild; BiTreeNode *rChild; BiTreeNode():lChild(NULL),rChild(NULL){}; ~BiTreeNode(){}; }; class BiTree{ private: BiTreeNode *root; int pos; // pos方便利用字符串进行建树 string strTree; // 前序遍历的结果字符串，用于建树 BiTreeNode * createBiTree(); void preOrder(BiTreeNode *t); void inOrder(BiTreeNode *t); void postOrder(BiTreeNode *t); public: BiTree(){}; ~BiTree(){}; void createTree(string treeArray); // 利用前序遍历的结果建树 void preOrder(); // 开放接口 void inOrder(); void postOrder(); }; void BiTree::createTree(string treeArray){ pos = 0; strTree.assign(treeArray); root = createBiTree(); } // 利用先序遍历的结果进行 递归建树 BiTreeNode* BiTree::createBiTree(){ BiTreeNode *T; char ch; ch = strTree[pos++]; if(ch=='0'){ T = NULL; } else{ T = new BiTreeNode(); T->data = ch; // 生成根节点 T->lChild = createBiTree(); // 构建左子树 T->rChild = createBiTree(); // 构建右子树 } return T; } void BiTree::preOrder(){ preOrder(root); } void BiTree::preOrder(BiTreeNode *t){ if(t!=NULL){ cout<<t->data<<' '; preOrder(t->lChild); preOrder(t->rChild); } } void BiTree::inOrder(){ inOrder(root); } void BiTree::inOrder(BiTreeNode *t){ if(t!=NULL){ inOrder(t->lChild); cout<<t->data<<' '; inOrder(t->rChild); } } void BiTree::postOrder(){ postOrder(root); } void BiTree::postOrder(BiTreeNode *t){ if(t!=NULL){ postOrder(t->lChild); postOrder(t->rChild); cout<<t->data<<' '; } } int main(){ int Nt; cin >> Nt; while(Nt--){ string s; cin >> s; // BiTree bt(); BiTree bt; bt.createTree(s); bt.preOrder(); cout<<endl; bt.inOrder(); cout<<endl; bt.postOrder(); cout<<endl; } }
DS二叉树——二叉树之数组存储
题目描述
二叉树可以采用数组的方法进行存储，把数组中的数据依次自上而下,自左至右存储到二叉树结点中，一般二叉树与完全二叉树对比，比完全二叉树缺少的结点就在数组中用0来表示。，如下图所示
从上图可以看出，右边的是一颗普通的二叉树，当它与左边的完全二叉树对比，发现它比完全二叉树少了第5号结点，所以在数组中用0表示，同样它还少了完全二叉树中的第10、11号结点，所以在数组中也用0表示。
结点存储的数据均为非负整数
输入
第一行输入一个整数t，表示有t个二叉树
第二行起，每行输入一个数组，先输入数组长度，再输入数组内数据，每个数据之间用空格隔开，输入的数据都是非负整数
连续输入t行
输出
每行输出一个示例的先序遍历结果，每个结点之间用空格隔开
样例输入
3 3 1 2 3 5 1 2 3 0 4 13 1 2 3 4 0 5 6 7 8 0 0 9 10
样例输出
1 2 3 1 2 4 3 1 2 4 7 8 3 5 9 10 6
解题思路
对比完全二叉树以及一般二叉树的数组发现，
完全二叉树的的节点值=一般二叉树的数组索引+1，所以我们可以直接根据完全二叉树就行索引输出。
#include <iostream> using namespace std; class BiTree{ int len; int *tree; void PreOrder(int i); public: BiTree(); ~BiTree(); void PreOrder(); }; BiTree::BiTree() { cin>>len; tree = new int[len+1]; for(int i=1;i<=len;i++) cin>>tree[i]; } BiTree::~BiTree() { delete []tree; } void BiTree::PreOrder() { PreOrder(1); cout<<endl; } void BiTree::PreOrder(int i) { if(tree[i]!=0 && i<=len) { cout << tree[i]<<' '; PreOrder(2 * i); PreOrder(2 * i+1); } } int main() { int t; cin>>t; while (t--) { BiTree myTree; myTree.PreOrder(); } return 0; }
DS二叉树——二叉树之父子结点
题目描述
给定一颗二叉树的逻辑结构如下图，（先序遍历的结果，空树用字符‘0’表示，例如AB0C00D00），建立该二叉树的二叉链式存储结构。
编写程序输出该树的所有叶子结点和它们的父亲结点
输入
第一行输入一个整数t，表示有t个二叉树
第二行起，按照题目表示的输入方法，输入每个二叉树的先序遍历，连续输入t行
输出
第一行按先序遍历，输出第1个示例的叶子节点
第二行输出第1个示例中与叶子相对应的父亲节点
以此类推输出其它示例的结果
样例输入
4 AB0C00D00 AB00C00 ABCD0000EF000 A00
样例输出
C D B A B C A A D F C E A A
解题思路
在遍历的时候，带上双亲节点的值，当遇到叶子时，直接输出叶子的值，把双亲的值入队。
#include<iostream> #include<cstring> #include<queue> using namespace std; queue<char> qf; class BiTreeNode{ public: char data; BiTreeNode *lChild; BiTreeNode *rChild; BiTreeNode():lChild(NULL),rChild(NULL){}; ~BiTreeNode(){}; }; class BiTree{ private: BiTreeNode *root; int pos; // pos方便利用字符串进行建树 string strTree; // 前序遍历的结果字符串，用于建树 BiTreeNode * createBiTree(); void preOrder(BiTreeNode *t, char father); public: BiTree(){}; ~BiTree(){}; void createTree(string treeArray); // 利用前序遍历的结果建树 void preOrder(); // 开放接口 }; void BiTree::createTree(string treeArray){ pos = 0; strTree.assign(treeArray); root = createBiTree(); } // 利用先序遍历的结果进行 递归建树 BiTreeNode* BiTree::createBiTree(){ BiTreeNode *T; char ch; ch = strTree[pos++]; if(ch=='0'){ T = NULL; } else{ T = new BiTreeNode(); T->data = ch; // 生成根节点 T->lChild = createBiTree(); // 构建左子树 T->rChild = createBiTree(); // 构建右子树 } return T; } void BiTree::preOrder(){ preOrder(root,root->data); } void BiTree::preOrder(BiTreeNode *t,char father){ if(t!=NULL){ if(!t->lChild && !t->rChild){ cout<<t->data<<' '; qf.push(father); } preOrder(t->lChild,t->data); preOrder(t->rChild,t->data); } } int main(){ int Nt; cin >> Nt; while(Nt--){ while(!qf.empty()){ qf.pop(); } string s; cin >> s; BiTree bt; bt.createTree(s); bt.preOrder(); cout<<endl; while(!qf.empty()){ cout<<qf.front()<<' '; qf.pop(); } cout<<endl; } return 0; }
