网站开发系统的可行性研究报告,网站建设公司西安,商城WordPress,深圳展厅公司二叉树层次建树
对于二叉树#xff0c;建树过程中需要一个#xff08;尾插法的#xff09;链表#xff08;或队列#xff09;来辅助确认当前父亲节点
由于尾插法需要一个尾指针。因此可以理解为队列#xff0c;只不过是不带头结点的链表版队列。
但其实就是一个辅助找…二叉树层次建树
对于二叉树建树过程中需要一个尾插法的链表或队列来辅助确认当前父亲节点
由于尾插法需要一个尾指针。因此可以理解为队列只不过是不带头结点的链表版队列。
但其实就是一个辅助找到当前父亲节点的作用不必纠结是啥名字。
代码如下
#includestdio.h
#includestdlib.h
typedef char ElemType;
//树结构体
typedef struct tree_node{ElemType val;struct tree_node*lc;struct tree_node*rc;
}Tnode,*BTree;//链表
typedef struct link{BTree tree;//存储的是树的节点struct link*next;
}LinkNode,*LinkList;void build_tree(BTreetree,LinkListfront,LinkList rear)
{//还需要一个指向当前父亲节点的指针LinkList cur NULL;ElemType data;while(scanf(%c,data) data ! \n){//每次来一个新建一个树的节点和链表的节点BTree newTree (BTree)calloc(1,sizeof(Tnode));LinkList newList (LinkList)calloc(1,sizeof(LinkNode));newTree-val data;newList-treenewTree;//进行判读是不是父亲节点if(tree NULL){tree newTree;//入队front rear newList;currear;}else{if(cur-tree-lc NULL){//插入左子树cur-tree-lcnewTree;//入队并更新尾指针rear-nextnewList;rear rear-next;}else{cur-tree-rc newTree;//入队并更新尾指针rear-nextnewList;rear rear-next;//注意这里左右子树都满了当前父亲节点要换cur cur-next;}}}
}//前序便利
void pre_print(BTree tree)
{if(tree){putchar(tree-val);pre_print(tree-lc);pre_print(tree-rc);}
}
void mid_print(BTree tree)
{if(tree){//左跟右mid_print(tree-lc);putchar(tree-val);mid_print(tree-rc);}
}
void post_print(BTree tree)
{if(tree){//左右跟post_print(tree-lc);post_print(tree-rc);putchar(tree-val);}
}
int main()
{BTree tree NULL;//树根LinkList frontNULL;LinkList rearNULL;//需要用到尾插法build_tree(tree,front,rear);pre_print(tree);puts();mid_print(tree);puts();post_print(tree);return 0;
}
前序便利根左右---先打印自身再左子树再右子树
//前序便利
void pre_print(BTree tree)
{if(tree){putchar(tree-val);pre_print(tree-lc);pre_print(tree-rc);}
}
中序遍历左根右---先打印左子树再打印自身再右子树 void mid_print(BTree tree)
{if(tree){//左跟右mid_print(tree-lc);putchar(tree-val);mid_print(tree-rc);}
}后序遍历左右根---先打印左子树再右子树再自身 void post_print(BTree tree)
{if(tree){//左右跟post_print(tree-lc);post_print(tree-rc);putchar(tree-val);}
}
【注意】以上三中便利采用递归思想。
代码运行结果如下 封装思想展示队列封装
#includestdio.h
#includestdlib.h
typedef char ElemType;//树
typedef struct trees{ElemType data;struct trees*lc;struct trees*rc;
}treeNode,*Tree;//链表
typedef struct Links{Tree tree;struct Links*next;
}LNode,*LinkList;//队列
typedef struct{LinkList front;LinkList rear;
}LinkQue;void init_que(LinkQueq)
{q.frontq.rear(LinkList)calloc(1,sizeof(LNode));q.frontq.rear;
}bool isEmpty(LinkQueq)
{return q.front q.rear;
}//入队
void push_que(LinkQueq,Tree tree)
{//新建链表节点LinkList newList (LinkList)calloc(1,sizeof(LNode));newList-nextNULL;newList-treetree;q.rear-nextnewList;q.rearq.rear-next;
}
bool pop_que(LinkQueq,Tree tree)
{if(isEmpty(q)){return false;}LinkList del q.front-next;//头结点不存数据第一个节点才是真的数据起始位置q.front-nextdel-next;//断链treedel-tree;if(q.rear del)//只剩下尾节点的数据{q.rearq.front;//置空}free(del);return true;
}void build_tree(Treetree)
{LinkQue q;init_que(q);LinkList cur NULL;ElemType data;while(scanf(%c,data) data ! \n){Tree newTree (Tree)calloc(1,sizeof(treeNode));//申请新的树的节点newTree-datadata;if(tree NULL){tree newTree;push_que(q,tree);//入队cur q.rear;}else{if(cur-tree-lc NULL){cur-tree-lc newTree;push_que(q,newTree);}else{cur-tree-rc newTree;push_que(q,newTree);//改变当前父亲节点cur cur-next;}}}
}void pre_print(Tree t)
{if(t){putchar(t-data);pre_print(t-lc);pre_print(t-rc);}
}
void mid_print(Tree t)
{if(t){mid_print(t-lc);putchar(t-data);mid_print(t-rc);}
}
void post_print(Tree t)
{if(t){post_print(t-lc);post_print(t-rc);putchar(t-data);}
}int main()
{Tree tree NULL;build_tree(tree);// pre_print(tree);return 0;
}
层次遍历在下节
