2018-11-18-18:25:23
一：二叉树
1.二叉树的性质
①：在二叉树的第i层上至多有pow(2,i-1)个结点(i>=1)。
②：深度为k的二叉树至多有pow(2,k)-1个结点(k>=1)。
③：对任何一颗二叉树T,如果其终端结点的个数为n0，度为2的结点数为n2，则n0==n2+1。
④：具有n个结点的完全二叉树的深度为log2n(取不大于它的最大正整数)+1。
⑤：对于一颗有n个结点的完全二叉树，对任一结点i(i>=1&&i<=n)有：
<1>:如果i==1，则结点i是二叉树的根，无双亲；如果i>1，则其双亲是结点i/2(取不大于它的最大正整数)。
<2>:如果2*i>n，则结点i无左孩子(结点i为叶子结点)，否则其左孩子是结点2*i。
<3>:如果2*i+1>n，则结点i无右孩子，否则其右孩子是结点2i+1。
2.二叉树的层序遍历：初始时让根结点入队列，然后while循环判断队列不空时，弹出一个结点并且访问它，并把它的所有孩子结点入队列，队列空时结束循环。
1 void PrintBiTree(BiTree T){ 2 //按照层序遍历输出二叉树 3 if(T==NULL) return; 4 queue<BiTree>QueueTreeNode; 5 QueueTreeNode.push(T);//首先将二叉树的头结点放入队列 6 while(!QueueTreeNode.empty()){//如果队列为空则结束遍历 7 BiTree QueueNode=QueueTreeNode.front();//每次访问队列的第一个元素并将其弹出 8 QueueTreeNode.pop(); 9 cout<<QueueNode->Elem<<' '; 10 if(QueueNode->Left_Child)//将第一个元素的左右子树的结点都放入队列 11 QueueTreeNode.push(QueueNode->Left_Child); 12 if(QueueNode->Right_Child) 13 QueueTreeNode.push(QueueNode->Right_Child); 14 } 15 }
3.二叉树的非递归遍历：
① 非递归前序遍历：
<1> 算法思路：
创建一个结点用来遍历二叉树，从二叉树根结点开始访问二叉树，若cur结点存在左子树则将其打印并且入栈等待下一步操作，cur结点不存在左子树时判断栈是否空，栈非空时让cur等于其栈顶元素并且
弹出栈顶元素，接着访问改结点的右子树(左子树刚刚都打印完了才放入栈的呀)。
代码:
1 void PreOrderTraverse_Stack_one(BiTree T){ 2 //非递归实现二叉树的先序遍历 3 BiTree cur=T; 4 stack<BiTree>StackNode; 5 while(cur||!StackNode.empty()){ 6 while(cur){ 7 cout<<cur->Elem;//先访问元素 8 StackNode.push(cur);//然后入栈以便访问他的子树 9 cur=cur->Left_Child;//循环结束时这个结点的所有子树的左子树已经输出完毕并且储存到栈中等待下一步调用 10 } 11 if(!StackNode.empty()){ 12 cur=StackNode.top();//如果栈非空，取栈顶元素并且将其弹出 13 StackNode.pop(); 14 cur=cur->Right_Child;//如果存在右子树则对右子树进行上述操作，不存在右子树则跳过该结点，对下一个结点进行上述操作 15 } 16 } 17 }
<2> 算法思路：
创建一个结点用来遍历二叉树，初始时将二叉树的根结点压入栈顶，对其栈顶进行访问并弹出栈顶元素，先将栈顶输出，然后依次将栈顶元素的右子树和左子树压入栈(如果子树结点非空)，重复上述步骤，
当栈空时结束遍历。
代码：
1 void PreOrderTraverse_Stack_two(BiTree T){ 2 if(!T) return; 3 stack<BiTree>StackNode; 4 BiTree cur=T;//初始时让cur指向二叉树的根结点 5 StackNode.push(cur); 6 while(!StackNode.empty()){ 7 cur=StackNode.top();//每次都让cur指向栈顶结点并且弹出栈顶元素 8 StackNode.pop(); 9 if(cur){//如果栈顶元素存在则输出其并且将它的右子树和左子树依次压入栈中 10 cout<<cur->Elem; 11 StackNode.push(cur->Right_Child); 12 StackNode.push(cur->Left_Child); 13 } 14 } 15 }
② 非递归中序遍历：
算法思路：
创建一个结点来遍历二叉树，从二叉树的根结点开始访问二叉树，因为每个结点又是另一颗二叉树，所以将路径上所有的左子树的结点保存，直至二叉树不存在左子树时访问该结点并且将其弹出，接着对其右子树
进行上述操作，直至栈为空时访问完毕。
代码:
1 void Stack_InOrderTraverse(BiTree T){ 2 //非递归实现二叉树的中序遍历 3 BiTree cur=T; 4 stack<BiTree>StackNode; 5 while(cur||!StackNode.empty()){ 6 while(cur){ 7 StackNode.push(cur);//然后入栈以便访问他的子树 8 cur=cur->Left_Child;//循环结束时这个结点的所有子树的左子树已经输出完毕并且储存到栈中等待下一步调用 9 } 10 if(!StackNode.empty()){ 11 cur=StackNode.top();//如果栈非空，取栈顶元素并且将其弹出 12 cout<<cur->Elem;//访问元素 13 StackNode.pop(); 14 cur=cur->Right_Child;//如果存在右子树则对右子树进行上述操作，不存在右子树则跳过该结点，对下一个结点进行上述操作 15 } 16 } 17 }
③非递归后序遍历：
算法思路：创建一个结点指向二叉树的根结点用来遍历二叉树，首先利用循环找到后续遍历的第一个结点并将路径上的所有元素入栈，接着让cur等于当前的栈顶元素，每次访问栈顶元素并且将其弹出，判断
如果当前结点等于栈顶元素的左儿子则说明右儿子还未处理，则将右儿子插入栈顶，否则用NULL表示可以处理当前栈顶元素，循环上述操作，当栈为空时结束循环。
代码:
1 void PostOrderTraverse_Stack(BiTree T){ 2 stack<BiTree>StackNode; 3 BiTree cur=T;//遍历二叉树所用的结点 4 while(cur||!StackNode.empty()){//栈空或者树不存在时结束遍历 5 while(cur){ 6 StackNode.push(cur); 7 cur=cur->Left_Child?cur->Left_Child:cur->Right_Child;//找到后序遍历的第一个结点，并且将路径上的结点都放入栈 8 } 9 cur=StackNode.top();//每次让cur等于栈顶元素 10 StackNode.pop(); 11 cout<<cur->Elem<<' ';//访问栈顶元素并且将其弹出栈 12 if(!StackNode.empty()&&cur==(StackNode.top())->Left_Child) 13 cur=(StackNode.top())->Right_Child;//如果当前元素为栈顶元素的左儿子则说明右儿子还未处理，则让当前元素等于栈顶元素的，否则用NULL表示可以处理当前栈顶元素 14 else 15 cur=NULL; 16 } 17 }
二叉树完整代码：
1 /********************************************************* 2 链式二叉树基本操作的实现 3 mian函数操作： 4 1.输入一个二叉树，叶结点以‘#’表示 5 6 **********************************************************/ 7 #include <cstdio> 8 #include <iostream> 9 #include <stack> 10 #include <queue> 11 using namespace std; 12 #define Maxn 0xffff 13 typedef char TreeElemtype; 14 typedef struct Bitree{ 15 TreeElemtype Elem; 16 struct Bitree*Right_Child; 17 struct Bitree*Left_Child; 18 }BiNode,*BiTree; 19 20 void CreatBiTree(BiTree &T); 21 void PreOrderTraverse(BiTree T); 22 void InOrderTraverse(BiTree T); 23 void PostOrderTraverse(BiTree T); 24 void PrintBiTree(BiTree T); 25 void Stack_InOrderTraverse_one(BiTree T); 26 void Stack_InOrderTraverse_two(BiTree T); 27 void PreOrderTraverse_Stack_one(BiTree T); 28 void PreOrderTraverse_Stack_two(BiTree T); 29 void PostOrderTraverse_Stack(BiTree T); 30 int Depth_of_BiTree(BiTree T); 31 int Count_of_BiNode(BiTree T); 32 int LeafBiNode(BiTree T); 33 int Node_one_Count(BiTree T); 34 void PrintAllPath(BiTree T, char path[], int pathlen); 35 //main函数内所有数据均为测试数据，读者可根据自己测试方式自行调换 36 37 int main(){ 38 BiTree T; 39 CreatBiTree(T); 40 cout<<"递归式前序遍历输出："<<'\t'; 41 PreOrderTraverse(T); 42 cout<<endl; 43 cout<<"非递归式前序遍历输出："<<'\t'; 44 PreOrderTraverse_Stack_one(T); 45 cout<<endl; 46 cout<<"非递归式前序遍历输出："<<'\t'; 47 PreOrderTraverse_Stack_two(T); 48 cout<<endl; 49 cout<<"递归式中序遍历输出："<<'\t'; 50 InOrderTraverse(T); 51 cout<<endl; 52 cout<<"非递归式中序遍历输出："<<'\t'; 53 Stack_InOrderTraverse_one(T); 54 cout<<endl; 55 cout<<"递归式后序遍历输出："<<'\t'; 56 PostOrderTraverse(T); 57 cout<<endl; 58 cout<<"非递归式后序遍历输出："<<'\t'; 59 PostOrderTraverse_Stack(T); 60 cout<<endl; 61 cout<<"层序遍历输出："<<'\t'; 62 PrintBiTree(T); 63 cout<<endl; 64 cout<<"二叉树的深度为"<<'\t'<<Depth_of_BiTree(T)<<endl; 65 cout<<"二叉树的结点个数为"<<'\t'<<Count_of_BiNode(T)<<endl; 66 cout<<"二叉树的叶子结点个数为"<<'\t'<<LeafBiNode(T)<<endl; 67 cout<<"二叉树的度为1的结点的个数为"<<'\t'<<Node_one_Count(T)<<endl; 68 int pathlen=0; 69 char path[Maxn]; 70 PrintAllPath(T,path,pathlen); 71 return 0; 72 } 73 void CreatBiTree(BiTree&T){ 74 //先序创建二叉树，以'#'代表该结点为叶子结点 75 TreeElemtype ch; 76 cin>>ch; 77 if(ch=='#') 78 T=NULL; 79 else{ 80 T=new BiNode; 81 T->Elem=ch; 82 CreatBiTree(T->Left_Child); 83 CreatBiTree(T->Right_Child); 84 } 85 } 86 87 void PreOrderTraverse(BiTree T){ 88 if(T){ 89 cout<<T->Elem<<' '; 90 PreOrderTraverse(T->Left_Child); 91 PreOrderTraverse(T->Right_Child); 92 } 93 } 94 95 void InOrderTraverse(BiTree T){ 96 if(T){ 97 InOrderTraverse(T->Left_Child); 98 cout<<T->Elem<<' '; 99 InOrderTraverse(T->Right_Child); 100 } 101 } 102 103 void PostOrderTraverse(BiTree T){ 104 if(T){ 105 PostOrderTraverse(T->Left_Child); 106 PostOrderTraverse(T->Right_Child); 107 cout<<T->Elem<<' '; 108 } 109 } 110 111 void PrintBiTree(BiTree T){ 112 //按照层序遍历输出二叉树 113 if(T==NULL) return; 114 queue<BiTree>QueueTreeNode; 115 QueueTreeNode.push(T);//首先将二叉树的头结点放入队列 116 while(!QueueTreeNode.empty()){//如果队列为空则结束遍历 117 BiTree QueueNode=QueueTreeNode.front();//每次访问队列的第一个元素并将其弹出 118 QueueTreeNode.pop(); 119 cout<<QueueNode->Elem<<' '; 120 if(QueueNode->Left_Child)//将第一个元素的左右子树的结点都放入队列 121 QueueTreeNode.push(QueueNode->Left_Child); 122 if(QueueNode->Right_Child) 123 QueueTreeNode.push(QueueNode->Right_Child); 124 } 125 } 126 127 void Stack_InOrderTraverse_one(BiTree T){ 128 //非递归实现二叉树的中序遍历 129 BiTree cur=T; 130 stack<BiTree>StackNode; 131 while(cur||!StackNode.empty()){ 132 while(cur){ 133 StackNode.push(cur);//然后入栈以便访问他的子树 134 cur=cur->Left_Child;//循环结束时这个结点的所有子树的左子树已经输出完毕并且储存到栈中等待下一步调用 135 } 136 if(!StackNode.empty()){ 137 cur=StackNode.top();//如果栈非空，取栈顶元素并且将其弹出 138 cout<<cur->Elem<<' ';//访问元素 139 StackNode.pop(); 140 cur=cur->Right_Child;//如果存在右子树则对右子树进行上述操作，不存在右子树则跳过该结点，对下一个结点进行上述操作 141 } 142 } 143 } 144 145 void PreOrderTraverse_Stack_one(BiTree T){ 146 //非递归实现二叉树的先序遍历 147 BiTree cur=T; 148 stack<BiTree>StackNode; 149 while(cur||!StackNode.empty()){ 150 while(cur){ 151 cout<<cur->Elem<<' ';//先访问元素 152 StackNode.push(cur);//然后入栈以便访问他的子树 153 cur=cur->Left_Child;//循环结束时这个结点的所有子树的左子树已经输出完毕并且储存到栈中等待下一步调用 154 } 155 if(!StackNode.empty()){ 156 cur=StackNode.top();//如果栈非空，取栈顶元素并且将其弹出 157 StackNode.pop(); 158 cur=cur->Right_Child;//如果存在右子树则对右子树进行上述操作，不存在右子树则跳过该结点，对下一个结点进行上述操作 159 } 160 } 161 } 162 163 void PreOrderTraverse_Stack_two(BiTree T){ 164 if(!T) return; 165 stack<BiTree>StackNode; 166 BiTree cur=T;//初始时让cur指向二叉树的根结点 167 StackNode.push(cur); 168 while(!StackNode.empty()){ 169 cur=StackNode.top();//每次都让cur指向栈顶结点并且弹出栈顶元素 170 StackNode.pop(); 171 if(cur){//如果栈顶元素存在则输出其并且将它的右子树和左子树依次压入栈中 172 cout<<cur->Elem<<' '; 173 StackNode.push(cur->Right_Child); 174 StackNode.push(cur->Left_Child); 175 } 176 } 177 } 178 179 void PostOrderTraverse_Stack(BiTree T){ 180 stack<BiTree>StackNode; 181 BiTree cur=T;//遍历二叉树所用的结点 182 while(cur||!StackNode.empty()){//栈空或者树不存在时结束遍历 183 while(cur){ 184 StackNode.push(cur); 185 cur=cur->Left_Child?cur->Left_Child:cur->Right_Child;//找到后序遍历的第一个结点，并且将路径上的结点都放入栈 186 } 187 cur=StackNode.top();//每次让cur等于栈顶元素 188 StackNode.pop(); 189 cout<<cur->Elem<<' ';//访问栈顶元素并且将其弹出栈 190 if(!StackNode.empty()&&cur==(StackNode.top())->Left_Child) 191 cur=(StackNode.top())->Right_Child;//如果当前元素为栈顶元素的左儿子则说明右儿子还未处理，则将右儿子插入栈顶，否则用NULL表示可以处理当前栈顶元素 192 else 193 cur=NULL; 194 } 195 } 196 197 int Depth_of_BiTree(BiTree T){ 198 if(T==NULL) return 0; 199 int m=Depth_of_BiTree(T->Left_Child); 200 int n=Depth_of_BiTree(T->Right_Child); 201 return m>n?m+1:n+1; 202 } 203 204 int Count_of_BiNode(BiTree T){ 205 if(T==NULL) return 0; 206 else return Count_of_BiNode(T->Left_Child)+Count_of_BiNode(T->Right_Child)+1; 207 } 208 209 int LeafBiNode(BiTree T){ 210 if(!T) return 0; 211 if((!T->Left_Child)&&(!T->Right_Child)) 212 return 1; 213 else 214 return LeafBiNode(T->Left_Child)+LeafBiNode(T->Right_Child); 215 } 216 217 int Node_one_Count(BiTree T){ 218 if(!T) return 0; 219 if(((!T->Left_Child)&&(T->Right_Child))||((!T->Right_Child)&&(T->Left_Child))) 220 return 1; 221 else 222 return Node_one_Count(T->Left_Child)+Node_one_Count(T->Right_Child); 223 } 224 225 void PrintAllPath(BiTree T, char path[], int pathlen){//二叉树中从每个叶子结点到根结点的路径 226 if(T!=NULL){ 227 path[pathlen]=T->Elem;//将当前结点放入路径中 228 if(T->Left_Child==NULL&&T->Right_Child==NULL){//叶子结点 229 for(int i=pathlen;i>=0;i--) 230 cout<<path[i]<<" " ; 231 cout<<endl; 232 } 233 else{ 234 PrintAllPath(T->Left_Child,path,pathlen + 1); 235 PrintAllPath(T->Right_Child,path,pathlen + 1); 236 } 237 } 238 } 239 240 /**************************************** 241 Author:CRUEL_KING 242 Time:2018/11/20 243 Program name:链式二叉树基本操作的实现.cpp 244 ****************************************/
二：线索二叉树
1. 线索二叉树的定义：n个结点的二叉链表中含有n+1[2n-(n-1)=n+1]个空指针域。利用二叉链表中的空指针域，存放指向结点在某种遍历次序下的前驱和后继结点的指针（这种附加的指针称为"线索"）。
1 typedef bool PointerTag; 2 typedef char TreeElemtype; 3 typedef struct BiThrNode{ 4 TreeElemtype Elem;//存放结点数据 5 PointerTag LTag,RTag;//true表示指向前驱或后继的线索,false表示指向左右孩子的指针 6 struct BiThrNode *Left_Child,*Right_Child; 7 }BiThrNode,*BiThrTree;
2.线索二叉树结构实现：线索化的实质就是将二叉链表中的空指针改为指向前驱和后继的线索，这种过程在遍历二叉树时进行。
1 BiThrTree Pre;//全局变量，始终指向上一个被访问过的结点 2 void InThreading(BiThrTree p){ 3 //中序遍历进行中序线索化 4 if(p){ 5 InThreading(p->Left_Child); 6 if(!p->Left_Child){ 7 p->LTag=true; 8 p->Left_Child=Pre; 9 } 10 if(!Pre->Right_Child){ 11 Pre->RTag=true; 12 Pre->Right_Child=p; 13 } 14 Pre=p; 15 InThreading(p->Right_Child); 16 } 17 }
3.线索二叉树的遍历：和双向链表结构一样，在二叉树线索链表上添加一个头结点，并令其Left_Child域的指针指向二叉树的根结点，其Right_Child域的指针指向中序遍历时访问的最后一个结点。(以中序线索化为例)，同时，令二叉树的中序序列中的第一个结点的Left_Child域和最后一个结点的Right_Child域指针均指向头结点。这样定义的好处就是既可以从第一个结点起顺后继进行遍历，也可以从最后一个结点开始顺前驱进行遍历。
代码思路：
①：申请一个新的结点p让他指向二叉树的根结点，T指向二叉树的头结点。
②：如果该结点等于二叉树的头结点(即中序序列最后一个结点的Right_Child域指针指向的结点) 则结束操作。
③：如果p->LTag为true则执行⑤。
④：p指向其左子树并且执行③。
⑤：输出p结点的数据域。
⑥：如果p->RTag==false或P的Right_Child与T相等时执行⑨。
⑦：p指向其右子树。
⑧：输出p结点的数据域并且执行⑥。
⑨：让p指向其右子树并且执行②。
1 /* T指向头结点，头结点左孩子Left_Child指向二叉树的根结点， 2 头结点右孩子Right_Child指向中序遍历的最后一个结点。 3 */ 4 bool InOrderTraverse_The(BiThrTree T){ 5 BiThrTree p; 6 p=T->Left_Child;//p指向二叉树的根结点 7 while(p!=T){ //空树或遍历结束时p==T 8 while(!p->LTag) 9 p=p->Left_Child;//循环结束时p指向中序序列的下一个结点 10 cout<<p->Elem; 11 while(p->RTag&&p->Right_Child!=T){ 12 p=p->Right_Child; 13 cout<<p->Elem; 14 } 15 p=p->Right_Child;//让p指向其右子树 16 } 17 return true; 18 }