樹(shù)
定義:二叉樹(shù)是n（n>0）個(gè)節(jié)點(diǎn)的有限集合，該集合或者為空集（空二叉樹(shù)）,或者由一個(gè)根節(jié)點(diǎn)和兩棵互不相交分別稱(chēng)為根節(jié)點(diǎn)的左子樹(shù)和右子樹(shù)的二叉樹(shù)組成。
*** 注意：***
- n>0 時(shí)節(jié)點(diǎn)是唯一的，不可能存在多個(gè)節(jié)點(diǎn)，別和現(xiàn)實(shí)中的樹(shù)木混在一起。
- m>0 時(shí)，子樹(shù)的個(gè)數(shù)沒(méi)有限制，但是一定是不交互的。
樹(shù)的四種遍歷
遍歷：二叉樹(shù)的遍歷是指從根節(jié)點(diǎn)出發(fā),按照某種次序依次訪(fǎng)問(wèn)二叉樹(shù)中所有節(jié)點(diǎn),使得每個(gè)節(jié)點(diǎn)被訪(fǎng)問(wèn)依次且被訪(fǎng)問(wèn)依次。
- 前序遍歷
- 中序遍歷
- 后序遍歷
- 層序遍歷
前序遍歷
定義：規(guī)則是若二叉樹(shù)為空，則空操作返回。 否則先訪(fǎng)問(wèn)跟節(jié)點(diǎn)，然后前序遍歷左子樹(shù)，再遍歷右子樹(shù)。
優(yōu)先級(jí)：根->左->右
中序遍歷
定義：規(guī)則是樹(shù)若為空，操作返回，否則從根節(jié)點(diǎn)開(kāi)始，中序遍歷(注意并不是訪(fǎng)問(wèn)根節(jié)點(diǎn))根節(jié)點(diǎn)的左子樹(shù)，然后訪(fǎng)問(wèn)根節(jié)點(diǎn)，最后中序遍歷右子樹(shù)。
優(yōu)先級(jí)：左->根->右
后序遍歷
定義：規(guī)則是若樹(shù)空,操作返回，否則是從左到右先葉子后節(jié)點(diǎn)的方式遍歷訪(fǎng)問(wèn)左右子樹(shù)，最后是訪(fǎng)問(wèn)跟節(jié)點(diǎn)。
優(yōu)先級(jí)：左->右->根
層序遍歷
定義：規(guī)則是若樹(shù)空,操作返回，否則是從樹(shù)的第一層，也就是從根節(jié)點(diǎn)開(kāi)始訪(fǎng)問(wèn)，從上而下逐層遍歷，在同一層中，從左到右的順序?qū)?jié)點(diǎn)逐個(gè)訪(fǎng)問(wèn)。優(yōu)先級(jí)：頂部到底部的所有節(jié)點(diǎn)
代碼示例4中遍歷
這四種遍歷示例：
A
/ \
B C
/ \ / \
D E F G
層序遍歷結(jié)果是: ABCDEFG
前序遍歷結(jié)果是: ABDECFG
中序遍歷結(jié)果是: DBEAFCG
后序遍歷結(jié)果是: DEBFGCA
//節(jié)點(diǎn)對(duì)象
@interface Node : NSObject
@property (nonatomic) NSInteger data;//存儲(chǔ)的數(shù)據(jù)
@property (nonatomic) Node * leftNode; //左節(jié)點(diǎn)
@property (nonatomic) Node * rightNode; //右節(jié)點(diǎn)
@end
@implementation Node
@end
每一種遍歷其實(shí)都是遞歸，只是遞歸的時(shí)候，處理數(shù)據(jù)的代碼時(shí)機(jī)不一樣。
//前序 遍歷
/*
規(guī)則是若二叉樹(shù)為空，則空操作返回。 否則先訪(fǎng)問(wèn)跟節(jié)點(diǎn)，然后前序遍歷左子樹(shù)，再遍歷右子樹(shù)。跟->左->右
*/
-(void)printNode:(Node *)node{
if (node == nil) {
return;
}
NSLog(@"%ld",node.data);
[self printNode:node.leftNode];
[self printNode:node.rightNode];
}
// 中序遍歷 從 左子樹(shù)【左->根->右】
-(void)printCenterNode:(Node *)node{
if (node == nil) {
return;
}
[self printCenterNode:node.leftNode];
NSLog(@"%ld",node.data);
[self printCenterNode:node.rightNode];
}
// 后序遍歷 從 左子樹(shù)【左->右->根】
-(void)print2Node:(Node *)node{
if (node == nil) {
return;
}
[self print2Node:node.leftNode];
[self print2Node:node.rightNode];
NSLog(@"%ld",node.data);//節(jié)點(diǎn)數(shù)據(jù)可以進(jìn)行其他操作
}
//層序遍歷 迭代版本
func trav_L_R(tree:Tree) -> Void {
var i = 0
self.treesAray.append(tree);//添加根節(jié)點(diǎn)
while true {
//直到所有子樹(shù)都遍歷完成則退出
if i >= self.treesAray.count{break};
let t = self.treesAray[i];
if t.left != nil{//如果有左子樹(shù)就入棧
self.treesAray.append(t.left ?? Tree());
}
if t.right != nil{//如果有右子樹(shù)就入棧
self.treesAray.append(t.right ?? Tree());
}
i += 1;// 遍歷下個(gè)子樹(shù)
}
}
Swift版本
//中序遍歷
func travIn_C(tree:Tree?) -> Void {
if tree == nil{
return;
}
travIn_C(tree: tree?.left);
self.valsArray.append(tree?.val ?? 0);
travIn_C(tree: tree?.right);
}
//先序遍歷
func travIn_L(tree:Tree?) -> Void {
if tree == nil{
return;
}
self.valsArray.append(tree?.val ?? 0);
travIn_L(tree: tree?.left);
travIn_L(tree: tree?.right);
}
//后續(xù)遍歷
func travIn_R(tree:Tree?) -> Void {
if tree == nil{
return;
}
travIn_R(tree: tree?.left);
travIn_R(tree: tree?.right);
self.valsArray.append(tree?.val ?? 0);
}
二叉樹(shù)的迭代前中后序遍歷
原二叉樹(shù)
前序遍歷迭代：
前序遍歷迭代
中序遍歷迭代：
中序遍歷迭代
后序遍歷迭代
：
//先序遍歷
func travIn_I_L(tree:Tree?) -> Void {
if tree == nil{
return;
}
var t = tree;
while true {
while t != nil {
self.valsArray.append(t?.val ?? -1);
if t?.right != nil{
self.treesAray.append(t?.right ?? Tree());
}
t = t?.left;
}
if self.treesAray.count == 0 {
break;
}
t = self.treesAray.removeLast();
}
}
//中序遍歷
func travIn_I_C(tree:Tree?) -> Void {
if tree == nil{
return;
}
var t = tree;
while true {
while t != nil {
self.treesAray.append(t ?? Tree());
t = t?.left;
}
if self.treesAray.count == 0 {
break;
}
t = self.treesAray.removeLast();
self.valsArray.append(t?.val ?? -1);
//有右結(jié)點(diǎn) 則向右移動(dòng)一個(gè)節(jié)點(diǎn)
if t?.right != nil{
t = t?.right;
}else{//否則刪除已經(jīng)添加好的結(jié)點(diǎn)
t = nil;
}
}
}
//后續(xù)遍歷
func travIn_I_R(tree:Tree?) -> Void {
if tree == nil{
return;
}
var t = tree;
while true {
while t != nil {
self.treesAray.append(t ?? Tree());
t = t?.left;
}
if self.treesAray.count == 0 {
break;
}
t = self.treesAray.last;
//有右結(jié)點(diǎn) 則向右移動(dòng)一個(gè)節(jié)點(diǎn)
if t?.right != nil{
t = t?.right;
}else{//否則刪除已經(jīng)添加好的結(jié)點(diǎn)
self.valsArray.append(t?.val ?? -1);
self.treesAray.removeLast();
if self.treesAray.count > 0 {
let t1 = self.treesAray.last;
t1?.left = nil;
if t1?.right == t{//判斷是否是向上攀爬 YES則刪除右結(jié)點(diǎn)，否則不刪除
t1?.right = nil;
}
}
t = nil;
}
}
}
func isSymmetric(_ root: TreeNode?) -> Bool {
// 層序遍歷 校驗(yàn)是否是 對(duì)稱(chēng)樹(shù)
if root == nil {
return true;
}
var list :Array = [TreeNode]()
if let val = root {
list.append(val)
}
while list.count > 0 {
for index in 0...list.count/2 {
let node1 = list[index]
let node2 = list[list.count-index-1];
if isSameTree2(node1, node2) == false {
return false;
}
}
var subList:Array = [TreeNode]()
var end:Int = 0 //統(tǒng)計(jì)空節(jié)點(diǎn)
for index in list {
if let left = index.left {
subList.append(left)
}else {
end += 1
let left = TreeNode(0);
subList.append(left);
}
if let right = index.right {
subList.append(right)
}else {
end += 1
let left = TreeNode(0);
subList.append(left);
}
}
if end == subList.count {
subList.removeAll()
}
list.removeAll()
list += subList
subList.removeAll()
}
return true;
}
//判斷是否是相同的節(jié)點(diǎn)
func isSameTree(_ left:TreeNode?,_ right:TreeNode?) -> Bool {
if left == nil && right == nil {
return true;
}else if left == nil && right != nil {
return false
}else if left != nil && right == nil {
return false
}else if let val1 = left?.val {
let val2 = right?.val
if val1 == val2 {
return true;
}
}
return false;
}
//構(gòu)造節(jié)點(diǎn)
-(Node *)randNode{
Node * node =[Node new];
node.data = rand()%20 + 1;
return node;
}
其實(shí)平時(shí)都拿來(lái)數(shù)據(jù)是數(shù)組形式，并不能夠直接當(dāng)做二叉樹(shù)直接來(lái)操作，需要把數(shù)組轉(zhuǎn)化成二叉樹(shù)，那么怎么轉(zhuǎn)呢？
利用二叉樹(shù)的性質(zhì)，深度為k的節(jié)點(diǎn)的左子樹(shù)為k*2+1，右子樹(shù)為k*2+2。
那么滿(mǎn)二叉樹(shù)節(jié)點(diǎn)最多為2^(k)-1，最后一層葉子最多為2^(k-1)。得出最后一行的葉子的索引為2^(k-1)+1。所以假設(shè)數(shù)組有n個(gè)元素，則最后一行葉子的索引為n/2-1
得出 ：
func createTree() -> Tree? {
self.vals = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15];
self.top = createTreeWithArray(list: self.vals);
return top;
}
func createTreeWithArray(list:[Int]) -> Tree {
let length = list.count/2-1;
var tArray:[Tree] = [Tree]();
//生成數(shù)組 ??
for i in 0..<list.count{
let tsub = Tree.loadTree(val: list[i]);
tArray.append(tsub);
}
//構(gòu)造二叉樹(shù)??
for i in 0..<length{
let t :Tree = tArray[i];
//構(gòu)造左孩子
t.left = tArray[i*2+1];
//構(gòu)造右孩子
t.right = tArray[i*2+2];
}
//構(gòu)造最后一個(gè)做孩子
tArray[length].left = tArray[length*2+1];
if length%2 == 1{//若數(shù)組為奇數(shù)則存在右孩子
tArray[length].right = tArray.last;
}
//返回 topTree
return tArray[0];
}
