wordpress站内搜索框,网页设计图片变圆角,爱战网关键词挖掘机,视觉中国网站建设公司1 二叉树 二叉树和树都属于树形结构#xff0c;但两者互不包含。即二叉树不是特殊的树。 1.1 二叉树的基本概念
1.2 二叉树的顺序存储
仅适用于完全二叉树
#define MaxSize 100
typedef int ElemType;
typedef struct TreeNode{ElemType value;//结点中的数据元素bool isE…
1 二叉树 二叉树和树都属于树形结构但两者互不包含。即二叉树不是特殊的树。 1.1 二叉树的基本概念
1.2 二叉树的顺序存储
仅适用于完全二叉树
#define MaxSize 100
typedef int ElemType;
typedef struct TreeNode{ElemType value;//结点中的数据元素bool isEmpty;//结点是否为空
}TreeNode;
构造结点数为MaxSize的完全二叉树t。
TreeNode t[MaxSize];
1.3 二叉树的链式存储
1.3.1 二叉链表
typedef struct BiNode{ElemType data;//数据域 struct BiNode *lchild,*rchild;//左右孩子指针
}BiNode,*BiTree;
二叉链表具体实现
#includeiostream
#includestack
#includequeue
using namespace std;
typedef char ElemType;
//二叉树的结点链式存储
typedef struct BiNode{ElemType data;//数据域 struct BiNode *lchild,*rchild;//左右孩子指针
// struct BiTNode *parent;//父节点指针 三叉链表
}BiNode,*BiTree;
//先序遍历的顺序建立二叉链表
void CreateBiTree(BiTree T){char ch;cinch;if(ch#) TNULL;else{Tnew BiNode;T-datach; CreateBiTree(T-lchild);CreateBiTree(T-rchild);}
}
//先序遍历
void PreOrder(BiTree T){if(T!NULL){coutT-data ;PreOrder(T-lchild);PreOrder(T-rchild);}
}
//中序遍历
void InOrder(BiTree T){if(T!NULL){PreOrder(T-lchild);coutT-data ;PreOrder(T-rchild);}
}
//后序遍历
void AfterOrder(BiTree T){if(T!NULL){PreOrder(T-lchild);PreOrder(T-rchild);coutT-data ;}
}
//非递归调用的先序遍历
void PreOrderTree(BiTree T){stackBiNode * s;while(T||!s.empty()){while(T){coutT-data;s.push(T);TT-lchild;}if(!s.empty()){Ts.top();s.pop();TT-rchild;}}coutendl;
}
//非递归调用的中序遍历
void InOrderTree(BiTree T){stackBiNode * s;while(T||!s.empty()){while(T){s.push(T);TT-lchild;}if(!s.empty()){Ts.top();s.pop();coutT-data;TT-rchild;}}coutendl;
}//非递归调用的后序遍历
void AfterOrderTree(BiTree T){stackBiNode* s;BiNode* lastVisited NULL; // 记录上一个访问过的结点while (T || !s.empty()) {while (T) {s.push(T);T T-lchild;}if (!s.empty()) {BiNode* topNode s.top();if (topNode-rchild topNode-rchild ! lastVisited) {T topNode-rchild;} else {cout topNode-data;lastVisited topNode; s.pop();}}}cout endl;
}
//层次遍历
void LevelOrder(BiTree T){queueBiNode * q;q.push(T);while(q.size()){BiNode *fq.front();q.pop();coutf-data;if(f-lchild!NULL){q.push(f-lchild);}if(f-rchild!NULL){q.push(f-rchild);}}coutendl;
}
//复制二叉树
void Copy(BiTree T,BiTree NewT){if(TNULL){NewTNULL;return;}else{NewTnew BiNode;NewT-dataT-data;Copy(T-lchild,NewT-lchild);Copy(T-rchild,NewT-rchild);}
}
//计算二叉树的深度
int Depth(BiTree T){if(TNULL){return 0;}int mDepth(T-lchild);int nDepth(T-rchild);if(mn){return m1;}else{return n1;}
}
//统计二叉树中结点的个数
int NodeCount(BiTree T){if(TNULL) return 0;else return NodeCount(T-lchild)NodeCount(T-rchild)1;
}
int main(){BiTree T;cout------------------创建二叉链表先序遍历的顺序------------------endl;CreateBiTree(T);cout创建完成:;PreOrder(T);//先序遍历的顺序输出二叉树coutendl;cout------------------先序遍历输出二叉树------------------endl;PreOrderTree(T);cout------------------中序遍历输出二叉树------------------endl;InOrderTree(T);cout------------------后序遍历输出二叉树------------------endl;AfterOrderTree(T);cout------------------层次遍历输出二叉树------------------endl;LevelOrder(T);cout------------------求深度------------------endl;cout深度为Depth(T)endl; cout------------------求结点个数------------------endl;cout结点个数为NodeCount(T)endl;return 0;
} 求中序遍历的前驱和后继
//找前驱
BiNode *p;//目标结点
BiNode *pre;
BiNode *final;
void visit(BiNode *q){if(qp){finalpre;}else{preq;}
// //找后继
// if(prep){
// finalq;
// }else{
// preq;
// }
}
void findPre(BiTree T){if(T!NULL){TT-lchild;visit(T);TT-rchild;}
}
1.3.2 线索链表
定义
typedef char ElemType;
typedef struct BiThrNode{ElemType data;struct BiThrNode *lchild,*rchild;int LTag,RTag;//左右标志0指向左右孩子 1指向前驱或后继
}BiThrNode,* BiThrTree;
先序线索化
//先序线索化(防止转圈问题)
void PreThreadTree(BiThrNode *p,BiThrNode *pre){if(p!NULL){//根 if(p-lchildNULL){p-LTag1;p-lchildpre;}else{p-LTag0;}if(pre!NULLpre-rchildNULL){pre-RTag0;pre-rchildp;}else{p-RTag0;}prep;//左if(p-LTag0) PreThreadTree(p-lchild,pre);//右 PreThreadTree(p-rchild,pre);}
}
void CreatePreThreadTree(BiThrTree T){BiThrNode *preNULL;if(T!NULL){InThreadTree(T,pre);if(pre-rchildNULL){pre-RTag1;}}
}
中序线索化
//中序线索化
void InThreadTree(BiThrNode *p,BiThrNode *pre){if(p!NULL){InThreadTree(p-lchild,pre);if(p-lchildNULL){p-LTag1;p-lchildpre;}else{p-LTag0;}if(pre!NULLpre-rchildNULL){pre-RTag0;pre-rchildp;}else{p-RTag0;}prep;InThreadTree(p-rchild,pre);}
}
void CreateInThreadTree(BiThrTree T){BiThrNode *preNULL;if(T!NULL){InThreadTree(T,pre);if(pre-rchildNULL){pre-RTag1;}}
} 后序线索化
//后序线索化
void PostThreadTree(BiThrTree p,BiThrNode *pre){if(p!NULL){//左PostThreadTree(p-lchild,pre);//右 PostThreadTree(p-rchild,pre);//根 if(p-lchildNULL){p-LTag1;p-lchildpre;}else{p-LTag0;}if(pre!NULLpre-rchildNULL){pre-RTag0;pre-rchildp;}else{p-RTag0;}prep;}
}
void CreatePostThreadTree(BiThrTree T){BiThrNode *preNULL;if(T!NULL){InThreadTree(T,pre);if(pre-rchildNULL){pre-RTag1;}}
}
1.3.3 三叉链表
typedef struct BiNode{ElemType data;//数据域 struct BiNode *lchild,*rchild;//左右孩子指针 struct BiTNode *parent;//父节点指针
}BiNode,*BiTree;
2 树
1.1 树的基本概念
树Tree是nn0个结点的有限集它或为空树n0或为非空树。
基本术语 结点树中的一个独立单元 1.2 树的
