重慶涪陵網站建設南寧百度推廣seo
二叉樹鏈式存儲及遍歷
文章目錄
- 二叉樹鏈式存儲及遍歷
- 前言
- 實現(xiàn)過程
- 代碼實現(xiàn)
- 源代碼
- 總結
前言
本文章中的內容參考于王道數(shù)據結構考研書,如果你對該部分的內容的記憶有所模糊,可以閱讀我的文章再加深印象
實現(xiàn)過程
1.定義二叉樹結構體
2.初始化二叉樹的根結點
3.實現(xiàn)二叉樹鏈式存儲的插入操作
4.實現(xiàn)二叉樹的先序遍歷、中序遍歷、后序遍歷
代碼實現(xiàn)
- 定義二叉樹鏈式存儲的結構體
typedef struct BiTNode {int data; //數(shù)據域BiTNode* lchild;//左指針BiTNode* rchild;//右指針
}BiTNode,*BiTree;
- 初始化二叉樹的根結點
void InitTree(BiTree &root)
{//創(chuàng)建一個根結點root = (BiTree)malloc(sizeof(BiTNode));//初始化根結點數(shù)據root->data = { 1 };root->lchild = NULL;root->rchild = NULL;
}
- 定義插入操作的函數(shù),對插入操作的實習
void InsertNode(BiTree& root)
{BiTNode* p = (BiTNode*)malloc(sizeof(BiTNode));//將新創(chuàng)建的結點初始化p->data = { 2 };p->lchild = NULL;p->rchild = NULL;//將新結點變?yōu)閞oot的左孩子root->lchild = p;
}
- 先序遍歷
void PreOrder(BiTree root)
{if(root!=NULL){visit(root);PreOrder(root->lchild);PreOrder(root->rchild);}
}
- 中序遍歷
void InOrder(BiTree& root)
{if (root != NULL){InOrder(root->lchild);visit(root);InOrder(root->rchild);}
}
- 后序遍歷
void PostOrder(BiTree& root)
{if (root != NULL){PostOrder(root->lchild);PostOrder(root->rchild);visit(root);}
}
- 對遍歷visit函數(shù)的定義(這里遍歷就直接將其打印即可)
void visit(BiTNode* node)
{printf("%d", node->data);
}
源代碼
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>typedef struct BiTNode {int data;BiTNode* lchild;BiTNode* rchild;
}BiTNode,*BiTree;void InitTree(BiTree &root)
{//創(chuàng)建一個根結點root = (BiTree)malloc(sizeof(BiTNode));//初始化根結點數(shù)據root->data = { 1 };root->lchild = NULL;root->rchild = NULL;
}void InsertNode(BiTree& root)
{BiTNode* p = (BiTNode*)malloc(sizeof(BiTNode));//將新創(chuàng)建的結點初始化p->data = { 2 };p->lchild = NULL;p->rchild = NULL;//將新結點變?yōu)閞oot的左孩子root->lchild = p;
}void visit(BiTNode* node)
{printf("%d", node->data);
}void PreOrder(BiTree root)
{if(root!=NULL){visit(root);PreOrder(root->lchild);PreOrder(root->rchild);}
}void InOrder(BiTree& root)
{if (root != NULL){InOrder(root->lchild);visit(root);InOrder(root->rchild);}
}void PostOrder(BiTree& root)
{if (root != NULL){PostOrder(root->lchild);PostOrder(root->rchild);visit(root);}
}int main()
{//定義一個空樹BiTree root=NULL;//初始化根結點InitTree(root);//插入新結點InsertNode(root);//先序遍歷PreOrder(root);//中序遍歷InOrder(root);//后序遍歷PostOrder(root);return 0;
}
總結
如果本篇文章對你有所幫助,那么可以給我點個關注,我們一起進步!