数据结构7——二叉树

一、二叉树的定义与性质

1.定义

首先是树形结构，每个节点最多有2棵树，二叉树的子树有左右之分，不能颠倒。

2.性质

（1）二叉树的第i层,最多有2的（i-1)次幂。
（2）深度为k（层数也为k)的二叉树，最多有2^k-1结点。
（3）对于任意二叉树而言，若度为0的节点为N0个，度为2的节点为N2个，则：N0=N2+1。

二、二叉树的节点设计

1.采用顺序存储结构还是链式存储结构？

采用链式存储结构。

原因：顺序存储结构用数组实现，但对于数组来说，只适用于完全二叉树的情况，而对于一般的情况来说，浪费的空间较大。

2.二叉树（二叉链表）的有效节点设计

对于一个结点来说，最多有2个孩子，分别是左孩子和右孩子，所以设计二叉链表时，不仅需要设计该节点的值，而且还需要2个指针域，一个表示当前节点的左孩子，一个表示当前结点的右孩子。

typedef int ELEM_TYPE;
typedef struct Bin_Node
{ELEM_TYPE val;// 数据域struct Bin_Node* leftchild; //左孩子域struct Bin_Node* rightchild;//右孩子域 
}Bin_Node;

3.二叉树（二叉链表）的辅助结点的设计

让其辅助结点指向该二叉树的根节点位置。

typedef struct Bin_Tree{Bin_Node*root;  //存放二叉树根节点的地址 
}Bin_Tree; 

三、二叉树的基本操作

1.二叉树的初始化

 将二叉树的根节点置为空。

void Init(Bin_Tree* tree)
{assert(tree!=NULL);tree->root=NULL;// 将根节点置为空 } 

2.购买新结点

（1）malloc申请空间，并判断空间是否申请成功。
（2）如果申请成功，则把其左孩子和右孩子指针置为空。

Bin_Node* BuyNode()
{//1.malloc申请空间Bin_Node*pnewnode=(Bin_Node*)malloc(sizeof(Bin_Node));if(pnewnode==NULL)exit(1);//将左孩子和右孩子置为空pnewnode->leftchild=pnewnode->rightchild=NULL; return pnewnode; } 

3.二叉树的构建

3.1 用单个序列构造（此处使用先序）

(先序、中序、后序的一个，需要包含终止符#）

（1）先将根节点置为空。

（2）从键盘输入数据，判断数据是否为“#”

（3）如果不是，则购买结点，并为该节点赋值。对其左孩子和右孩子采用递归方法调用。

（4）如果是，则不断回退。

//采用先序遍历，使用递归实现 
Bin_Node* Create_Bin_Tree1()
{//将根节点置为空 Bin_Node* root=NULL;ELEM_TYPE val;scanf("%d",&val);if(val!='#') //判断是否是终止符 {root=BuyNode(); //购买节点，并为结点赋值 root->val=val;root->leftchild=Create_Bin_Tree1(); //对其左右孩子采用递归方式实现 root->rightchild=Create_Bin_Tree1();} return root;
}

3.2 用两个序列构造

（不需要包含终止符#,但都需要存在中序遍历）

3.2.1 采用先序和中序的遍历的方式

（1）首先定义一个节点，将该结点置为空。

（2）判断先序或者中序中元素的个数，如果个数为0，则不需要进行构造。

（3）个数大于0，则开始构造。

（4）购买一个结点，通过先序序列为该结点赋值，因为先序序列的第一个节点就是根节点。

（5）在中序序列找到当前结点的值，并返回下标。此时，根据此下标，可以将中序序列分为左右两个部分。

（6）对左右两个部分分别采用递归调用。

int Find_Pos(const char*in_str,ELEM_TYPE val) //在中序序列中找出val值所在的下标，进而将中序序列一分为二 
{int count=0;  //通过变量来返回位置 while(*in_str!=val){in_str++;count++;}return count; 
}
Bin_Node* Create_Bin_Tree3_Pre_In(const char* pre_str, const char* in_str, int n)  
{Bin_Node* pnewnode=NULL;if(n>0)//判断先序/中序的有效元素的个数 {//1.购买节点pnewnode=BuyNode();//2.为购买的节点赋值pnewnode->val=pre_str[0];//因为先序序列的第一个节点就是根节点//3.根据penwnode的值将中序划分为左右两个部分int index=Find_Pos(in_str,pre_str[0]);//4.将问题规模缩小化，采用递归的方式pnewnode->leftchild=Create_Bin_Tree3_Pre_In(pre_str+1,in_str,index);pnewnode->rightchild=Create_Bin_Tree3_Pre_In(pre_str+1+index,in_str+index+1,n-index-1); }return pnewnode;}

3.2.2 采用中序和后序的遍历的方式

（1）首先定义一个节点，将该结点置为空。

（2）判断后序或者中序中元素的个数，如果个数为0，则不需要进行构造。

（3）个数大于0，则开始构造。

（4）购买一个结点，通过后序序列为该结点赋值，因为后序序列的最后一个节点就是根节点。

（5）在中序序列找到当前结点的值，并返回下标。此时，根据此下标，可以将中序序列分为左右两个部分。

（6）对左右两个部分分别采用递归调用。

int Find_Pos(const char*in_str,ELEM_TYPE val) //在中序序列中找出val值所在的下标，进而将中序序列一分为二 
{int count=0;  //通过变量来返回位置 while(*in_str!=val){in_str++;count++;}return count; 
}Bin_Node* Create_Bin_Tree3_In_Post(const char* in_str, const char* post_str, int n)
{Bin_Node*pnewnode=NULL;if(n>0) //存在有效的个数{pnewnode=BuyNode();//购买节点pnewnode->val=post_str[n-1];//通过后序遍历得到根节点//根据pnewnode的值将中序序列划分为左右两个部分 int index=Find_Pos(in_str,pnewnode->val);//将问题规模缩小化，采用递归的方式pnewnode->leftchild=Create_Bin_Tree3_In_Post(in_str,post_str,index) ;pnewnode->rightchild=Create_Bin_Tree3_In_Post(in_str+index+1,post_str+index,n-index-1);} return pnewnode;
}

4.二叉树的遍历（非递归实现）

4.1 二叉树的先序遍历 （根左右）

（1）申请一个栈，然后将根节点入栈。

（2）while循环判断栈是否为空，如果栈不为空，取出栈顶元素值。

（3）判断其左右孩子是否存在，如果存在，则先将右孩子压入栈，然后在将左孩子压入栈。

（4）直到栈为空（while结束为止）

void Preorder(Bin_Tree* tree)
{//assert(tree!=NULL);//申请一个栈，将根节点入栈std::stack<Bin_Node*> st;st.push(tree->root);//判断栈是否为空while(!st.empty()){//取出栈顶元素的值Bin_Node*p=st.top();st.pop();//打印printf("%d",p->val); //先判断其右孩子是否存在，存在则入栈if(p->rightchild!=NULL){st.push(p->rightchild);}//判断其左孩子是否存在，存在则入栈 if(p->leftchild!=NULL){st.push(p->leftchild);} } } 

4.2 二叉树的中序遍历（左根右）

（1）先申请一个栈，将根节点压入栈中。

（2）设置一个标记位：判断当前结点是新插入的结点还是老结点。

（3）如果是新插入的节点，则判断其左孩子是否存在，存在则将左孩子压入栈中，直到左孩子为空。

（4）此时，已经将最左边的全部压入栈中，将当前的栈顶结点出栈，并打印栈顶元素的值。

（5）判断当前节点的右孩子是否存在，存在则将右孩子压入栈中，此时更改标记位为新插入的结点。

（6）如果右孩子不存在，则更改标记位为老节点。

（7）直到栈为空结束。

void Inorder(Bin_Tree* tree)
{//assertassert(tree->root!=NULL);//申请一个栈std::stack<Bin_Node*> st;//将根节点入栈st.push(tree->root);//定义一个标记位bool tag=true;  //表示是刚插入的结点 while(!st.empty()){//判断当前节点是刚插入的结点还是老结点 while(tag&&st.top()->leftchild!=NULL) //是新结点且左孩子不为空 {//将左孩子入栈st.push(st.top()->leftchild); }//此时，获取栈顶元素的值Bin_Node* p=st.top() ;st.pop();printf("%d ",p->val);//判断其右孩子是否存在if(p->rightchild!=NULL){//存在则将右孩子入栈，并更改标记位st.push(p->rightchild);tag=true; }else{tag=false;} }} 

4.3 二叉树的后序遍历（左右根）

4.3.1 双栈法实现

（1）先申请两个栈，s1和s2。其中s2表示结点的访问顺序。将根节点压入到s1中。

（2）判断s1是否为空，如果不为空，则将当前节点取出，压入到s2中，并判断当前结点的左右孩子是否存在，如果存在，则将其压入到s1中。

（3）重复执行，直到s1为空，此时，将s2中各节点的元素值打印出来。

void PostOrder(Bin_Tree* tree)
{//申请两个栈  S1 S2 std::stack<Bin_Node*> s1,s2;//将根节点压入到S1中s1.push(tree->root) ;//判断S1是否为空Bin_Node*p=NULL;while(!s1.empty()) {p=s1.top();//获取当前的栈顶元素 s1.pop() ;s2.push(p);//将结点压入到S2中if(p->leftchild!=NULL)  //判断左孩子是否为空 {s1.push(p->leftchild);}if(p->rightchild!=NULL) //判断右孩子是否为空 {s1.push(p->rightchild);}	}//此时，s1为空，则将S2中的元素逐个打印while(!s2.empty()) {printf("%d ",s2.top()->val);s2.pop();}} 

4.3.2 单栈法实现

（1）申请一个栈，将根节点入栈。

（2）栈不为空时，先去判断当前结点是新结点还是老结点，如果是新结点再判断其左孩子是否存在，如果存在则将左孩子压入栈中。

（3）如果左孩子不存在或者当前结点是老节点，则去判断当前节点是否存在右孩子，如果右孩子存在，则将右孩子压入栈。右孩子不存在或者右孩子是老结点，则将该节点的元素值打印出来，并让当前指针指向该结点。

void PostOrder1(Bin_Tree* tree)
{assert(tree!=NULL);//1.申请一个栈std::stack<Bin_Node*> st;st.push(tree->root);//定义一个标记位，用来遍历最左边的结点bool tag=true; //定义一个指针，用来记录右边刚被访问的节点Bin_Node* preNode=NULL; //2.判断栈是否为空while(!st.empty()){//判断是否是新结点以及其左孩子是否存在while(tag&&st.top()->leftchild!=NULL){st.push(st.top()->leftchild);//将左孩子压入到栈中 }//此时左边已经结束 ，判断右孩子是否存在if(st.top()->rightchild==NULL||st.top()->rightchild==preNode){Bin_Node*p=st.top();st.pop();printf("%d ",p->val);preNode=p;tag=false;}else  //右孩子存在，则将右孩子入栈 {st.push(st.top()->rigthchild);tag=true;// 只要有入栈的操作则表示是新结点，需要更改标记位 }} } 

4.4 二叉树的层序（层次）遍历 

（1）申请一个队列，并将根节点入队。

（2）循环判断队列是否为空。

（3）如果队列不为空，则获取队头元素，并将队头元素出队，接着判断其左右孩子是否存在，如果存在，则将左右孩子入队。

（4）如果为空，则结束。

void Level_Traversal(Bin_Node* root) 
{//先申请一个队列 std::queue<Bin_Node*> q;//将根节点入队 q.push(root);//循环判断根节点是否为空 while(!q.empty()){Bin_Node*p=q.front();//获取队头元素 q.pop();printf("%d ",p->val);//判断其左右孩子是否存在if(p->leftchild!=NULL){q.push(p->leftchild);} if(p->rightchild!=NULL){q.push(p->rightchild);}} 	
}

4.5 二叉树的正S遍历

（1）申请两个栈，栈s1,s2。

（2）将根节点入栈到s1中。

（3）只要两个栈中，一个不为空，则入栈。

（4）判断哪个栈不为空，如果栈1不为空，则将栈1中的元素取出，并按照从右向左的顺序判断其左右孩子是否存在，如果存在，则将右孩子和左孩子分别入栈2。直到栈1为空，停止。

（5）如果栈2不为空，则将栈2中的元素取出，并按照从左向右的顺序判断其左右孩子是否存在，如果存在，则将左孩子和右孩子分别入栈1。直到栈2为空，停止。

（6）如此循环，直到栈1和栈2均为空为止。

void S_Level_Traversal(Bin_Node* root)
{//申请两个栈 std::stack<Bin_Node*> st1,st2;//将根节点入栈1st1.push(root);//while循环while(!st1.empty()||!st2.empty()){while(!st1.empty()) //栈1不为空 {//取出栈中的元素值Bin_Node*p=st1.top();st1.pop();printf("%d ",p->val); //按照从右向左的顺序判断其孩子是否存在，存在则将孩子压入栈2中if(p->rightchild!=NULL){st2.push(p->rightchild);} if(p->leftchild!=NULL){st2.push(p->leftchild);}}while(!st2.empty()) //栈2不为空，则取出元素的值{Bin_Node*p=st2.top() ;st2.pop();printf("%d ",p->val);//按照从左向右的顺序判断其孩子是否存在，存在则将孩子压入栈1中if(p->leftchild!=NULL) {st1.push(p->leftchild);}if(p->rightchild!=NULL){st1.push(p->rightchild);}} } 
}

4.6 二叉树的倒S遍历

（1）申请两个栈，栈s1,s2。

（2）将根节点入栈到s1中。

（3）只要两个栈中，一个不为空，则入栈。

（4）判断哪个栈不为空，如果栈1不为空，则将栈1中的元素取出，并按照从左向右的顺序判断其左右孩子是否存在，如果存在，则将左孩子和右孩子分别入栈2。直到栈1为空，停止。

（5）如果栈2不为空，则将栈2中的元素取出，并按照从右向左的顺序判断其左右孩子是否存在，如果存在，则将右孩子和左孩子分别入栈1。直到栈2为空，停止。

（6）如此循环，直到栈1和栈2均为空为止。

void Reverse_S_Level_Traversal(Bin_Node* root)
{//申请两个栈 std::stack<Bin_Node*> st1,st2;//将根节点入栈1st1.push(root);//while循环while(!st1.empty()||!st2.empty()){while(!st1.empty()) //栈1不为空 {//取出栈中的元素值Bin_Node*p=st1.top();st1.pop();printf("%d ",p->val); //按照从左向右的顺序判断其孩子是否存在，存在则将孩子压入栈2中if(p->leftchild!=NULL){st2.push(p->leftchild);}if(p->rightchild!=NULL){st2.push(p->rightchild);} }while(!st2.empty()) //栈2不为空，则取出元素的值{Bin_Node*p=st2.top() ;st2.pop();printf("%d ",p->val);//按照从右向左的顺序判断其孩子是否存在，存在则将孩子压入栈1中if(p->rightchild!=NULL){st1.push(p->rightchild);}if(p->leftchild!=NULL) {st1.push(p->leftchild);}} } 
}

5. 二叉树的销毁 （非递归）

（1）申请一个栈，将根节点入栈

（2）判断栈是否为空，如果为空，则结束。

（3）如果不为空，则将栈顶元素出栈，判断其左右孩子是否为空，如果不为空，则将左右孩子入栈。

（4）直到栈空结束。

void Destroy1(Bin_Tree* pTree)//非递归
{//申请一个栈 std::stack<Bin_Node*> st;st.push(pTree->root);//将根节点入栈 while(!st.empty()){Bin_Node*p=st.top();st.pop();//将栈顶结点出栈 if(p->leftchild!=NULL) //判断其左右孩子是否存在 {st.push(p->leftchild);  }if(p->rightchild!=NULL){st.push(p->rightchild);}free(p);//释放该节点 } 
}