本文共 8347 字，大约阅读时间需要 27 分钟。

树相关概念

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
   
    #include
    
     #define maxSize 100000using 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
     
      >par>>total;    int c,s=-1;    for(int i=0; i
      
       >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
      
     
    
   

C 语言版本(二叉树搜索)

#include
   
    using namespace std;#define maxSize 25typedef 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 "<
    
     <<": parent = "<< bt[mm].parent    << ", sibling = "<< sibling << ", degree = " << getdegree(bt[mm])    << ", depth = " << getdp(bt[mm]) << ", height = " << getH( mm ) <<", " << type <
     
      >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<
     
    
   

C语言版本的二叉树遍历

// 二叉树的遍历#include
   
    #define maxSize 25using 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
    
     > a >> b >> c;    no[a].l = b;    no[a].r = c;    no[b].parent = no[c].parent = a;  }  for(int i=0; i
    
   

C++版本二叉树模板(二叉链表建树方法)

#include
   
    #include
    
     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<
     
      data<<' ';		preOrder(t->lChild);		preOrder(t->rChild);	} }void BiTree::inOrder(){	inOrder(root);}void BiTree::inOrder(BiTreeNode *t){ 	if(t!=NULL){		inOrder(t->lChild);		cout<
      
       data<<' ';		inOrder(t->rChild);	} }void BiTree::postOrder(){	postOrder(root);}void BiTree::postOrder(BiTreeNode *t){		if(t!=NULL){		postOrder(t->lChild);		postOrder(t->rChild);		cout<
       
        data<<' ';	} }int main(){	int Nt;	cin >> Nt;	while(Nt--){		string s;		cin >> s;		//		BiTree bt();		BiTree bt;		bt.createTree(s);		bt.preOrder();		cout<
       
      
     
    
   

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 
   
    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<
    
     >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
   
    #include
    
     #include
     
      using namespace std;queue
      
        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<
       
        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<