二叉樹鏈式存儲及遍歷

前言

本文章中的內容參考于王道數(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;
}

總結

如果本篇文章對你有所幫助，那么可以給我點個關注，我們一起進步！