投稿
  1. 首页
  2. 随笔

JAVA第23天——二叉树（二）——遍历二叉树

江西网络干部学院 • 2022-12-17 • 随笔 • 阅读 13

JAVA第23天——二叉树（二）——遍历二叉树,第1张

JAVA第23天——二叉树（二）——遍历二叉树 遍历二叉树

一、几种遍历方法

深度遍历：

  1. 先序遍历二叉树的 *** 作定义为:
    若二叉树为空,则空 *** 作;否则
    (1)访问根结点；
    (2)先序遍历左子树；
    (3)先序遍历右子树。
  2. 中序遍历二叉树的 *** 作定义为:
    若三叉树为空,则空 *** 作;否则
    (1)中序遍历左子树；
    (2)访问根结点；
    (3)中序遍历右子树。
  3. 后序遍历二叉树的 *** 作定义为
    若二叉树为空,则空 *** 作;否则
    (1)后序遍历左子树；
    (2)后序遍历右子树；
    (3)访问根结点。

广度遍历：

  1. 层次遍历
    (1)严格的从左至右
    (2)从上到下

二、例子

  • 先序遍历：1 2 4 3 5
  • 中序遍历：4 2 1 3 5
  • 后序遍历：4 2 5 3 1
  • 层次遍历：1 2 3 4 5

二、代码实现（C语言，数据结构）

  1. 先序遍历
// 先序遍历
void PreorderTraversal(BiTree T) {
	if(T) {
		printf("%d ",T->data);
		PreorderTraversal(T->lchild);
	    PreorderTraversal(T->rchild);
	}
}
  1. 中序遍历
// 中序遍历
void InorderTraversal(BiTree T) {
	if(T) {
		InorderTraversal(T->lchild);
		printf("%d ",T->data);
	    InorderTraversal(T->rchild);
	}	
}
  1. 后序遍历
// 后序遍历
void PostorderTraversal(BiTree T) {
	if(T) {
		PostorderTraversal(T->lchild);
	    PostorderTraversal(T->rchild);
	    printf("%d ",T->data);
	}
}
  1. 层次遍历
// 层次遍历
void LevelorderTraversal(BiTree T) {
	if(T) {
		// 不用队列，只能取数组了
		BiTree B[100];
		// 根节点第一个
		B[0] = T;
		// 巧妙之处 
		int first = 0;
		int after = 1;
		// 循环 
		while(first < after) {
			printf("%d ",B[first]->data);
			if(B[first]->lchild) {
				B[after] = B[first]->lchild;
				after++;
			} // of if for lchild
			if(B[first]->rchild) {
				B[after] = B[first]->rchild;
				after++;
			} // of if for rchild
			first++;			
		} // end while
	} // end if
} // end LevelorderTraversal
  1. 二叉树的存储
typedef int TElemType;

// 二叉树的二叉链表存储表示
typedef struct BiTNode {
	TElemType data;
	struct BiTNode *lchild, *rchild;
}BiTNode, *BiTree;
void CreatBiTree(BiTree &T) {
	// 
	T = (BiTree)malloc(sizeof(BiTNode));
	// 
	TElemType data;
	scanf("%d",&data);
	if(data == -1) T = NULL;
	if(T) {
		T->data = data;
		printf("输入%d节点的左子节点：n",data);
		CreatBiTree(T->lchild);
		printf("输入%d节点的右子节点：n",data);
		CreatBiTree(T->rchild);		 
	} // end if
} // end CreatBiTree
  • C语言完整代码
#include
#include

typedef int TElemType;

// 二叉树的二叉链表存储表示
typedef struct BiTNode {
	TElemType data;
	struct BiTNode *lchild, *rchild;
}BiTNode, *BiTree;
void CreatBiTree(BiTree &T) {
	// 
	T = (BiTree)malloc(sizeof(BiTNode));
	// 
	TElemType data;
	scanf("%d",&data);
	if(data == -1) T = NULL;
	if(T) {
		T->data = data;
		printf("输入%d节点的左子节点：n",data);
		CreatBiTree(T->lchild);
		printf("输入%d节点的右子节点：n",data);
		CreatBiTree(T->rchild);		 
	} // end if
} // end CreatBiTree

// 先序遍历
void PreorderTraversal(BiTree T) {
	if(T) {
		printf("%d ",T->data);
		PreorderTraversal(T->lchild);
	    PreorderTraversal(T->rchild);
	}
}
// 中序遍历
void InorderTraversal(BiTree T) {
	if(T) {
		InorderTraversal(T->lchild);
		printf("%d ",T->data);
	    InorderTraversal(T->rchild);
	}	
}
// 后序遍历
void PostorderTraversal(BiTree T) {
	if(T) {
		PostorderTraversal(T->lchild);
	    PostorderTraversal(T->rchild);
	    printf("%d ",T->data);
	}
}
// 层次遍历
void LevelorderTraversal(BiTree T) {
	if(T) {
		// 不用队列，只能取数组了
		BiTree B[100];
		// 根节点第一个
		B[0] = T;
		// 巧妙之处 
		int first = 0;
		int after = 1;
		// 循环 
		while(first < after) {
			printf("%d ",B[first]->data);
			if(B[first]->lchild) {
				B[after] = B[first]->lchild;
				after++;
			} // of if for lchild
			if(B[first]->rchild) {
				B[after] = B[first]->rchild;
				after++;
			} // of if for rchild
			first++;			
		} // end while
	} // end if
} // end LevelorderTraversal
int main(void) {
	printf("输入根节点：n");
	BiTree T;
	CreatBiTree(T);
	printf("先序遍历：");
	PreorderTraversal(T); printf("n");
	printf("中序遍历：");
	InorderTraversal(T); printf("n");
	printf("后序遍历：");
	PostorderTraversal(T); printf("n");
	printf("层次遍历：");
	LevelorderTraversal(T); printf("n");
	return 0;
}
  • 效果图

三、代码实现（Java）

有点难，感觉。先想一下

  1. 先序遍历
	
	public void PreorderTraversal() {
		System.out.print(data + " ");
		if(lchild != null) {
			lchild.PreorderTraversal();
		}
		if(rchild != null) {
			rchild.PreorderTraversal();
		}
	}
  1. 中序遍历
	
	public void InorderTraversal() {
		if(lchild != null) {
			lchild.InorderTraversal();
		}
		System.out.print(data + " ");
		if(rchild != null) {
			rchild.InorderTraversal();
		}
	}
  1. 后序遍历
	
	public void PostorderTraversal() {
		if(lchild != null) {
			lchild.PostorderTraversal();
		}
		if(rchild != null) {
			rchild.PostorderTraversal();
		}
		System.out.print(data + " ");
	}
  1. 层次遍历
	
	public static void LevelorderTraversal(BiTree T) {
		if(T != null) {
			// 不用队列，只能取数组了
			BiTree[] B = new BiTree[100];
			// 根节点第一个
			B[0] = T;
			// 巧妙之处 
			int first = 0;
			int after = 1;
			// 循环 
			while(first < after) {
				System.out.printf("%d ",B[first].data);
				if(B[first].lchild != null) {
					B[after] = B[first].lchild;
					after++;
				} // of lchild
				if(B[first].rchild != null) {
					B[after] = B[first].rchild;
					after++;
				} // of rchild
				first++;			
			} // end while
		} // end if
		
	} // end LevelorderTraversal
  1. 比较简单的二叉树存储
	
	public BiTree CreatBiTree() {
		
		// 创建根节点
		BiTree T = new BiTree(1);
		
		// 创建树枝，值域
		BiTree T_l = new BiTree(2);
		BiTree T_r = new BiTree(3);
		BiTree T_l_l = new BiTree(4);
		BiTree T_r_r = new BiTree(5);
		
		// 指针域
		T.lchild = T_l;
		T.rchild = T_r;
		T_l.lchild = T_l_l;
		T_r.lchild = T_r_r;
		
		return T;
	}
  • 源码：
//package pta;

public class BiTree {
	
	
	int data;
	BiTree lchild;
	BiTree rchild;
	
	BiTree() {}
	
	
	BiTree(int elem) {
		data = elem;
		lchild = null;
		rchild = null;
	}
	
	
	public BiTree CreatBiTree() {
		
		// 创建根节点
		BiTree T = new BiTree(1);
		
		// 创建树枝，值域
		BiTree T_l = new BiTree(2);
		BiTree T_r = new BiTree(3);
		BiTree T_l_l = new BiTree(4);
		BiTree T_r_r = new BiTree(5);
		
		// 指针域
		T.lchild = T_l;
		T.rchild = T_r;
		T_l.lchild = T_l_l;
		T_r.lchild = T_r_r;
		
		return T;
	}
	
	
	public void PreorderTraversal() {
		System.out.print(data + " ");
		if(lchild != null) {
			lchild.PreorderTraversal();
		}
		if(rchild != null) {
			rchild.PreorderTraversal();
		}
	}
	
	
	public void InorderTraversal() {
		if(lchild != null) {
			lchild.InorderTraversal();
		}
		System.out.print(data + " ");
		if(rchild != null) {
			rchild.InorderTraversal();
		}
	}
	
	
	public void PostorderTraversal() {
		if(lchild != null) {
			lchild.PostorderTraversal();
		}
		if(rchild != null) {
			rchild.PostorderTraversal();
		}
		System.out.print(data + " ");
	}
	
	
	public static void LevelorderTraversal(BiTree T) {
		if(T != null) {
			// 不用队列，只能取数组了
			BiTree[] B = new BiTree[100];
			// 根节点第一个
			B[0] = T;
			// 巧妙之处 
			int first = 0;
			int after = 1;
			// 循环 
			while(first < after) {
				System.out.printf("%d ",B[first].data);
				if(B[first].lchild != null) {
					B[after] = B[first].lchild;
					after++;
				} // of lchild
				if(B[first].rchild != null) {
					B[after] = B[first].rchild;
					after++;
				} // of rchild
				first++;			
			} // end while
		} // end if
		
	} // end LevelorderTraversal
	
	
	public static void main(String[] args) {
		BiTree BT = new BiTree();
		
		System.out.print("先序遍历：");
		BT.CreatBiTree().PreorderTraversal();
		System.out.println();
		
		System.out.print("中序遍历：");
		BT.CreatBiTree().InorderTraversal();
		System.out.println();
		
		System.out.print("后序遍历：");
		BT.CreatBiTree().PostorderTraversal();
		System.out.println();
		
		System.out.print("层次遍历：");
		LevelorderTraversal(BT.CreatBiTree());
		System.out.println();
	}
}
  • 效果图：

欢迎分享，转载请注明来源：内存溢出

原文地址: http://outofmemory.cn/zaji/5692572.html

赞 (0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
江西网络干部学院 江西网络干部学院 一级用户组
0 0
上一篇 2022-12-17
下一篇 2022-12-17

发表评论

登录后才能评论

评论列表（0条）

保存